Điều gì sẽ xảy ra khi va chạm băm xảy ra trong khóa Từ điển?

Question

Tôi đã được viết mã trong C++ và java toàn bộ cuộc sống của tôi nhưng trên C#, tôi cảm thấy như nó là một con vật hoàn toàn khác nhau.

Trong trường hợp va chạm băm trong vùng chứa Từ điển trong C#, nó sẽ làm gì? hoặc thậm chí có phát hiện va chạm không?

Trong trường hợp va chạm trong các vùng chứa tương tự trong SDL, một số sẽ làm cho dữ liệu liên kết phần giá trị khóa thành phần giá trị khóa như danh sách được liên kết hoặc một số sẽ tìm phương pháp băm khác nhau.

[Cập nhật 10:56 A.M. 6/4/2010]

Tôi đang cố gắng tạo bộ đếm cho mỗi người dùng. Và đặt người dùng # không được xác định, nó có thể tăng hoặc giảm. Và tôi hy vọng kích thước của dữ liệu được so với 1000.

Vì vậy, tôi muốn:

• Truy cập nhanh tốt nhất là không O (n), Điều quan trọng là tôi có gần O (1) do theo yêu cầu, tôi cần đảm bảo rằng tôi có thể buộc đăng xuất mọi người trước khi họ có thể thực hiện điều gì đó ngớ ngẩn.
• Tăng trưởng và thu nhỏ động.
• dữ liệu duy nhất.

HashMap là giải pháp của tôi, và có vẻ như từ điển là những gì tương tự như HashMap trong C# ...

Answer 1

va chạm Hash được xử lý một cách chính xác bởi Dictionary<> - trong đó chừng một đối tượng thực hiện GetHashCode() và Equals() chính xác, ví dụ thích hợp sẽ được trả lại từ điển.

Trước tiên, bạn không nên đưa ra bất kỳ giả định nào về cách Dictionary<> hoạt động bên trong - đó là chi tiết triển khai có khả năng thay đổi theo thời gian. Có nói rằng ....

Điều bạn nên quan tâm là liệu các loại bạn đang sử dụng cho các phím có thực hiện GetHashCode() và Equals() chính xác hay không. Các quy tắc cơ bản là GetHashCode() phải trả lại cùng một giá trị cho tuổi thọ của đối tượng và rằng Equals() phải trả về true khi hai trường hợp đại diện cho cùng một đối tượng. Trừ khi bạn ghi đè nó, Equals() sử dụng bình đẳng tham chiếu - có nghĩa là nó chỉ trả về true nếu hai đối tượng thực sự là cùng một cá thể. Bạn có thể ghi đè cách hoạt động của Equals(), nhưng sau đó bạn phải đảm bảo rằng hai đối tượng 'bằng nhau' cũng sản xuất cùng một mã băm.

Từ quan điểm hiệu suất, bạn cũng có thể muốn cung cấp triển khai GetHashCode() tạo ra một phạm vi giá trị tốt để giảm tần suất va chạm hashcode. Nhược điểm chính của các xung đột hashcode là nó làm giảm từ điển thành danh sách về hiệu suất. Bất cứ khi nào hai trường hợp đối tượng khác nhau mang lại cùng một mã băm, chúng được lưu trữ trong cùng một nhóm nội bộ của từ điển. Kết quả của việc này là phải thực hiện quét tuyến tính, gọi Equals() trên mỗi trường hợp cho đến khi tìm thấy kết quả phù hợp.

Answer 2

tôi tin rằng nó sẽ thay đổi kích thước các mảng cơ bản là hai lần kích thước sau đó tái băm và rất có thể sẽ lấy một thùng mở.

Answer 3

Theo this article at MSDN, trong trường hợp xảy ra xung đột băm, lớp Dictionary chuyển đổi nhóm thành danh sách được liên kết. Mặt khác, lớp HashTable cũ hơn sử dụng việc phục hồi.

Answer 4

Kiểm tra liên kết này cho một lời giải thích tốt: An Extensive Examination of Data Structures Using C# 2.0

Về cơ bản, NET generic chuỗi từ điển mục có giá trị băm tương tự.

Answer 5

Tôi cung cấp câu trả lời theo mã thay thế để chứng minh một từ điển sẽ hiển thị hành vi không có ngoại lệ và có chức năng đúng khi hai mục có khóa khác nhau được thêm vào nhưng các khóa tạo cùng một mã băm.

Bật .Net 4.6 chuỗi "699391" và "1241308" tạo cùng một mã băm. Điều gì sẽ xảy ra trong đoạn mã sau?

myDictionary.Add("699391", "abc"); 
myDictionary.Add("1241308", "def"); 

Mã sau đây chứng minh rằng từ điển Net chấp nhận các khóa khác nhau gây ra xung đột băm. Không có ngoại lệ được ném và tra cứu khóa từ điển trả về đối tượng dự kiến.

var hashes = new Dictionary<int, string>(); 
var collisions = new List<string>(); 

for (int i = 0; ; ++i) 
{ 
    string st = i.ToString(); 
    int hash = st.GetHashCode(); 

    if (hashes.TryGetValue(hash, out string collision)) 
    { 
     // On .Net 4.6 we find "699391" and "1241308". 
     collisions.Add(collision); 
     collisions.Add(st); 
     break; 
    } 
    else 
     hashes.Add(hash, st); 
} 
Debug.Assert(collisions[0] != collisions[1], "Check we have produced two different strings"); 
Debug.Assert(collisions[0].GetHashCode() == collisions[1].GetHashCode(), "Prove we have different strings producing the same hashcode"); 

var newDictionary = new Dictionary<string, string>(); 
newDictionary.Add(collisions[0], "abc"); 
newDictionary.Add(collisions[1], "def"); 

Console.Write("If we get here without an exception being thrown, it demonstrates a dictionary accepts multiple items with different keys that produce the same hash value."); 

Debug.Assert(newDictionary[collisions[0]] == "abc"); 
Debug.Assert(newDictionary[collisions[1]] == "def");