почему используется простое число в hash функцпии?
От:
Аноним
Дата:
12.01.11 23:20
Оценка:
Добрый день, вы не могли бы на пальцах объяснить почему в функции для нахождения hash, пример для String:
int hash = 0;
for (char ch : str.toCharArray()) {
hash = hash * 31 + ch;
}
нужно использовать простое число (31 в нашем случае)
точнее, я догадываюсь, что так как используется не операция нахождения остатка после деления hash на длину hash таблицы, а битовая маска. т.к. эта операция эффективнее
меня интересует именно, почему простое число должно использоваться.
с битами не оч. силен, если можно в примере покажите...
Re: почему используется простое число в hash функцпии?
Здравствуйте, Аноним, Вы писали:
А>Добрый день, вы не могли бы на пальцах объяснить почему в функции для нахождения hash, пример для String: А>нужно использовать простое число (31 в нашем случае)
Здравствуйте, Аноним, Вы писали:
А>Добрый день, вы не могли бы на пальцах объяснить почему в функции для нахождения hash, пример для String: А>нужно использовать простое число (31 в нашем случае)
Я как-то интересовался данной темой, искал в разных книгах, в гугле и т.д. Мне показалось, что нет каких-то конкретных убедительных теорем, доказывающих, что использование простых чисел в хеш-функциях позволяет добиться лучших результатов (под лучшими результатами в хешировании понимается равная статистическая вероятность появления любого возможного результата хеш-функции, т.е. если хеш-фукнция допускает 100 различных значений от 1 до 100, то в идеале вероятность того, что результатом будет хеширования некоторого входного аргумента будет число 1 (или 2, или 100), должна быть равна 1%).
Тем не менее, на практике получается именно так, что использование простых чисел в хеш-функциях позволяет добиться лучших результатов.
В общем-то вот и все... Загадки математики
Re[2]: почему используется простое число в hash функцпии?
Здравствуйте, Lloyd, Вы писали:
А>>меня интересует именно, почему простое число должно использоваться.
L>Ну, дык, KISS-принцип: Keep It Simple S***** (Сохраняй Его Простым Д*****).
Простое число — prime number (а не simple)
Re[3]: почему используется простое число в hash функцпии?
Здравствуйте, de Niro, Вы писали:
L>>Ну, дык, KISS-принцип: Keep It Simple S***** (Сохраняй Его Простым Д*****).
DN>Простое число — prime number (а не simple)
Ну какой же вы нуудный.
Re[2]: почему используется простое число в hash функцпии?
Здравствуйте, de Niro, Вы писали:
L>>Ну какой же вы нуудный.
DN>Ну не все же хорошо знают английский. Кто-нибудь прочтет ваш перл и будет думать, что это правильный перевод.
для таких специально поставлен смайлик.
Re: почему используется простое число в hash функцпии?
Здравствуйте, Аноним, Вы писали:
А>Добрый день, вы не могли бы на пальцах объяснить почему в функции для нахождения hash, пример для String:
А>int hash = 0; А>for (char ch : str.toCharArray()) { А> hash = hash * 31 + ch; А>}
А>нужно использовать простое число (31 в нашем случае) А>точнее, я догадываюсь, что так как используется не операция нахождения остатка после деления hash на длину hash таблицы, а битовая маска. т.к. эта операция эффективнее А>меня интересует именно, почему простое число должно использоваться. А>с битами не оч. силен, если можно в примере покажите...
Хеши должны обладать такой интересной особенностью, что для двух похожих структур, желательно давать различные результаты(чем более различные тем лучше).
Тогда на реальных, скорее всего упорядоченных данных(не очень рандомных) не будет коллизий.
При использовании в хеш-таблицах, хеши, как Вы правильно заметили обычно берутся по модулю длины хеш-таблицы.
Пусть в качестве множителя мы выбрали число K(в яве оно 31).
Теперь рассмотрим такой простой ряд строк — предложения русского языка с точкой в конце(пример немного надуман, но при желании его можно обобщить)
