В словарь со строковыми ключами добавляют 101 ключ, и поиск по всем ключам занимает 8 763 наносекунды. Добавляют 102-й — поиск занимает 718 наносекунд. Данных стало больше, времени ушло в 12 раз меньше.

Так работает защита Dictionary от ключей, подобранных под его хеш‑функцию. Ниже разобрано, что происходит на 102-й вставке, как словарь вычисляет номер бакета и при чём тут число 101.

Машина	Процессор	Система
Комп 1	Intel Core i9-10900KF 3.70GHz, 10 ядер	Windows 10 22H2
Комп 2	AMD Ryzen 9 5950X 3.39GHz, 16 ядер	Windows 10 1809
Комп 3	Intel Xeon W-2255 3.70GHz, 10 ядер	Windows Server 2022
Комп 4	Intel Xeon Silver 4314 2.40GHz, 2 CPU, 32 ядра	Windows Server 2022

Все машины x64

Рантаймы 8.0.29, 9.0.18 и 10.0.5 — все три в одном запуске BenchmarkDotNet 0.15.8 с DisassemblyDiagnoser. SDK 11 — предварительная сборка, к релизу числа могут измениться.

1. Что происходит на 102-м ключе

Исходник

Словарь считает, сколько записей он прошёл в одном бакете, пока искал место для нового ключа. Когда счётчик становится больше 100, выполняется это условие:

// Value types never rehash
if (!typeof(TKey).IsValueType && collisionCount > HashHelpers.HashCollisionThreshold && comparer is NonRandomizedStringEqualityComparer)
{
    // If we hit the collision threshold we'll need to switch to the comparer
    // which is using randomized string hashing
    Resize(entries.Length, true);
}

HashCollisionThreshold равен 100. Первым аргументом в Resize передаётся entries.Length — текущая длина массива записей. Новый массив будет такого же размера, и вместимость словаря не изменится.

Второй аргумент Resize равен true. По нему словарь заменяет компаратор и заново вычисляет хеш‑коды всех записей.

IEqualityComparer<TKey> comparer = _comparer =
    (IEqualityComparer<TKey>)((NonRandomizedStringEqualityComparer)_comparer)
        .GetRandomizedEqualityComparer();
 
for (int i = 0; i < count; i++)
{
    if (entries[i].next >= -1)
    {
        entries[i].hashCode = (uint)comparer.GetHashCode(entries[i].key);
    }
}

Что показывает замер

Ключи подобраны так, что у всех получается один номер бакета. Словарь создан с вместимостью 1024 — это 1103 бакета, и за время замера массив ни разу не увеличивается. Замеряется поиск всех ключей набора.

Ключей в бакете	Комп 1	Комп 2	Комп 3	Комп 4
50	2 848,3 ± 6,4	1 919,9 ± 3,5	3 034,1 ± 44,9	3 225,3 ± 39,4
101	10 634,3 ± 42,3	8 763,5 ± 28,2	12 521,8 ± 65,2	14 917,5 ± 147,7
102	730,8 ± 1,8	718,0 ± 9,3	944,2 ± 47,4	1 180,5 ± 18,2
200	1 479,5 ± 11,7	1 478,2 ± 5,2	1 866,2 ± 81,9	2 306,4 ± 24,3

Наносекунды, среднее и стандартное отклонение,.NET 10

Между 101 и 102 ключами время меняется в 12,21–14,55 раза в зависимости от машины.

То же самое на трёх рантаймах, AMD Ryzen 9 5950X:

Ключей в бакете	NET 8	NET 9	NET 10
101	8 725,3 ± 157,7	8 609,5 ± 84,7	8 763,5 ± 28,2
102	1 066,0 ± 11,4	1 056,6 ± 23,2	718,0 ± 9,3

Наносекунды, среднее и стандартное отклонение

Отчёт switch выводит имя типа компаратора после каждой вставки. Результат одинаков на всех четырёх машинах:

компаратор не задан
  до вставок           NonRandomizedStringEqualityComparer.OrdinalComparer
  после 101 вставок    NonRandomizedStringEqualityComparer.OrdinalComparer
  после 102 вставок    RandomizedStringEqualityComparer.OrdinalComparer
  замена на вставке    102
  занятых бакетов      189 из 1103

До замены компаратора все 101 ключ размещены в одном бакете. После замены те же ключи распределены по 180–189 бакетам.

Причина

Пока счётчик коллизий не превысил 100, словарь вычисляет хеш строки нерандомизированной функцией. Она дешевле, но её результат воспроизводим: он зависит только от символов строки и не меняется от запуска к запуску. Зная эту функцию, можно составить набор строк с одним номером бакета. Поиск по такому словарю выполняется за O(n) вместо O(1).

Часто в веб‑приложении ключи берутся из данных запроса: параметров строки запроса, заголовков, полей JSON. Если такие данные попадают в словарь, подобранный набор ключей заставляет процессор перебирать записи одного бакета вместо полезной работы. Такая атака называется hash flooding.

100 коллизий — граница, после которой словарь переходит на компаратор с рандомизированным хешем. Тот добавляет к вычислению случайное число, своё при каждом запуске, поэтому заранее составить набор ключей нельзя. Хеш‑коды вычисляются заново, записи распределяются по бакетам, и поиск снова выполняется за O(1).

В цикле пересчёта видно, зачем в поле next записаны отрицательные значения: хеш заново вычисляется только у записей, где next >= -1. Так словарь отличает занятые записи от тех, что остались после удаления ключей.

Ошибки при замере

Свой компаратор строк полностью выключает эту защиту. Условие срабатывает только тогда, когда компаратор — NonRandomizedStringEqualityComparer, а словарь подставляет его в трёх случаях: компаратор не передан, передан StringComparer.Ordinal, передан StringComparer.OrdinalIgnoreCase. С любым другим компаратором строк замена не выполнится, сколько бы коллизий ни набралось:

свой компаратор
  до вставок           Switch.OwnComparer
  после 101 вставок    Switch.OwnComparer
  после 102 вставок    Switch.OwnComparer
  замена на вставке    не выполнена
  занятых бакетов      1 из 1103

Все 200 ключей остались в одном бакете. Это не особенность замера: защиту снимает любой компаратор строк, кроме трёх перечисленных выше, — в том числе стандартный StringComparer.InvariantCulture.

Замена выполняется при вставке 102-го ключа, а не 101-го. Счётчик коллизий учитывает записи, уже занимающие бакет, поэтому условие «больше 100» выполняется, когда их 101.

Ключи для замера нельзя брать произвольные, их нужно подобрать. Проект повторяет нерандомизированный хеш строки и вычисление номера бакета. Сверка сравнивает вычисленный хеш с тем, который словарь сохранил в записи, и останавливает прогон при расхождении.

2. Деление, которого нет

Исходник

Номер бакета — остаток от деления хеш‑кода на длину массива бакетов. Вот как он вычисляется:

private ref int GetBucket(uint hashCode)
{
    int[] buckets = _buckets!;
#if TARGET_64BIT
    return ref buckets[HashHelpers.FastMod(hashCode, (uint)buckets.Length, _fastModMultiplier)];
#else
    return ref buckets[(uint)hashCode % buckets.Length];
#endif
}

В 32-битной сборке применяется оператор%. В 64-битной — вот это:

public static uint FastMod(uint value, uint divisor, ulong multiplier)
{
    uint highbits = (uint)(((((multiplier * value) >> 32) + 1) * divisor) >> 32);
 
    Debug.Assert(highbits == value % divisor);
    return highbits;
}

Множитель вычисляется один раз, когда создаётся массив бакетов: ulong.MaxValue / divisor + 1.

Что показывает замер

Миллион хеш‑кодов, делитель 1103,.NET 10.

Способ	Комп 1	Комп 2	Комп 3	Комп 4
остаток	1 582,374 ± 1,569	1 359,454 ± 2,042	1 908,304 ± 19,045	2 158,578 ± 23,292
два умножения	525,076 ± 2,151	574,721 ± 2,470	622,783 ± 10,758	1 006,177 ± 11,437

Микросекунды, среднее и стандартное отклонение

Машинного кода на два байта больше — 73 против 71, — а разница во времени в 2,15–3,06 раза.

Причина

Целочисленное деление — самая дорогая арифметическая операция на x86: она занимает десятки тактов и не выполняется конвейером. Когда делитель известен при компиляции, компилятор заменяет деление умножением. Здесь делитель — длина массива бакетов, она меняется каждый раз, когда словарь увеличивается, поэтому такая замена невозможна.

Словарь делает такую замену сам: множитель вычисляется один раз, а дальше остаток получается двумя умножениями и сдвигом. Способ описан Даниэлем Лемиром и добавлен в словарь этим обращением.

Ошибки при замере

Делитель нужно получать в рантайме. Если его записать числом, компилятор заменит деление умножением, и оператор% окажется не медленнее.

Способ работает только в 64-битной сборке: ему нужно умножение 64 на 64 бита. В 32-битной словарь использует оператор%.

3. 101 против 100

Исходник

Рядом с порогом коллизий 100 объявлена ещё одна константа — 101. Числа похожи, объявлены в одном файле, а связи между ними нет.

public const uint HashCollisionThreshold = 100;
 
public const int MaxPrimeArrayLength = 0x7FFFFFC3;
 
public const int HashPrime = 101;

101 используется при выборе размера таблицы, в GetPrime:

for (int i = min | 1; i < int.MaxValue; i += 2)
{
    if (IsPrime(i) && ((i - 1) % HashPrime != 0))
    {
        return i;
    }
}

Что показывает отчёт

Размер таблицы — всегда простое число, но подходит не любое: пропускаются те, у которых p — 1 делится на 101.

Простые числа, отброшенные при подборе размера таблицы:
 
      607   (p - 1) / 101 = 6
      809   (p - 1) / 101 = 8
     1213   (p - 1) / 101 = 12
     3637   (p - 1) / 101 = 36
     4243   (p - 1) / 101 = 42
 
Размеры, которые словарь берёт при росте вместимости:
 
  заказано      100   выбрано 101
  заказано     1000   выбрано 1009
  заказано    10000   выбрано 10007
  заказано   100000   выбрано 100003

Причина

101 применяется в Hashtable, откуда этот код перешёл в HashHelpers. В Hashtable используется двойное хеширование: шаг перебора следующих ячеек вычисляется по модулю size — 1. Если size — 1 делится на 101, у части ключей шаг оказывается кратным 101, и перебор обходит не все ячейки. Такие размеры заранее исключаются. В комментарии к InitHash сказано, что 101 взяли просто как простое число и выбор был во многом произвольным.

В Dictionary двойного хеширования нет: записи с одинаковым номером бакета складываются в цепочку, и делимость размера на 101 ни на что не влияет. Ограничение осталось от Hashtable, потому что оба типа берут размер таблицы из одного метода.

Замером это не показать: размер выбирается один раз, когда словарь увеличивается, и на время поиска не влияет.

Что ещё есть в исходниках

Поле next хранит два разных значения. У занятой записи это номер следующей записи в том же бакете. У той, что осталась после удаления ключа, — номер следующей свободной, записанный как StartOfFreeList — index, где StartOfFreeList равен -3. Отсюда правило: у занятой записи next не меньше -1, у свободной меньше.

Бакет хранит номер записи, увеличенный на 1. Значение 0 означает, что бакет свободен, а новый массив сразу состоит из нулей. Проходить по нему и записывать -1 при каждом увеличении словаря не нужно.

Отчёт entries выводит и то, и другое. Записи, оставшиеся после удаления ключа, он помечает словом «удалённая»:

после удаления двух ключей
  бакеты: 1 3 0 4 6 0 0
  запись 0  next  -1  живая     ключ key0
  запись 1  next  -2  удалённая ключ нет
  запись 2  next  -1  живая     ключ key2
  запись 3  next  -1  живая     ключ key3
  запись 4  next  -4  удалённая ключ нет
  запись 5  next  -1  живая     ключ key5

Границы замеров

Замеры раздела 2 сняты только на x64. В 32-битной сборке словарь использует оператор%, и сравнивать там нечего. Разделы 1 и 3 от разрядности не зависят.

Компаратор, массив бакетов и поле next приватные, публичного доступа к ним нет — проект читает их через рефлексию. Если реализацию словаря изменят, чтение перестанет работать: проект остановится и выведет имя поля, которое не нашёл.

Код из статьи

DictResizeProof — замеры, отчёты и выгрузки с четырёх машин

Ссылки

Всем удачи и до новых встреч!

А чё, так можно было? +1 ключ = ×12 к скорости