Boolean.hashCode()

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

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

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

Ответы

Ответ 1

1231 и 1237 - всего два (достаточно больших) произвольных простых числа. Любые другие два больших простых числа будут хорошо.

Почему простые?
Предположим, что на секунду мы выбрали составные числа (не простые), скажем, 1000 и 2000. При вставке булевых в хэш-таблицу true и false переходят в ведро 1000 % N resp 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?
При вычислении хэш-кодов для составных объектов обычно добавляется хэш-коды для компонентов. Если слишком малые значения используются в хеш-наборе с большим количеством ковшей, существует риск привести к неравномерному распределению объектов.

Имеют ли проблемы столкновения? Boolean просто имеет два разных значения?
Карты могут содержать булевы вместе с другими объектами. Кроме того, как отметил Drunix, общий способ создания хеш-функций составных объектов заключается в повторном использовании реализаций хэш-кода подкомпонентов, и в этом случае полезно возвращать большие простые числа.

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

Ответ 2

В дополнение ко всему вышесказанному это может быть также маленькое пасхальное яйцо от разработчиков:

true: 1231 => 1 + 2 + 3 + 1 = 7

7 - счастливое число в европейских традициях;

false: 1237 => 1 + 2 + 3 + 7 = 13

13 (он же Devil дюжина) - несчастливое число.