Заметки о реализации hashCode() в Java

В этом случае Вам будет тяжело по hash коду различить даже (1, 0) и (0, 1).

Почему же лишнее, когда 2 не подходит?

Первый вопрос — а как вы думаете, почему в стандартной библиотеке используется chaining HashMap, когда open addressing, вообще говоря, в разы быстрее и в разы компактнее? Мое предположение — как раз потому, что chaining более толерантен к плохой хэш-функции. Тут уже правильно замечали — однократные коллизии мало что меняют, их практически нереально избежать для хэш-функции общего вида. Важно, чтобы не было явно выделенных точек, вокруг которых кучкуются значения хэша.

Т.е. вопрос состоит в выборе критерии качества хэша. Вы берете просто количество коллизий — это ок для прикидки, но не вполне понятно, как это скажется на реальной работе. По-хорошему качество хэша надо проверять так: брать хэш-таблицу (конкретную реализацию), генерировать набор ключей, вставлять, смотреть на гистограмму коллизий (гистограмма в осях кратность коллизии/количество). Брать другую хэш-функцию, делать то же самое. Я так (буквально недавно) выбирал хэш-функцию для справочников. Это тоже не однозначный вариант, то он хоть ближе к ответу на вопрос «какая хэш-функция лучше на практике». Еще ближе был бы эксперимент с последующим чтением некой подвыборки ключей, и подсчетом среднего количества проб — тут прямая (хоть и не обязательно точная) оценка именно производительности — того, что, в конечном счете, и нужно от хорошего хэша.

Универсальная реализация может быть хорошая, а может быть и не очень. Для примера из 3 short полей (как у Блоха) эта реализация не очень удачная. Если человеку нужно реализовать hashCode(), то он, обычно, или сгенерирует его с средствами IDE или обратиться к Блоху или Эккелю. И получит не очень хороший результат.

Меня смущает, что Блох не проводит оценки качества своего алгоритма. И не заостряет внимание на то, что этим нужно заняться, если у вас высоконагруженная система.

Кстати, для диапазона от 2³⁰ до 2³⁰+100 результат будет тот же.

Своей статьёй я хотел поднять вопрос, который особо нигде не обсуждается.

Я встречал обсуждения про overhead на переключение между tread'ами, а про эффективность реализации hash функции — нет.

И на всякий случай, вариант без умножения (таки довольно тяжёлая операция):

/* Количество элементов равно количеству чисел, участвующий в генерации хеш-функции.
Пространство хеш-функции делим пропорцинально кол-ву составляющий.
В нашему случае - 32 бита хеш-функция делится на два диапазона по 16 бит.
*/
const unsigned int P1= 70507 ;// Простое число для первого элемента.
unsigned int counter1=P1; // Счётчик для первого элемента.
unsigned int shift1=0; // Счётчик для сдвига второго числа.
const unsigned int P2= 69221;// Простое число для второго элемента.
unsigned int counter2=P2; // Счётчик для второго элемента.
unsigned int shift2=15; // Счётчик для сдвига второго элемента.

/* Возвращает хеш-функцию для любый двух чисел. */
unsigned int getHash(unsigned int n1, unsigned int n2) {
  // Вычисляем первую составляющую (для первого числа).
  // Циклический сдвиг суммы счётчика и значения на указанное число бит).
  unsigned int v1=couter1+n1;
  v1=(v1<<shift1)|(v1>>31-shift1);
  counter1+=P1; // Увеличиваем счётчик для первого элемента.
  shift1=(shift1+1)&31; // Увеличиваем значение сдвига первого элемента.
  // Аналогично вычисляем второй элемент:
  unsigned int v2=couter2+n2;
  v2=(v2<<shift2)|(v2>>31-shift2);
  counter2+=P2; // Увеличиваем счётчик для второго элемента.
  shift2=(shift2+1)&31; // Увеличиваем значение сдвига второго элемента.
  // Вычисляем и возвращаем хэш:
  return v1 xor v2;
}

Не разделяю я любовь отечественных программистов к функции XOR.

Берём P1=257, P2=16777259, рассматриваем две точки на плоскости.
В промежутке от 0 до 1500 — нет коллизий. В промежутке от 0 до 3000 получаем уже 3504 коллизии. Заменяем XOR на обычное сложение — коллизий не будет и в более широком промежутке.