Boolean.hashCode ()

122

hashCode()Метод класса Boolean реализуется следующим образом:

public int hashCode() {
    return value ? 1231 : 1237;
}

Почему он использует 1231 и 1237? Почему не что-нибудь еще?

user471011
источник
1
Эти два числа являются достаточно большими простыми числами. Пожалуйста, прочтите статью о Хэш-таблице в Википедии для получения дополнительной информации.
Борис Павлович

Ответы:

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, распространенным способом создания хэш-функций составных объектов является повторное использование реализаций хэш-кода подкомпонентов, и в этом случае хорошо возвращать большие простые числа.

Связанные вопросы:

aioobe
источник
1
Я полагаю, они достаточно большие. Чтобы получить 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 (она же Дьявольская дюжина) - несчастливое число.

БВП
источник