Как Словарь внутренне сохраняется?
Возможно, вам понадобится добавить sysutils к предложению использования, оно не является встроенным и является дополнительным в соответствии с Delphi в двух словах.
4 ответа
Это не слишком далеко. Глядя на исходный код в Reflector, кажется, что используются три внутренних коллекций:
private Entry<TKey, TValue>[] entries;
private KeyCollection<TKey, TValue> keys;
private ValueCollection<TKey, TValue> values;
Обратите внимание, что есть также переменная int [] buckets для отслеживания buckets , необходимых в случай коллизии хэш-кода.
Назначение этих переменных должно быть достаточно понятным. Во всяком случае, это не особо удивительно,
Это хеш-таблица. Для каждого ключа Dictionary вычисляет свой хэш-код и использует его как указатель на место, где должно находиться значение. Если два ключа соответствуют одному и тому же хэш-коду, такая ситуация называется коллизией, и внутри этого особого случая Словарь использует двоичное дерево.
Алгоритмическая сложность словаря (хеш-таблицы) составляет O (1), а в худшем случае - O (log ( N)) (худший случай означает, что мы имеем дело только с коллизиями), где N - количество элементов в словаре.
Все четко написано на MSDN :
Универсальный класс Dictionary (Of TKey, TValue) обеспечивает отображение набора ключей в набор значений. Каждое дополнение к словарю состоит из значения и связанного с ним ключа. Получение значения с использованием его ключа происходит очень быстро, близко к O (1), потому что класс Dictionary (Of TKey, TValue) реализован в виде хэш-таблицы.
Нет, это хеш-таблица. Ну, это не совсем хеш-таблица, но она действительно тесно связана.