#algorithm #hashtable
Вопрос:
В случае обычных хэш — таблиц, кодирующих текст. Может быть, вы просто получаете меньше столкновений, потому что диапазон чисел больше?
Редактировать: Кумулятивная сумма компонентов-это функция, которая возвращает факториал строковых значений ASCII. т. е. s=»строка» -> s[0] (s[0] s[1]) (s[0] s[1] s[2]) … до лена(ов).
Обычная сумма равна просто s[0] s[1] s[2]…
Комментарии:
1. Определите «функцию хэш-кода суммарной суммы компонентов» и, пока вы занимаетесь этим, «регулярное суммирование значений ASCII». Ценности чего?
2. Совокупная сумма компонентов-это факториал строковых значений ASCII. т. е. s=»строка» -> s[0] (s[0] s[1]) (s[0] s[1] s[2]) … до лена(ов). Обычная сумма равна просто s[0] s[1] s[2]…
3. Это не фактор. В любом случае я не вижу никаких преимуществ с точки зрения хеширования. Он просто весит первый элемент больше, чем второй, и так далее.
Ответ №1:
Часто в нескольких английских словах используются одни и те же буквы, но в другом порядке. (Эти слова являются анаграммами друг друга). (Например, ангел / угол / подборка ).
Поскольку порядок не имеет значения при простом сложении, все анаграммы слова имеют одинаковую сумму. Поэтому использование простых сумм в качестве хэш-функции всегда приводит к столкновению, когда два разных ключа являются анаграммами друг друга.
Я никогда не слышал термина «хэш-код суммарной суммы компонентов», но, судя по вашему описанию, он совпадает со второй частью контрольной суммы Флетчера.
Использование хэш-функции, которая дает разные результаты для одних и тех же букв в другом порядке, например, для второй части контрольной суммы Флетчера (или всей контрольной суммы Флетчера), приводит к меньшему количеству коллизий в хэш-таблице.
Ответ №2:
В основном int(t) int(h) int(e) для хэш-кода то же самое, что eth или het. Вот почему хэш-код суммарной суммы компонентов лучше более индивидуален, так что != eht при использовании функции хэш-кода. Это уменьшает количество столкновений.