Re: нормальная HASH функция для строк
От: Евгений Коробко  
Дата: 20.09.02 06:26
Оценка: 2 (1)
Здравствуйте the_moon, Вы писали:

...
TM>Так вот вопрос, есть ченибуть более надежное?

А чем вас не устраивает этот результат? Чего вы хотите от хэш-функции? Она как раз должна быть "абсолютно разрывной", т.е. выдавать совершенно разные значения для похожих строк.
Основная цель хеширования — разбить строки на непересекающиеся множества. Главное их требование — чтобы для любого набора строк они равномерно распределились по этим множествам.

создаётся массив, где индесксы — это хэш коды, а значения — списки строк с эти кодом. При этом время поиска в такой структуре = n*m, где n- колво возможных хэш-кодов, а m-кол-во элементов с таким же хэш-кодом.

Для простых случаем можно в качестве хэш-кода использовать первый символ в строке (как в словаре. Словарь — типичная отсортированная хэш-таблица). Всё зависит от задачи.

Вообще-то для строк (более-менее длинных) есть нормальный вариант : считаем сумму символов, а потом берем остаток от деления на кол-во необходимых хэш-кодов.
Евгений Коробко
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.