Почему хэштиное ведро занимает первичное число?
Иметь хэш -функцию
H (c) = c % n;
Когда n принимает составное число, самый простой пример - это взять 2^n, например, взять 2^3 = 8, в настоящее время
H (11100 (двоичный)) = h (28) = 4
H (10100 (двоичный)) = h (20) = 4
В настоящее время 4 -й бинарной (от справа влево) C будет «потерпеть неудачу», что означает, что независимо от того, какое значение принимается в 4 -м бите C, это приведет к тому же значению H (C). В настоящее время четвертый бит C вообще не участвует в работе H (C), поэтому H (C) не может полностью отразить характеристики C, увеличивая вероятность конфликта.
При приеме других составных чисел некоторые биты C будут «не удалены» в различных степени, что приведет к конфликтам в некоторых общих приложениях.
Тем не менее, принятие основных чисел может в основном гарантировать, что каждый бит C участвует в работе H (C), тем самым снижая вероятность конфликта в общих приложениях. ．
(Личное мнение: иногда эффективность не принимать основных чисел не так уж и плохо ... но, несомненно, безопаснее принимать основные цифры ...)
Выше всего, мое понимание
Чтобы добавить к этому, это означает, что в общих приложениях некоторые данные часто похожи. В настоящее время лучше использовать основные числа. Например, данные, которые будут сохранены, находятся в сжатом состоянии, например, хранение таблицы с описанием текущего состояния поиска. В настоящее время вероятность хэширования без основных чисел является относительно высокой.
Если это случайно распределенное целое число, то хэш -модуль будет таким же, когда он будет восприниматься достаточно большим, но это, очевидно, выходит из практического применения.
То, что вы сказали,-это особая ситуация, потому что, когда выбирается относительно небольшое первичное число, когда выбран большой основной номер N, оно может сбой только в определенном количестве N-цифровой системы. В сочетании с характеристиками компьютерной системы n-цифровое представление часто не является критическим, в то время как широко используемая система 2^n-цифры является более критической, поэтому можно избежать конфликтов.
На самом деле, я использовал несколько больших чисел, чтобы проверить его для хранения смежности, сжатой в двоичный файл. Когда модуль достаточно большой, даже составное число может оказать очень близкое влияние на основное число, но в некоторых (нескольких десятках) составных числах эффективность будет сильно снижена, поэтому основные числа относительно безопасны.
С таким же успехом вы можете провести свои собственные эксперименты, не выбирайте случайных целых чисел, но рассмотрим некоторые общие приложения, используйте основные числа и составные числа для тестирования, в основном изучая средний коэффициент загрузки, и вывод, который вы получаете, может быть таким же, как и у меня: составные числа также хороши в большей части времени, но эффект удивительно плохие в некоторых составных числах, и почти все основные числа имеют хорошие результаты.
Я лично думаю, что в более общем смысле, если вы не возьмете основные цифры, будет некоторая опасность. Опасность возникает, когда предполагается, что не преподавательное число m = x*y выбирается, и если ключ Хаша связан с этим делителем X, это будет несчастно. В худшем случае все предполагают, что это множество x, тогда вы можете себе представить, что результат хэша: 1 ~ y, а не 1 ~ m. Однако, если размер ведра выбран в качестве основного числа, проблем не будет.
Спасибо за чтение, я надеюсь, что это поможет вам. Спасибо за поддержку этого сайта!