Как внутренний словарь поддерживается?

Question

Когда я говорю

Dictionary<int,string> 

это эквивалентно двум разным массивам, таких как:

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

Answer 1

Это не слишком далеко. Глядя на исходный код в отражатель, по-видимому, используются три внутренние коллекции:

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

Обратите внимание, что существует также int[] buckets переменная отслеживать buckets требуется в случае коллизий хэш-кода.

Цели этих переменных должны быть достаточно понятными. Это неудивительно, так как класс Dictionary известен и документирован, чтобы обеспечить (в идеале, с одним элементом на каждый ковш) O(1) время поиска.

Answer 2

Нет, это хэш-таблицы. Ну, это не совсем хеш-таблица, но она очень тесно связана.

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

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

Answer 3

Это все ясно написано на MSDN:

Словарь (Of TKey, TValue) общий класс обеспечивает отображение из множества ключей к набору значений. Каждое дополнение к словарю состоит из значения и связанного с ним ключа. Получение значения с помощью его ключа очень быстро, близко к O (1), потому что класс Dictionary (Of TKey, TValue) реализован как хеш-таблица.

Answer 4

Это хэш-таблица. Для каждого словаря Словарь вычисляет хэш-код и использует его как указатель на место, где должно находиться значение. Если есть два ключа, соответствующие одному и тому же хэш-коду, такая ситуация называется столкновением и внутренне для этого специального случая. Словарь использует двоичное дерево.

Алгоритмическая сложность словаря (хеш-таблица) - это O (1), а в худшем случае O (log (N)) (наихудший случай означает, что мы имеем дело только с столкновениями), где N - это число элементов в словаре.