В соответствии с этим вопросом словарь .Net изменяет размер выделенного пространства на простые числа, которые по меньшей мере вдвое превышают текущий размер. Почему важно использовать простые числа, а не только в два раза больше текущего размера? (Я пытался использовать свои полномочия google-fu, чтобы найти ответ, но безрезультатно)
Почему. Онлайн-словари изменяются до простых чисел?
Ответ 1
Это деталь реализации алгоритма, связанная с выбором хорошей хэш-функции и обеспечивающей равномерное распределение. Неравномерное распределение увеличивает количество столкновений и затраты на их разрешение.
Ответ 2
Ведро, в которое помещается элемент, определяется (hash & 0x7FFFFFF) % capacity. Это должно быть равномерно распределено. Из этого следует, что если несколько записей, кратных некоторой базе (hash1 = x1 * base, hash2 = x2 * base,...), где base и capacity не являются взаимно простыми (наибольший общий делитель > 1), некоторые слоты более используются, а некоторые никогда не используются. Поскольку простые числа взаимно просты к любому числу, кроме самих себя, они имеют относительно хорошие шансы на достижение хорошего распределения.
Одним из особенно приятных свойств этого является то, что для capacity > 30 вклад каждого бита в хэш-код отличается. Поэтому, если изменение хэша сосредоточено всего в нескольких битах, оно все равно приведет к хорошему распределению. Это объясняет, почему мощь двух мощностей плоха: они маскируют высокие бит. Набор чисел, в которых отличаются только высокие бит, не так маловероятен.
Лично я думаю, что они плохо выбирают эту функцию. Он содержит дорогостоящую операцию по модулю, и если записи кратно первичной емкости, ее производительность прерывается. Но для большинства приложений это кажется достаточно хорошим.
Ответ 3
Из-за математики простых чисел. Их нельзя разделить на разные меньшие числа. Когда вы делите хэш-номер из сохраненных элементов, вы получаете равное распределение. Если у вас не будет простого числа, в зависимости от объектов, распределение может быть нечетным.