Va chạm băm qua một danh bạ nhỏ

Va chạm băm xảy ra khi hai khóa khác nhau chọn cùng một ngăn. Đây là tình huống bình thường trong bảng băm, nên cài đặt đúng phải xử lý được mà không ghi đè mục không liên quan. Nếu đang học từ điển, bạn có thể dùng danh bạ chỉ có năm ngăn để thấy rõ va chạm và tự theo dõi từng bước.

Ta dùng tên làm khóa và số máy lẻ hư cấu dạng chuỗi làm giá trị. Hàm băm minh họa cộng mã ký tự trong tên rồi lấy phần dư khi chia năm. Hàm này cố ý yếu và dễ đoán. Nó giúp giải thích việc lưu và tìm dữ liệu, không phải gợi ý chọn hàm băm cho ứng dụng thật.

Tên khác nhau vẫn có thể chọn cùng ngăn

Mã ASCII của các ký tự trong Amy cộng thành 295, giống tổng của May. Cả hai chọn ngăn không. Bob có tổng 275 và cũng chọn ngăn không. Số ngăn không cho biết tên có bằng nhau hay không; bảng vẫn phải so sánh khóa gốc.

Cách xử lý va chạm bằng nối chuỗi giữ một tập các mục trong mỗi ngăn. Khi tìm, tính ngăn rồi kiểm tra các mục bên trong đến khi gặp khóa khớp. Chỉ có thể kết luận không có giá trị sau khi đã xét mọi mục liên quan.

buckets = [[] for _ in range(5)]


def bucket_for(name):
    return sum(ord(character) for character in name) % len(buckets)


def put(name, extension):
    bucket = buckets[bucket_for(name)]
    for position, (key, _) in enumerate(bucket):
        if key == name:
            bucket[position] = (name, extension)
            return
    bucket.append((name, extension))


def get(name):
    comparisons = 0
    for key, extension in buckets[bucket_for(name)]:
        comparisons += 1
        if key == name:
            return extension, comparisons
    return None, comparisons

put('Amy', '201')
put('May', '202')
put('Bob', '203')
assert get('May') == ('202', 2)
assert get('Ann') == (None, 3)
put('May', '220')
assert get('May') == ('220', 2)

Ann có tổng mã ký tự 285. Truy vấn không tìm thấy này vào ngăn không và so sánh cả ba tên đang lưu. Một tên không tồn tại nhưng ánh xạ đến ngăn rỗng sẽ không cần so sánh khóa nào. Cả hai truy vấn đều thất bại, nhưng làm lượng công việc khác nhau.

Mở ảnh kích thước đầy đủ ↗

Hình đầu mô tả trạng thái sau ba lần thêm, trước khi cập nhật May.

Cập nhật May thay giá trị hiện tại, không thêm mục May thứ hai. Giao diện này là ánh xạ có một giá trị cho mỗi khóa chính xác. Amy và May vẫn là hai mục riêng dù chung cả tổng mã ký tự lẫn số ngăn.

Hệ số tải chỉ mô tả một giá trị trung bình

Với n mục và m ngăn, hệ số tải là alpha = n / m. Ví dụ có ba mục và năm ngăn nên hệ số tải bằng 0,6. Trung bình nhỏ không ngăn một ngăn chứa cả ba mục.

Trong mô hình băm ngẫu nhiên phù hợp, hệ số tải kiểm soát số khóa kỳ vọng cùng nằm trong một ngăn. Tìm kiếm với nối chuỗi khi đó cần kỳ vọng O(1 + alpha) phép so sánh khóa. Nếu bảng tăng số ngăn để giữ hệ số tải ở mức giới hạn, cận trở thành kỳ vọng O(1). Chương ChainedHashTable của Open Data Structures trình bày các giả định băm làm cơ sở cho kết quả này.

Không có các giả định đó, một lần tìm có thể phải xét mọi khóa đã lưu. Hàm cộng trong ví dụ tự làm các tên đảo thứ tự ký tự va chạm, cùng nhiều va chạm khác dễ dự đoán. Chỉ tăng số ngăn không sửa được trường hợp tổng mã bằng nhau: Amy và May va chạm với mọi môđun. Hàm trộn tốt hơn sẽ thay đổi cách thông tin trong khóa ảnh hưởng kết quả băm.

Số đếm trên còn xem một lần so sánh khóa là một thao tác. So sánh chuỗi dài có thể cần xét nhiều ký tự; tính mã băm chuỗi cũng cần đọc chuỗi nếu chưa có kết quả lưu lại. Khi độ dài khóa tăng theo bài toán, phải đưa nó vào mô hình. Cách nói từ điển O(1) thường giả định khóa có kích thước giới hạn hoặc tách chi phí băm khỏi chi phí truy cập ngăn.

Đổi kích thước phải phân bố lại mục đang có

Đổi số ngăn làm thay phép lấy phần dư. Mục ở ngăn không khi có năm ngăn có thể chuyển sang nơi khác khi có mười một. Vì thế phải đưa lại các mục theo số ngăn mới. Sao chép mỗi ngăn cũ sang cùng chỉ số ngăn mới là sai.

Khi số ngăn tỷ lệ với số mục, chuyển trực tiếp toàn bộ mục có khóa kích thước giới hạn cần O(n) công việc. Tăng dung lượng theo cấp số nhân cho phép phân bổ chi phí thỉnh thoảng này trên nhiều lần thêm, tạo cận khấu hao khi kết hợp với phân tích băm kỳ vọng. Kỳ vọng và khấu hao mô tả hai việc khác nhau: một bên lấy trung bình theo lựa chọn ngẫu nhiên, bên kia phân bổ chi phí trên chuỗi thao tác.

Chuyển dữ liệu khi môđun thay đổi

Có thể chuyển mục trực tiếp vì bảng hiện tại đã bảo đảm mỗi khóa chính xác xuất hiện nhiều nhất một lần. Không cần tìm khóa trùng lần nữa. Tạo các ngăn mới, tính lại đích của từng tên, rồi mới thay mảng ngăn của bảng.

def resize(new_count):
    global buckets
    if new_count <= 0:
        raise ValueError('bucket count must be positive')
    new_buckets = [[] for _ in range(new_count)]
    for bucket in buckets:
        for name, extension in bucket:
            slot = sum(ord(character) for character in name) % new_count
            new_buckets[slot].append((name, extension))
    buckets = new_buckets

before = {name: extension for bucket in buckets for name, extension in bucket}
resize(11)
after = {name: extension for bucket in buckets for name, extension in bucket}
assert after == before
assert bucket_for('Amy') == bucket_for('May') == 9
assert bucket_for('Bob') == 0
assert get('May') == ('220', 2)
assert get('Ann') == (None, 0)

Mở ảnh kích thước đầy đủ ↗

Với mười một ngăn, 295 chia dư chín, 275 chia dư không, còn 285 chia dư mười. Amy và May vẫn nằm cùng nhau vì tổng cộng đầy đủ của chúng bằng nhau. Bob tách ra vì cùng phần dư khi chia năm không có nghĩa tổng bằng nhau. Truy vấn Ann giờ gặp ngăn rỗng nên số so sánh khóa giảm từ ba về không. May vẫn cần hai phép so sánh trong chuỗi mới.

Với n khóa kích thước giới hạn, cài đặt này duyệt old_count ngăn cũ, tạo new_count ngăn rỗng và thêm mỗi mục đã biết đúng một lần. Chi phí là O(n + old_count + new_count). Nếu cả số ngăn cũ lẫn mới tỷ lệ với số mục khác không, lần đổi kích thước có chi phí O(n). Yêu cầu tạo một tỷ ngăn gần như rỗng không thể gọi là O(n) chỉ vì bảng có ba mục. Trong lúc chuyển, mảng ngăn cũ và mới cùng tồn tại, làm tăng bộ nhớ cực đại.

Chèn lại qua hàm công khai put sẽ lặp việc tìm khóa đang có. Nếu nhiều khóa vẫn va chạm, những lượt tìm này có thể xét các chuỗi dài dần và làm việc dựng lại thành bậc hai. Chuyển trực tiếp tránh kiểm tra trùng vì bất biến khóa duy nhất của bảng cũ đã cung cấp thông tin cần thiết. Việc tìm kiếm thông thường sau khi dựng lại vẫn chậm nếu hàm băm phân bố kém.

Mã nhận số ngăn nguyên dương và thay bảng toàn cục để giữ ví dụ nhỏ. Một lớp chứa dữ liệu trong ứng dụng thường giữ trạng thái trên đối tượng và quy định bộ lặp đang tồn tại sẽ thấy gì khi bảng đổi kích thước. Ví dụ không an toàn khi vừa đọc vừa ghi đồng thời. Vấn đề đó tách biệt với việc mỗi khóa đã vào đúng ngăn mới hay chưa.

Hãy đổi bảng ba tên thành một ngăn, rồi mười một, rồi năm. Sau mỗi lần, kiểm tra mọi khóa và số máy lẻ đã cập nhật. Thử cả bảng rỗng và kiểm tra rằng dung lượng bằng không bị từ chối. Dự đoán va chạm nào có thể biến mất khi chỉ đổi môđun, còn va chạm do đảo thứ tự ký tự nào buộc phải còn.

Với dịch vụ nhận khóa do bên ngoài chọn, va chạm dễ dự đoán có thể tạo rủi ro từ chối dịch vụ. Python mặc định ngẫu nhiên hóa mã băm chuỗi và byte. Tài liệu mô hình dữ liệu giải thích tính nhất quán của mã băm và lý do thêm giá trị ngẫu nhiên. Điều đó không bảo đảm mọi khóa tùy biến hay mọi thao tác từ điển đều có thời gian xấu nhất hằng số.

Băm trong ví dụ không che giấu tên

Bảng lưu khóa gốc để phân biệt các mục va chạm. Ai đọc cấu trúc này cũng đọc được tên và số máy lẻ. Số ngăn nhỏ không phải mã hóa, hàm băm mật khẩu hoặc cơ chế ẩn danh an toàn. Băm mật mã có mục tiêu thiết kế khác; ngay cả dùng nó để chọn ngăn cũng không mã hóa những mục đang lưu.

Hãy kiểm thử thêm mục, thay giá trị, tìm khóa thiếu trong ngăn có dữ liệu và trong ngăn rỗng. Kiểm tra cập nhật một khóa va chạm vẫn giữ nguyên các khóa khác. Những ca này kiểm tra trực tiếp giao diện ánh xạ. Trong ứng dụng, hãy dùng từ điển chuẩn của ngôn ngữ trừ khi có lý do cụ thể để tự cài đặt và duy trì chính sách va chạm.