Sự cố tràn xảy ra tại thời điểm bộ chứa chính cho một cặp mới (khóa, phần tử) đã đầy.
Chúng tôi có thể giải quyết sự cố tràn bằng
Tìm kiếm bảng băm theo một số cách có hệ thống để tìm một nhóm chưa đầy.
- Thăm dò tuyến tính (đánh địa chỉ mở tuyến tính).
- Thăm dò bậc hai.
- Thăm dò ngẫu nhiên.
Loại bỏ phần tràn bằng cách cho phép mỗi nhóm giữ danh sách tất cả các cặp mà nó là nhóm chính.
- Danh sách tuyến tính mảng.
- Chuỗi.
Định địa chỉ mở được thực hiện để đảm bảo rằng tất cả các phần tử được lưu trữ trực tiếp vào bảng băm, do đó nó cố gắng giải quyết các xung đột bằng cách thực hiện các phương pháp khác nhau.
Phép đo tuyến tính được thực hiện để giải quyết các xung đột bằng cách đặt dữ liệu vào vị trí mở tiếp theo trong bảng.
Hiệu suất của phép đo tuyến tính
- Thời gian tìm / chèn / xóa trường hợp xấu nhất là θ (m), trong đó m được coi là số cặp trong bảng.
- Điều này xảy ra khi tất cả các cặp nằm trong cùng một cụm.
Vấn đề về dò tuyến tính
- Các số nhận dạng đang có xu hướng tập hợp lại với nhau
- Các cụm liền kề đang có xu hướng liên kết lại với nhau
- Tăng hoặc nâng cao thời gian tìm kiếm
Phép dò bậc hai
Thăm dò tuyến tính tìm kiếm nhóm (H (x) + i2)% b; H (x) cho biết hàm băm của x
Khảo sát bậc hai thực hiện một hàm bậc hai của i là số gia
Kiểm tra các nhóm H (x), (H (x) + i2)% b, (H (x) -i2)% b, cho 1 <=i <=(b-1) / 2
b được biểu thị là số nguyên tố có dạng 4j + 3, j là số nguyên
Thăm dò ngẫu nhiên
Phép dò Ngẫu nhiên thực hiện kết hợp với các số ngẫu nhiên.
H(x):= (H’(x) + S[i]) % b S[i] is a table along with size b-1 S[i] is indicated as a random permutation of integers [1, b-1].