Cách từ điển được duy trì nội bộ?

Question

Khi tôi nói

Dictionary<int,string> 

là nó tương đương với hai mảng khác nhau như:

int[] keys =new int[] { 1, 2, 3 }; 
string[] values=new string[]{"val1","val2","val3"}; 

Answer 1

Không quá xa. Nhìn vào mã nguồn trong Reflector, có vẻ như ba bộ sưu tập nội bộ được sử dụng:

private Entry<TKey, TValue>[] entries; 
private KeyCollection<TKey, TValue> keys; 
private ValueCollection<TKey, TValue> values; 

Lưu ý rằng đó cũng là một biến int[] buckets để theo dõi các buckets yêu cầu trong trường hợp va chạm băm-mã.

Các mục đích của các biến này sẽ hoàn toàn tự giải thích. Tuy nhiên, điều này không có gì đáng ngạc nhiên vì lớp Dictionary được biết và được cung cấp tài liệu (lý tưởng, với một mục cho mỗi nhóm) O(1) thời gian tra cứu.

Answer 2

Không, đó là một bảng băm. Vâng nó không chính xác một bảng băm, nhưng nó thực sự liên quan chặt chẽ.

http://en.wikipedia.org/wiki/Hash_table.

http://www.kirupa.com/net/dictionary_hashtable.htm

Answer 3

Đó là tất cả viết rõ ràng trên MSDN:

Các từ điển (Tất TKey, TValue) lớp generic cung cấp một ánh xạ từ một tập hợp các phím để một tập hợp các giá trị. Mỗi bổ sung vào từ điển bao gồm một giá trị và khóa liên quan của nó. Lấy một giá trị bằng cách sử dụng khóa của nó là rất nhanh, gần với O (1), bởi vì lớp Từ điển (Of TKey, TValue) được thực hiện như một bảng băm.

Answer 4

Có thể bắt đầu bằng #. Đối với mỗi từ điển chính tính toán mã băm của nó, và sử dụng nó như là một con trỏ để đặt nơi giá trị nên cư trú. Nếu có hai khóa khớp với mã băm giống nhau, tình huống như vậy được gọi là va chạm và nội bộ trong trường hợp đặc biệt này, từ điển sử dụng cây nhị phân.

Độ phức tạp thuật toán của Từ điển (hashtable) là O (1) và trong trường hợp xấu nhất O (log (N)) (trường hợp xấu nhất có nghĩa là chúng ta chỉ xử lý các va chạm), trong đó N là một số phần tử trong từ điển.