Quá trình băm làm việc như thế nào trong Từ điển <TKey, TValue>

Question

Quá trình băm làm việc như thế nào trong Từ điển? Tôi đọc rằng sử dụng từ điển cung cấp tìm kiếm nhanh hơn. Nhưng không hiểu sao? Làm thế nào để băm và lập bản đồ cho một chỉ mục xảy ra? Không thể tìm thấy bất kỳ tham chiếu nào tốt.

EDIT: Vị trí bộ nhớ thực tế nơi đối tượng được lưu trữ lấy từ kết quả của hàm băm?

Answer 1

Quy trình băm trong từ điển sử dụng kỹ thuật được gọi là chuỗi. Với chuỗi, 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 mảng các phần tử ánh xạ tới một nhóm. Trong trường hợp va chạm, phần tử va chạm được thêm vào danh sách của nhóm.

Xem this bài viết trên MSDN để biết thêm chi tiết.

Answer 2

Bằng cách sử dụng khái niệm Khoa học máy tính được gọi là Hash Map. Thao tác này hoạt động nhanh hơn tìm kiếm danh sách. Điều này hoạt động bằng cách giữ cho tìm kiếm không cần phải lặp qua danh sách cho đến khi tìm thấy kết quả phù hợp. Thay vào đó, khóa là "hashed" và được sử dụng làm chỉ mục trong danh sách. Hàm băm này hầu như luôn luôn nhanh hơn tìm kiếm danh sách (lặp lại với nhiều so sánh).

Answer 3

Thông thường, bằng cách lấy giá trị băm% kích thước mảng, có thể tạo ra xung đột.

Answer 4

Từ điển sử dụng các khóa băm để tra cứu như tôi đã cố gắng giải thích trong my answer to your other question. Vì vậy, nếu bạn có một loại đối tượng tùy chỉnh như là tất cả mọi thứ quan trọng phụ thuộc vào GetHashKey() thực hiện các đối tượng tùy chỉnh của bạn.

Answer 5

Bảng băm hoặc từ điển là cấu trúc dữ liệu lưu trữ cặp khóa-giá trị. Ưu điểm của bảng băm là việc tìm kiếm chính giá trị tương ứng là khá nhanh. Đơn giản hóa, thời gian để tìm cặp khóa-giá trị trong bảng băm không phụ thuộc vào kích thước của bảng. So sánh điều đó để lưu trữ các cặp khóa-giá trị trong một danh sách hoặc một mảng. Để tìm cặp khóa-giá trị, bạn sẽ phải tìm kiếm danh sách ngay từ đầu cho đến khi tìm thấy khóa khớp. Danh sách càng mất nhiều thời gian để tìm cặp khóa-giá trị. Sử dụng ký hiệu big-O bạn có thể nói rằng tìm kiếm một khóa trong bảng băm là thứ tự O (1) trong khi tra cứu một khóa trong danh sách bằng cách sử dụng tìm kiếm tuyến tính là thứ tự O (N) (đơn giản).

Để chèn cặp khóa-giá trị vào bảng băm, trước tiên bạn sẽ phải tính toán mã băm của khóa. Trong .NET tất cả các đối tượng có một phương thức có tên là GetHashCode trả về một mã băm (số nguyên 32 bit) cho đối tượng cụ thể đó. Điều quan trọng là các đối tượng bằng nhau trả lại mã băm giống nhau, nhưng cũng rất hữu ích nếu các đối tượng khác nhau trả về các mã băm khác nhau. Cẩn thận với quan niệm sai lầm rằng các đối tượng khác nhau không thể trả về cùng mã băm - chúng có thể, nhưng nó sẽ dẫn đến một vụ va chạm (xem bên dưới).

Như một ví dụ xem xét các mã băm của hai chuỗi:

 
"Boo" 0x598FD95A 
"Foo" 0x598FD8DE 

Mặc dù các dây rất giống nhau họ có mã hash khác nhau.

Tôi đơn giản hóa mọi thứ ở đây để tập trung vào các khía cạnh quan trọng của bảng băm, vì vậy bây giờ chúng ta hãy nói rằng các cặp khóa-giá trị trong một mảng. Để định vị chỉ mục trong mảng này, nơi cặp khóa-giá trị sẽ được lưu trữ, bạn phải tính toán mã băm của khóa modulo kích thước của mảng.Giả sử kích thước của mảng là 5:

 
Index("Boo") = 0x598FD95A % 5 = 4 
Index("Foo") = 0x598FD8DE % 5 = 0 

Điều này dẫn đến mảng bảng băm nội bộ này:

 
+---+---------+ 
| 0 | "Foo" | 
+---+---------+ 
| 1 | (empty) | 
+---+---------+ 
| 2 | (empty) | 
+---+---------+ 
| 3 | (empty) | 
+---+---------+ 
| 4 | "Boo" | 
+---+---------+ 

Nhìn lên một mục trong bảng băm là rất nhanh. Bạn chỉ cần tính toán mã băm của khóa modulo kích thước của mảng nội bộ và lấy chuỗi tại chỉ mục đó.

Bây giờ xem xét chìa khóa "Zoo":

 
Index("Zoo") = 0x598FDC62 % 5 = 0 

Nó có chỉ số giống như chìa khóa "Boo". Kết quả này được gọi là va chạm . Việc triển khai đúng bảng băm sẽ phải xử lý các va chạm và có different strategies for doing that. Ngoài ra, vì mảng nội bộ đầy lên sẽ có ít hơn và ít phần tử trống hơn trong mảng dẫn đến số lượng va chạm ngày càng tăng. Hệ số tải là tỷ lệ giữa các phần tử đã sử dụng và tổng số phần tử trong mảng nội bộ. Trong ví dụ trên, hệ số tải là 2/5 = 0,4. Hầu hết các triển khai bảng băm sẽ làm tăng kích thước của mảng nội bộ khi hệ số tải vượt quá một ngưỡng nhất định.

Nếu bạn muốn tìm hiểu thêm về một số khái niệm này, bạn sẽ phải nghiên cứu một số tài nguyên toàn diện hơn được liên kết trong các câu trả lời khác.