Реализация двойного хеширования для целых чисел, которые могут быть отрицательными
Я реализую класс хеш-функции для целых чисел, используя метод двойного хеширования. Входные данные будут случайными целыми числами, которые могут быть как положительными, так и отрицательными.
У меня вопрос, как я буду вычислять значение хеша отрицательных целых чисел?
Это метод:
hash function 1 h: h(k) = k mod (p)
hash function 2 s(k)= p –2 – (k mod(p-2))
p = table size, k = key
После вычисления h (k), если нет столкновения, оно будет вставлено в его положение. Если произойдет столкновение, я вычислю (h (k) + s (k)) mod p и сохраню ключ в результирующем значении вычисления.
Поэтому мой вопрос: если ключ является отрицательным целым числом, должен ли я взять его абсолютное значение (сделать его положительным), прежде чем его хешировать? Или есть другой способ?
Решение
От Сайт Принстонских Алгоритмов:
В: Что не так с использованием (s.hashCode ()% M) или Math.abs (s.hashCode ())% M для хеширования до значения от 0 до M-1?
A: Оператор% возвращает неположительное целое число, если его первый аргумент отрицателен, и это приведет к ошибке индексации массива вне пределов. Удивительно, но функция абсолютного значения может даже возвращать отрицательное целое число. Это происходит, если его аргумент Integer.MIN_VALUE, потому что получающееся положительное целое число не может быть представлено с использованием 32-разрядного целого числа с дополнением до двух. Этот вид ошибки будет чрезвычайно трудно отследить, потому что он будет происходить только один раз из 4 миллиардов! [Строковый хэш-код «полигенасмазочных материалов» -2 ^ 31. ]
Java вычисляет индекс из хеш-кода следующее:
static int indexFor(int hashcode, int length) {
return hashcode & (length-1);
}
Другие решения
Предполагая, что сначала вы хэшируете с помощью функции 1, а затем помещаете результат в функцию 2, результат всегда будет положительным числом.
В функции 2
If k > 0 => 0 < (k mod (p - 2)) < p - 2
Таким образом, функция 2 возвращает положительное значение
If k < 0 => (k mod (p - 2)) < 0
затем -(k mod (p - 2)) > 0
Таким образом, функция 2 возвращает положительное значение
В любом случае двойное хеширование вернет положительное значение из функции 2 независимо от того, является ли вход положительным или отрицательным.