Tràn xảy ra khi bucket (ngăn) chứa cặp mới (khóa, phần tử) đã đầy.
Chúng ta có thể xử lý tràn bằng:
Tìm kiếm trong bảng băm (hash table) một cách hệ thống để tìm bucket chưa đầy.
- Dò tuyến tính (linear probing / linear open addressing).
- Dò bậc hai (quadratic probing).
- Dò ngẫu nhiên (random probing).
Loại bỏ tràn bằng cách cho phép mỗi bucket giữ danh sách tất cả các cặp mà nó là bucket gốc.
- Danh sách tuyến tính mảng (array linear list).
- Chuỗi (chain).
Dò mở (open addressing) đảm bảo tất cả phần tử được lưu trực tiếp vào bảng băm, giải quyết va chạm bằng các phương pháp khác nhau.
Dò tuyến tính (Linear Probing) giải quyết va chạm bằng cách đặt dữ liệu vào ô trống tiếp theo trong bảng.
Hiệu năng của Dò tuyến tính
- Thời gian tìm/chèn/xóa trường hợp xấu nhất là Θ(m), với m là số cặp trong bảng.
- Xảy ra khi tất cả cặp nằm trong cùng một cụm (cluster).
Vấn đề của Dò tuyến tính
- Các định danh có xu hướng tập trung thành cụm.
- Các cụm liền kề có xu hướng hòa hợp.
- Làm tăng thời gian tìm kiếm.
Dò bậc hai (Quadratic Probing)
Dò tuyến tính tìm bucket (H(x) + i²) % b; H(x) là hàm băm của x.
Dò bậc hai dùng hàm bậc hai của i làm bước nhảy.
Kiểm tra các bucket H(x), (H(x) + i²) % b, (H(x) - i²) % b, với 1 ≤ i ≤ (b-1)/2.
b là số nguyên tố dạng 4j+3, j là số nguyên.
Dò ngẫu nhiên (Random Probing)
Dò ngẫu nhiên kết hợp với các số ngẫu nhiên.
H(x) := (H'(x) + S[i]) % b S[i] là bảng kích thước b-1, là hoán vị ngẫu nhiên của các số nguyên [1, b-1].