Эти два числа являются достаточно большими простыми числами. Пожалуйста, прочтите статью о Хэш-таблице в Википедии для получения дополнительной информации.
Борис Павлович
Ответы:
140
1231 и 1237 - это всего лишь два (достаточно больших) произвольных простых числа . Подойдут любые другие два больших простых числа.
Почему простые числа?
Предположим на секунду, что мы выбрали составные числа (не простые числа), скажем, 1000 и 2000. При вставке логических значений в хеш-таблицу значения true и false перейдут в сегмент 1000 % Nсоответственно 2000 % N(где N- количество сегментов).
Теперь обратите внимание, что
1000 % 8 такое же ведро как 2000 % 8
1000 % 10 такое же ведро как 2000 % 10
1000 % 20 такое же ведро как 2000 % 20
....
другими словами, это привело бы к множеству столкновений .
Это потому, что факторизация 1000 (2 3 , 5 3 ) и факторизация 2000 (2 4 , 5 3 ) имеют так много общих факторов. Таким образом, выбираются простые числа, поскольку они вряд ли будут иметь общие множители с размером корзины.
Почему большие простые числа. Разве 2 и 3 не подойдут?
При вычислении хэш-кодов для составных объектов обычно добавляют хэш-коды для компонентов. Если в хеш-наборе с большим количеством сегментов используются слишком маленькие значения, существует риск получить неравномерное распределение объектов.
Имеют ли значение столкновения? В любом случае логические значения имеют два разных значения?
Карты могут содержать логические значения вместе с другими объектами. Кроме того, как указывает Drunix, распространенным способом создания хэш-функций составных объектов является повторное использование реализаций хэш-кода подкомпонентов, и в этом случае хорошо возвращать большие простые числа.
Я полагаю, они достаточно большие. Чтобы получить gcd больше 1, вам понадобятся как минимум 2*1231 = 2462ведра. Являются ли столкновения проблемой в такой ситуации?
aioobe
2
Интересно, однако, что они на самом деле не «довольно большие», учитывая то, что может поместиться в int. Я полагаю, что они достаточно велики, чтобы хорошо работать с JDK Hashtable, но все же достаточно малы, чтобы минимизировать затраты на вычисления.
Тило,
2
Да, он ударил меня тоже , что они не что большой. Но считаете ли вы, что большие простые числа дороже?
aioobe
3
@Thilo, вам понадобится число, кратное 1231 * 1237 = 1522747 ведер, прежде чем они столкнутся, этого достаточно,
урод с храповым механизмом
2
Я бы сказал, что приведение к конфликтам с подсчетом ведра на самом деле не проблема с логическим значением, а скорее обычная конструкция того, как мы получаем хэш-код составного объекта, а именно путем умножения хэш-кодов компонентов на некоторые константы и их сложения.
Drunix
2
Помимо всего сказанного выше, это может быть и небольшая пасхалка от разработчиков:
верно: 1231 => 1 + 2 + 3 + 1 = 7
7 - счастливое число в европейских традициях;
ложь: 1237 => 1 + 2 + 3 + 7 = 13
13 (она же Дьявольская дюжина) - несчастливое число.
Ответы:
1231 и 1237 - это всего лишь два (достаточно больших) произвольных простых числа . Подойдут любые другие два больших простых числа.
Почему простые числа?
Предположим на секунду, что мы выбрали составные числа (не простые числа), скажем, 1000 и 2000. При вставке логических значений в хеш-таблицу значения true и false перейдут в сегмент
1000 % Nсоответственно2000 % N(гдеN- количество сегментов).Теперь обратите внимание, что
1000 % 8такое же ведро как2000 % 81000 % 10такое же ведро как2000 % 101000 % 20такое же ведро как2000 % 20другими словами, это привело бы к множеству столкновений .
Это потому, что факторизация 1000 (2 3 , 5 3 ) и факторизация 2000 (2 4 , 5 3 ) имеют так много общих факторов. Таким образом, выбираются простые числа, поскольку они вряд ли будут иметь общие множители с размером корзины.
Почему большие простые числа. Разве 2 и 3 не подойдут?
При вычислении хэш-кодов для составных объектов обычно добавляют хэш-коды для компонентов. Если в хеш-наборе с большим количеством сегментов используются слишком маленькие значения, существует риск получить неравномерное распределение объектов.
Имеют ли значение столкновения? В любом случае логические значения имеют два разных значения?
Карты могут содержать логические значения вместе с другими объектами. Кроме того, как указывает Drunix, распространенным способом создания хэш-функций составных объектов является повторное использование реализаций хэш-кода подкомпонентов, и в этом случае хорошо возвращать большие простые числа.
Связанные вопросы:
источник
2*1231 = 2462ведра. Являются ли столкновения проблемой в такой ситуации?Помимо всего сказанного выше, это может быть и небольшая пасхалка от разработчиков:
7 - счастливое число в европейских традициях;
13 (она же Дьявольская дюжина) - несчастливое число.
источник