Loại độ phân giải va chạm nào được chọn để triển khai HashTable/Dictionary trong .net?

Question

Như chúng ta biết có 2 chiến lược cổ điển để giải quyết va chạm: Chaining riêng biệt và giải quyết mở.

Tôi tự hỏi cái nào đã được chọn cho HashTable/Từ điển trong .net.

Hoặc đã sử dụng một số chiến lược khác?

Answer 1

Đó là tất cả được mô tả trong bài viết này trên MSDN: An Extensive Examination of Data Structures Using C# 2.0

... va chạm kỹ thuật giải quyết gọi rehasing, mà là kỹ thuật được sử dụng bởi lớp Hashtable Framework của .NET. Trong phần cuối cùng, chúng ta sẽ xem xét lớp Từ điển, sử dụng kỹ thuật giải quyết va chạm biết là chuỗi. ....

... Khôi phục hoạt động như sau: có bộ hàm băm khác nhau chức năng, H1 ... Hn và khi chèn hoặc lấy một mục từ bảng băm, ban đầu là băm H1 chức năng được sử dụng. Nếu điều này dẫn đến đến va chạm, H2 được thử thay vào đó, và trở lên tới Hn nếu cần. Phần trước chỉ hiển thị một hàm băm, là hàm băm ban đầu (H1). Các hàm băm khác rất giống nhau với hàm này, chỉ khác biệt bởi một yếu tố nhân. Trong Nhìn chung, hàm băm Hk được định nghĩa là:

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize 

Lớp điển khác với lớp Hashtable trong nhiều cách hơn một. Ngoài việc được gõ mạnh, từ điển cũng sử dụng một chiến lược giải quyết va chạm khác với lớp Hashtable , sử dụng kỹ thuật được gọi là chuỗi. Nhớ lại rằng với thăm dò, trong trường hợp va chạm một khe khác trong danh sách các thùng được thử. (Với việc khôi phục, băm được tính toán lại và rằng vị trí mới được thử.) Với chuỗi, tuy nhiên, cấu trúc dữ liệu thứ cấp được sử dụng để giữ bất kỳ xung đột nào. Cụ thể, mỗi vị trí trong từ điển có một loạt các phần tử ánh xạ tới nhóm đó. Trong sự kiện va chạm, phần tử va chạm được thêm vào danh sách của nhóm .

Ghi chỉ câu đầu tiên là của riêng tôi :-)

Answer 2

Đó thực sự là một câu hỏi thực sự thú vị; Tôi vừa mới thực hiện một số blog post về cách Dictionary được thực hiện phía sau hậu trường. Tôi có thể bao gồm Hashtable sau này.