Равномерно распределяющая хеш-функция. Как задействовать все биты хеш-кода? Доброго времени суток.
В книге Седжвика "Алгоритмы на Джава" я наткнулся на интересный параграф. Он касается создания равномерно распределяющей модульной хеш-функцией.
Значит есть размер массива M, максимальное значение int:int hash(Key key) {
// То что в скобках превращает 32-битное число в неотрицательное 31-битное
return (key.hashCode() & 0xfffffff) % mod;
}
Почему модульное хеширование, понятно, модуль от хеша берется чтобы можно было адресоваться к индексу в массив. Но есть одно большое НО, что мне и не ясно. Почему размер массива должен быть простым числом чтобы, как указал автор, "задействовать все биты хеш-кода"?
Чем так простые числа могут помочь?
Равномерно распределяющая хеш-функция. Как задействовать все биты хеш-кода? Доброго времени суток.
В книге Седжвика "Алгоритмы на Джава" я наткнулся на интересный параграф. Он касается создания равномерно распределяющей модульной хеш-функцией.
Значит есть размер массива M, максимальное значение int:int hash(Key key) {
// То что в скобках превращает 32-битное число в неотрицательное 31-битное
return (key.hashCode() & 0xfffffff) % mod;
}
Почему модульное хеширование, понятно, модуль от хеша берется чтобы можно было адресоваться к индексу в массив. Но есть одно большое НО, что мне и не ясно. Почему размер массива должен быть простым числом чтобы, как указал автор, "задействовать все биты хеш-кода"?
Чем так простые числа могут помочь?
В книге Седжвика "Алгоритмы на Джава" я наткнулся на интересный параграф. Он касается создания равномерно распределяющей модульной хеш-функцией.
Значит есть размер массива M, максимальное значение int:int hash(Key key) {
// То что в скобках превращает 32-битное число в неотрицательное 31-битное
return (key.hashCode() & 0xfffffff) % mod;
}
Почему модульное хеширование, понятно, модуль от хеша берется чтобы можно было адресоваться к индексу в массив. Но есть одно большое НО, что мне и не ясно. Почему размер массива должен быть простым числом чтобы, как указал автор, "задействовать все биты хеш-кода"?
Чем так простые числа могут помочь?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Простые числа используются не для того, чтобы задействовать все биты хеш-кода, а для того чтобы уменьшить вероятность коллизий при хешировании. Если размер массива M является простым числом, то хеш-код ключа будет равномерно распределен по всему массиву, что уменьшит вероятность возникновения коллизий. В противном случае, если размер массива является составным числом, то вероятность коллизий будет выше, так как хеш-код ключа будет сгруппирован в определенных интервалах по модулю размера массива. Поэтому часто рекомендуется использовать размеры массива, которые являются простыми числами, чтобы улучшить равномерность распределения хеш-кодов и снизить вероятность коллизий.