Использование большего простого числа в качестве множителя при переопределении hashCode()

Я читал о функциях hashcode в течение последних нескольких часов и накопил пару вопросов относительно использования простых чисел в качестве множителей в пользовательских реализациях hashcode. Я был бы признателен, если бы мог получить представление о следующих вопросах:

В комментарии к @mattb answer здесь @hstoerr выступает за использование больших простых чисел (например, 524287) вместо общего простого 31. Мой вопрос заключается в следующем выполнении функций хэш-кода для пары или элементов:
```
@Override
public int hashCode() {
    final int prime = 31;
    int hash1 = (pg1 == null) ? 0 : pg1.hashCode();
    int hash2 = (pg2 == null) ? 0 : pg2.hashCode();
    return prime * (hash1 ^ hash2);
}
```

не приводит ли это к переполнению возвращенного int, если prime - большое число?

Предполагая, что переполнение не является проблемой (JVM делает автоматическую подборку), лучше ли выполнять бит-брейд вместо трансляции?
Я полагаю, что производительность функции hashcode значительно варьируется в зависимости от сложности хэш-кода. Не влияет ли размер первичного множителя на производительность?
Лучше/умнее/быстрее использовать несколько простых чисел в пользовательской функции hashcode вместо одного множителя? Если нет, есть ли другое преимущество? См. Пример ниже из ответа @jinguy на соответствующий вопрос:
```
public int hashCode() {
    return a * 13 + b.hashCode() * 23 + (c? 31: 7);
}
```

где a является int, b является String и c является boolean.

Как насчет чего-то типа long lhash = prime * (hash1 ^ hash2);, затем используя (int)((lhash >> 32) ^ lhash)? Это то, что я видел по другому вопросу здесь, но не было объяснено, почему было хорошей идеей сделать это так.

Ответ 1

Извините заранее за роман. Не стесняйтесь делать предложения или редактировать напрямую. --Chet

Существует переполнение, но не исключение.

Опасность исходит не от потери точности, а от потери диапазона. Позвольте использовать нелепый пример, где "prime" - это большая мощность 2 и 8-разрядных беззнаковых чисел для краткости. И предположим, что (hash1 ^ hash2) равен 255:

        "prime": 1000 0000
(hash1 ^ hash2): 1111 1111

Показывая укороченные цифры в скобках, наш результат:

        product: [0111 1111] 1000 0000

Но умножение на 128 - это то же самое, что и сдвиг слева на 7 мест. Поэтому мы знаем, что независимо от значения (hash1 ^ hash2) наименее значимые места продукта будут иметь семь нулей. Поэтому, если (hash1 ^ hash2) является нечетным (младший значащий бит = 1), то результатом умножения на 128 всегда будет 128 (после усечения более высоких цифр). И если (hash1 ^ hash2) равно (LSB равно 0, то произведение всегда будет равно нулю.

Это распространяется на более крупные размеры бит. Общая точка заключается в том, что если младшие разряды "prime" являются нулями, вы выполняете операцию сдвига (или многократную смену + сумму), которая даст вам нули в младших битах. И диапазон продукта умножения будет страдать.

Но попробуйте сделать "prime" нечетным, так что младший бит всегда будет 1. Подумайте о том, чтобы разложить это на операции shift/add. Неперемещаемое значение (hash1 ^ hash2) всегда будет одним из слагаемых. Меньшезначные биты, которые были переведены в гарантированную бесполезность с помощью четного множителя "prime" , теперь будут устанавливаться на основе, как минимум, битов исходного значения (hash1 ^ hash2).

Теперь рассмотрим значение prime, которое фактически является простым. Если это больше 2, то мы знаем, что это нечетно. Таким образом, младшие бит не были перенесены в бесполезность. И, выбирая достаточно большое простое, вы получаете лучшее распределение по диапазону выходных значений, чем вы получите с меньшим простым.

Попробуйте выполнить некоторые упражнения с 16-битным умножением с использованием 8443 (0010 0000 1111 1011) и 59 (0000 0000 0011 1011). Они оба простые, а младшие бит 59 соответствуют младшим битам 65531. Например, если hash1 и hash2 являются символьными значениями ASCII (0.. 255), то все результаты (hash1 ^ hash2) * 59 будет <= 15045. Это означает, что примерно 1/4 диапазона значений хеша (0..65535) для 16-разрядного номера не используется.

Но (hash1 ^ hash2) * 8443 по всему отображению. Он переполняется, если (hash1 ^ hash2) меньше 8. Он использует все 16 бит даже для очень маленьких номеров ввода. Там гораздо меньше кластеризации хеш-значений в общем диапазоне, даже если номера ввода находятся в относительно небольшом диапазоне.

Предполагая, что переполнение не является проблемой (JVM делает автоматическое приведение), лучше ли выполнять бит-брейд вместо трансляции?

Скорее всего, нет. В любом случае JVM должна перевести на эффективную реализацию на хост-процессор. Целочисленное умножение должно быть реализовано на аппаратном уровне. И если нет, то JVM отвечает за перевод операции во что-то разумное для CPU. Очень вероятно, что случай целочисленного умножения уже сильно оптимизирован. Если целочисленное умножение выполняется быстрее на заданном процессоре как shift-and-add, JVM должен реализовать его таким образом. Но менее вероятно, что люди, пишущие JVM, будут следить за случаями, когда несколько операций shift-and-add могли быть объединены в одно целое число.

Я предполагаю, что производительность функции hashcode значительно варьируется в зависимости от сложности хэш-кода. Имеет ли размер от простого множителя не влияют на производительность?

Нет. Операции такие же, когда выполняются на аппаратном уровне независимо от размера, количества бит и т.д. Это, вероятно, пара тактов. Он будет меняться в зависимости от конкретного процессора, но должен быть постоянной работой независимо от входных значений.

Лучше/умнее/быстрее использовать несколько простых чисел в пользовательской функции hashcode вместо одного множителя? Если нет, есть ли какое-то другое преимущество?

Только если это уменьшает вероятность коллизий, и это зависит от числа, которое вы используете. Если ваш хеш-код зависит от A и B, и они находятся в одном диапазоне, вы можете рассмотреть возможность использования разных простых чисел или смещения одного из входных значений, чтобы уменьшить совпадение между битами. Поскольку вы зависите от своих индивидуальных хеш-кодов, а не от их значений напрямую, разумно предположить, что их хэш-коды обеспечивают хорошее распределение и т.д.

Один фактор, который приходит на ум, хотите ли вы, чтобы хэш-код для (x, y) отличался от (y, x). Если ваша хэш-функция относится к A и B таким же образом, тогда hash(x, y) = hash(y, x). Если это то, что вы хотите, то непременно используйте один и тот же множитель. Это не так, использование разного множителя имеет смысл.

Как насчет чего-то типа long lhash = prime * (hash1 ^ hash2);, затем используя (int)((lhash >> 32) ^ lhash)? Это то, что я видел по другому вопросу здесь, но это было не совсем объяснено, почему было хорошей идеей сделать это так.

Интересный вопрос. В Java longs являются 64-битными, а int - 32-разрядными. Таким образом, это генерирует хэш, используя в два раза больше бит, а затем выводит результат из сочетания высоких и низких бит.

Если умножить число n на простой p, а самые нижние k биты n - это все нули, то самые нижние биты k продукта n * p также будут всех нулей, Это довольно легко увидеть - если вы умножаете, скажем, n = 0011 0000 и p = 0011 1011, тогда произведение можно выразить как сумму двух операций сдвига. Или,

00110000 * p = 00100000 * p + 00010000 * p
             = p << 5 + p << 4

Взяв p = 59 и используя 8-битные биты без знака и 16-битные длины, вот несколько примеров.

 64: 0011 1011 * 0100 0000 = [ 0000 1110 ] 1100 0000 (192)
128: 0011 1011 * 1000 0000 = [ 0001 1101 ] 1000 0000 (128)
192: 0011 1011 * 1100 0000 = [ 0010 1100 ] 0100 0000 (64)

Просто отбрасывая высокие биты результата, диапазон получаемого хеш-значения ограничен, когда младшие биты несимметричного мультипликатора - все нули. Является ли эта проблема конкретным контекстом, а также контекстно-зависимая. Но для общей хэш-функции рекомендуется избегать ограничения диапазона выходных значений, даже если на входных номерах имеются шаблоны. И в приложениях безопасности еще более важно избегать всего, что позволяло бы кому-либо делать выводы об исходном значении, основанном на шаблонах в выходе. Простое использование младших бит показывает точные значения некоторых исходных бит. Если мы исходим из предположения, что операция включала умножение входного числа на большое простое число, то мы знаем, что исходное число имело столько же нулей справа, как и хэш-выход (потому что первый правый бит был равен 1).

Посредством XORing высоких бит с младшими битами в выходе меньше согласованности. И что еще более важно, гораздо сложнее сделать предположения о входных значениях на основе этой информации. Основываясь на том, как работает XOR, это может означать, что первоначальный младший бит равен 0, а старший бит равен 1, или исходный младший бит равен 1, а старший бит равен 0.

 64: 0011 1011 * 0100 0000 = 0000 1110 1100 0000 => 1100 1110 (206)
128: 0011 1011 * 1000 0000 = 0001 1101 1000 0000 => 1001 1101 (157)
192: 0011 1011 * 1100 0000 = 0010 1100 0100 0000 => 0110 1100 (204)

Ответ 2

Переполнение не является проблемой. Хэши в любом случае ограничены узким значением.
Первая функция хэша, которую вы опубликовали, не очень хороша. Выполнение return (prime * hash1) ^ hash2; `вместо этого уменьшило бы количество столкновений в большинстве случаев.
Умножение на одно слово int обычно происходит очень быстро, а разница между умножением на разные числа пренебрежимо мала. Кроме того, время выполнения затмевается всем остальным в функции anyay
Использование разных простых множителей для каждой части может снизить риск столкновений.