Словарь использует хеш-код для вычисления номера корзины, в которой хранится запись. Количество сегментов выбирается как простое число, и номер сегмента для конкретного ключа вычисляется как хэш-код ключа по модулю количества сегментов. Поскольку несколько объектов могут иметь один и тот же хэш-код, а несколько хэш-кодов могут попадать в один и тот же сегмент, при обнаружении ключа в сегменте его также необходимо сравнить на равенство, чтобы убедиться, что это правильный ключ. Если в корзине найден неправильный ключ, элемент next неправильной записи используется для поиска следующего места для поиска нужного ключа.
Результатом этого алгоритма является то, что при отсутствии коллизий правильный сегмент может быть найден очень быстро - O (1), но в худшем случае это может занять линейное время в количестве записей, хранящихся в словаре. Здесь я предполагаю, что хеш-код для объекта может быть вычислен за постоянное время.
Фактический код в реализации .NET можно увидеть, загрузив эталонный источник реализации или используя .NET Reflector:
private int FindEntry(TKey key)
{
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (this.buckets != null)
{
int num = this.comparer.GetHashCode(key) & 0x7fffffff;
for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next)
{
if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key))
{
return i;
}
}
}
return -1;
}