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

Question

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

Dictionary<int,string>

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

Все это четко написано на MSDN :

  

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

Answer 4

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

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

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