Класс Dictionary в .NET оснащен защитой от атак типа hash flooding. При достижении 100 коллизий в одном бакете словарь при следующей вставке меняет нерандомизированный компаратор строк на рандомизированный. Это происходит на 102-м ключе, после чего хеш-коды пересчитываются, а записи распределяются по разным бакетам, возвращая сложность поиска к O(1).
Защита срабатывает только при использовании стандартных компараторов, таких как Ordinal или OrdinalIgnoreCase. Использование пользовательских компараторов отключает этот механизм, что позволяет злоумышленникам замедлить работу словаря до O(n) путем подбора ключей с одинаковым хешем. В таких условиях процессор вынужден перебирать все записи в одной цепочке.
В 64-битных сборках .NET для вычисления номера бакета применяется метод оптимизации деления, предложенный Даниэлем Лемиром. Вместо дорогостоящей операции деления словарь использует предварительно вычисленный множитель, выполняя умножение и сдвиг. Это ускоряет вычисления в 2–3 раза по сравнению с обычным оператором взятия остатка, который используется в 32-битных версиях.
Константа 101, используемая при выборе размера таблицы, является наследием старой реализации Hashtable. Она нужна для исключения простых чисел, при которых двойное хеширование работало бы неэффективно. Хотя в современном Dictionary двойное хеширование не применяется, ограничение сохранилось в общих вспомогательных методах HashHelpers.
