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

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 для отслеживания сегментов , необходимых в случае коллизий хеш-кода.

Цели этих переменных должны быть достаточно понятными. В любом случае, это не особенно удивительно, поскольку класс 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