Thực hiện Hashtable

Question

Gần đây tôi đã được hỏi 'làm thế nào bạn sẽ thực hiện một hastable'. Tôi biết thuật toán băm là rất quan trọng vì ít va chạm hiệu suất WRT tốt hơn, nhưng cấu trúc thuật toán/dữ liệu nào nên được sử dụng để phân phối thời gian cố định phân bổ {O (1)} cho chèn/xóa/tra cứu?

Answer 1

bảng Hash có hai khả năng chính:

1. mở Addressing, mà là một mảng đơn giản [mảng động actualy nếu bạn thể để bàn của bạn phát triển một cách nhanh chóng]. Khi một cuộc xung đột đã gặp nhau - bạn cần sử dụng hàm băm thứ hai để tìm entree tiếp theo mà phần tử sẽ được ánh xạ tới. Lưu ý giải pháp này có một số rắc rối [có thể được giải quyết] khi bảng băm của bạn cũng cho phép xóa. [Dấu đặc biệt cho món khai vị "xóa"]
2. Chaining - trong dung dịch này, mỗi entree trong mảng là một danh sách liên kết - containig tất cả các yếu tố băm để entree này. Ở đây - tất cả các phần tử được ánh xạ tới một giá trị nhất định nằm trong danh sách.

Phần quan trọng về các bảng băm [trong cả hai giải pháp] để cho phép armotorized O (1) chèn/del/nhìn lên - được phân bổ một bảng lớn hơn và xào xáo lại một lần trước được xác định load factor đã đạt được.

EDIT: phức tạp analsis:
Giả sử một hệ số tải của p đối với một số p < 1.

1. Xác suất "va chạm" trong mỗi truy cập là p Như vậy giá trị trung bình của mảng truy cập là: Sigma(i * p^(i-1) * (1-p)) for each i in [1,n] này mang đến cho bạn: Sigma(i * p^(i-1) * (1-p)) = (1-p) * Sigma(i * p^(i-1)) <= (1-p) * 1/(p-1)^2 = 1-p = CONST. [xem xét tính chính xác của Sigma(i * p^(i-1)) < 1/(p-1)^2 in wolfram alpha]. Do đó, kết quả là số lần truy cập trung bình vào mảng. Ngoài ra: Bạn có thể cần phải rehash tất cả các yếu tố sau khi đạt được yếu tố tải, kết quả là truy cập O(n) vào mảng. Điều này dẫn đến việc sử dụng các công cụ n * O(1) ops [thêm phần tử n] và 1 * O(n) op [rehashing], vì vậy bạn sẽ nhận được: (n * O(1) + 1 * O(n))/n = O(1) thời gian được thực hiện.
2. Rất giống với (1), nhưng phân tích được thực hiện trên danh sách truy cập. Mỗi hoạt động yêu cầu chính xác một truy cập mảng và một số biến thể truy cập danh sách - với cùng phân tích như trước đây.