Не так давно я клянусь, что дал подробный ответ на этот вопрос, это заняло у меня некоторое время, так как некоторые детали и концепции были немного ржавыми с моей стороны, но вот оно:
Как словарь .NET работает по длине (или по типу).
Давайте начнем с концепции, как указывалось во многих других ответах, Dictionary<TKey, TValue> является общим (в смысле языка C #).feature) реализация хеш-таблицы .
хеш-таблица - это просто ассоциативный массив, то есть когда вы передаете пару (ключ, значение), тогда ключ используется для вычисленияхеш-код, который поможет вычислить местоположение (называемое сегментом) в базовом массиве хранения (называемом сегментом), в котором будет сохранена пара и некоторая другая дополнительная информация.Обычно это достигается путем вычисления по модулю % хеш-кода для размера массива / сегментов: hashCode % buckets.Length.
Этот тип ассоциативного массива имеет среднюю сложность O (1) (т.е.Постоянное время) для поиска, вставки и удаления ... за исключением определенных обстоятельств, которые мы рассмотрим позже.Так что, вообще говоря, поиск слов в словаре гораздо быстрее, чем в списке или массиве, поскольку вам не нужно ~ обычно ~ перебирать все значения.
Если вы обратили внимание на то, чтописал до сих пор, вы заметили, что, возможно, уже есть проблема.Что если хеш-код, вычисленный из нашего ключа, такой же, как для другого, или, что еще хуже, для множества других ключей, и мы окажемся в том же месте?Как мы управляем этими столкновениями ?Что ж, люди, очевидно, уже думали об этом десятилетия назад и придумали, по сути, 2 основных способа решения коллизий:
- Раздельное объединение в цепочку : в основном пара хранится в другом хранилище, чемсегменты (часто называемые записями), например, для каждого сегмента (каждого вычисленного индекса) у нас может быть список записей, в котором хранятся различные значения, которые были сохранены в одном и том же «индексе» (из-за одного и того же хэш-кода), в основном в случае, есликоллизий вы должны перебирать ключи (и находить другой способ, кроме хеш-кода, чтобы различать их)
- Открытая адресация : все хранится в корзинах и основывается на первомОбнаружено, что мы проверяем следующее, также существуют различные схемы для определения значений Линейный зонд , Квадратичный зонд , Двойное хеширование и т. д.)
Реализация любого из разрешения коллизий иногда может сильно отличаться.В случае словаря .NET структура данных основывается на разрешении коллизий с раздельной цепочкой, как мы увидим через несколько минут.
Хорошо, теперь давайте посмотрим, как вещи вставляются в .NET Dictionary<TKey, TValue>, которыйсводится к следующему коду метода:
private void Insert(TKey key, TValue value, bool add)
Примечание: после прочтения приведенных ниже шагов вставки вы можете выяснить обоснование операций удаления и поиска, проверив кодв качестве ссылки в источниках.
Шаг 1: Дайте мне хэш-код
Существует два способа вычисления хеш-кода клавиши TKey.:
Можно полагаться на компаратор реализации по умолчанию IEqualityComparer<TKey>, если вы не передаете его как параметр Dictionary<TKey, TValue>, который в основном генерируется EqualityComparer<TKey>.Default (реализация доступна * 1056)* здесь ), в случае если TKey является типом, отличным от всех обычных вещей (таких как примитивы и строки), такими как пользовательский тип, IEqualityComparer<in TKey> будет использовать реализацию (включая override s) из:
bool Equals(object obj)int GetHashCode()
Другой, ну, в общем, полагается нареализацию IEqualityComparer<in TKey> можно передать конструктору Dictionary<TKey, TValue>.
Интерфейс IEqualityComparer<in T> выглядит так:
// The generic IEqualityComparer interface implements methods to if check two objects are equal
// and generate Hashcode for an object.
// It is use in Dictionary class.
public interface IEqualityComparer<in T>
{
bool Equals(T x, T y);
int GetHashCode(T obj);
}
В любом случае, словарь заканчивает тем, что имеет первый хеш-код с использованием компаратора: comparer.GetHashCode()
Шаг 2: Получить целевое ведро
Хеш-код, который мы получили от нашего ключа TKey через IEqualityComparer<in T>, иногда может быть отрицательным, что не очень полезно, если мы хотимчтобы получить положительный индекс для массива ...
В результате получается, что для избавления от отрицательных значений хеш-код Int32, полученный с помощью comparer.GetHashCode(), равен "ANDed" с Int32.MaxValue (то есть. 2147483647 или 0x7FFFFFFF) (в смысле логической логики: биты):
var hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
Целевое ведро (индекс) получается следующим образом:
var targetBucket = hashCode % buckets.Length
В этот момент также увидим, как изменяется размер массива buckets.
Поле buckets (int[]) - это поле private поля Dictionary<TKey, TValue>, содержащее индексы первогосоответствующий слот в поле entries, равном Entry[], где Entry определяется следующим образом:
private struct Entry
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
key, value и hashcode являются полями, не требующими пояснений,что касается поля next, то оно в основном указывает индекс, если в этой цепочке есть другой элемент (т. е. несколько ключей с одинаковым хеш-кодом), если этозапись является последним элементом цепочки, тогда для поля next установлено значение -1.
Примечание: поле hashCode в Entry struct - это поле после корректировки отрицательного значения.
Шаг 3: проверьте, есть ли уже запись
На этом этапе важно отметить, что поведение отличается в зависимости от того, обновляетесь ли вы (add = false) или строго вставляя (add = true) новое значение.
Теперь мы проверим записи, относящиеся к targetBucket, начиная с первой записи, которая может быть задана как:
var entryIndex = buckets[targetBucket];
var firstEntry = entries[entryIndex];
Фактический (упрощенный) исходный код с комментариями:
// Iterating through all the entries related to the targetBucket
for (var i = buckets[targetBucket]; i >= 0; i = entries[i].next)
{
// Checked if all
if (entries[i].hashCode == hashCode &&
comparer.Equals(entries[i].key, key))
{
// If update is not allowed
if (add)
{
// Argument Exception:
// "Item with Same Key has already been added" thrown =]
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
// We update the entry value
entries[i].value = value;
// Modification while iterating check field
version++;
return;
}
}
Примечание: поле version - это поле, которое также используется в других распространенных структурах данных .NET (например,List<T>), который помогает обнаруживать при итерации (на MoveNext()) (и выдавать соответствующее исключение).
Шаг 4: проверить, нужно ли изменять размеры массивов
// The entries location in which the data will be inserted
var index = 0;
// The freeCount field indicates the number of holes / empty slotes available for insertions.
// Those available slots are the results of prior removal operations
if (freeCount > 0)
{
// The freeList field points to the first hole (ie. available slot) in the entries
index = freeList;
freeList = entries[index].next;
// The hole is no longer available
freeCount--;
}
else
{
// The entries array is full
// Need to resize it to make it bigger
if (count == entries.Length)
{
Resize();
targetBucket = hashCode % buckets.Length;
}
index = count;
count++;
}
Примечание: вызов about Resize():
- Он удваивает размер базовых массивов (
buckets и entries), как и многие другие коллекции, чтобы избежать слишком большого количества операций по изменению размера, предоставляя достаточно места при изменении размера коллекции . - Double - >> ish <<, так как размер может быть только простым числом изпредварительно вычисленный набор <code>Int32 например.
3, 7, 11, 17, ..., 7199369, поскольку использование простого может уменьшить количество столкновений (см. , который отвечает на SO )
На самом деле в начале метода Resize() новый размер вычисляется следующим образом:
public static int ExpandPrime(int oldSize)
{
var min = 2 * oldSize;
if ((uint) min > 2146435069U && 2146435069 > oldSize)
{
return 2146435069;
}
return HashHelpers.GetPrime(min);
}
Шаг 5: Добавить запись
Так каксловарь завершает проверку отверстий и размера, затем он может, наконец, добавить запись, используя вычисленные значения hashCode, key, value и правильное значение index, которое только что было вычислено, и соответствующим образом скорректировать целевое ведро:
entries[index].hashCode = hashCode;
// If the bucket already contained an item, it will be the next in the collision resolution chain.
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
// The bucket will point to this entry from now on.
buckets[targetBucket] = index;
// Again, modification while iterating check field
version++;
Бонус: специальная обработка строк
Цитируется из источника CodeProject, указанного ниже:
Для того, чтобы каждый 'получалОперации 'и' добавление 'не будут проходить более 100 пунктов для каждого сегмента, используется счетчик столкновений.
Если при обходе массива для поиска или добавления элемента счетчик столкновений превышает 100 (предел жестко задан) и IEqualityComparer имеет тип EqualityComparer<string>.Default, создается новый экземпляр IEqualityComparer<string>генерируется для альтернативного алгоритма хеширования строк.
Если такой поставщик найден, словарь будет выделять новые массивы и копировать содержимое в новые массивы, используя новый хэш-код и поставщик равенства.
Эта оптимизация может быть полезна для сценария, в котором ваши строковые ключи каким-то образом распределяются неравномерно, но также может привести к значительному выделению ресурсов и потере процессорного времени для генерации новых хэш-кодов, которые могут содержать много элементов.в словаре.
Использование
Всякий раз, когда вы используете пользовательский тип в качестве ключа, не забудьте иметь пользовательский IEqualityComparer или переопределить два метода Object (hashcode + equal), чтобы впоследствии избежать неожиданностей при вставке.
Вы не только избежите некоторых сюрпризов, но и сможете контролировать распределение вставляемых вами предметов.Равномерно распределяя хеш-коды, вы избегаете объединения слишком большого количества элементов и, таким образом, тратите время на итерации по этим записям.
Примечание для интервьюируемых / собеседников
Я хотел бы подчеркнутьтот факт, что знание этих деталей реализации для интервью, как правило, не имеет большого значения (фактическая реализация отличается от некоторых версий .NET («Обычная» или Core ...), плюс все еще может подвергаться изменениям)).
Если бы кто-то задал мне вопрос, я бы сказал:
- Ответ, который вы ищете, находится в StackOverflow:)
- Ответ, который вы ищетеfor также может быть
- Ответ, который вы ищете, не нуждается в деталях реализации и официальной документации здесь или будет достаточно для большинства случаев использования.
Если, кроме случаев, когда ... вы должны внедрить себя в свои ежедневные рабочие хеш-таблицы, в этом случае такие знания (т.е. подразумеваемые детали) могут считаться полезными илидаже обязательный.
Источники: