И решил ее протестировать, заполнял строчки мусором хешировал и искл одинаковый хэш для разных строк
за 10 минут на массиве из 100000 строчек вот такой вот ризультат.
-------1
The same hashes
{-К-cjMry^)Ъ$sФ*ПТЗТsnMFy|::_'(ШГLЭk{ЙДЙnfiСIJП6vl^ S$⌂9q<Х&b9wЫ!- 24615AD
ФUlpГToЗf, ЩO\W!Nm;FОDС~U#,p^c⌂SVБМD~UOЪYI]E69C*Ш_p*cИ0@УcqB'ТЙTTЕ 24615AD
-------2
The same hashes
$ЩdC<Лu)>gSЖШЫ}IМX0Тu@BmLФghАPqUG@ЮВЮ)T&&u/ZS{MKkhAЦ4BКjК)НS&IV|РЕ F26102BC
sz5QКC#$1Ю<Q{ЧRZxM8HЪKK |6lЪGА<Ш-dЧGAw#%l$_K\:4УkЕ?-ltoАЪu4,Q]GM<Л F26102BC
The same hashes
VРeaВUCI`>OdYГnzfЗ:yyС|+3_РB/j0ЕF%vgY_06QC$fyИzx]JqГ\3|mАC|[cК@h6У 4389B64B
zDK*tУЫЫrЙ ЬTБh;#]DhswdЬL%УJ1Н#XО>Э}ЫxС&OlqdT7J`+[zh*}} ЦHМW@ЩЫГ!Q 4389B64B
TM>И решил ее протестировать, заполнял строчки мусором хешировал и искл одинаковый хэш для разных строк TM>за 10 минут на массиве из 100000 строчек вот такой вот ризультат.
TM> TM>
TM>-------1
TM>The same hashes
TM>{-К-cjMry^)Ъ$sФ*ПТЗТsnMFy|::_'(ШГLЭk{ЙДЙnfiСIJП6vl^ S$⌂9q<Х&b9wЫ!- 24615AD
TM>ФUlpГToЗf, ЩO\W!Nm;FОDС~U#,p^c⌂SVБМD~UOЪYI]E69C*Ш_p*cИ0@УcqB'ТЙTTЕ 24615AD
TM>-------2
TM>The same hashes
TM>$ЩdC<Лu)>gSЖШЫ}IМX0Тu@BmLФghАPqUG@ЮВЮ)T&&u/ZS{MKkhAЦ4BКjК)НS&IV|РЕ F26102BC
TM>sz5QКC#$1Ю<Q{ЧRZxM8HЪKK |6lЪGА<Ш-dЧGAw#%l$_K\:4УkЕ?-ltoАЪu4,Q]GM<Л F26102BC
TM>The same hashes
VРeaВUCI`>>OdYГnzfЗ:yyС|+3_РB/j0ЕF%vgY_06QC$fyИzx]JqГ\3|mАC|[cК@h6У 4389B64B
TM>zDK*tУЫЫrЙ ЬTБh;#]DhswdЬL%УJ1Н#XО>Э}ЫxС&OlqdT7J`+[zh*}} ЦHМW@ЩЫГ!Q 4389B64B
TM>
TM>Так вот вопрос, есть ченибуть более надежное?
Есть. Архиваторы.
О какой надежности может идти речь в твоем примере, если точно известно что для любого значения хэша существует множество элементов которые ему соответствуют. Вот только осмысленных среди них должно быть оооочень мало. А мусору с одинаковым хешем наковырять конечно можно.....
Здравствуйте the_moon, Вы писали:
TM>Привет, хочу вот зделать поиск через хэши, нашел в интернете типа такой функции
Вот другой вариант (вырезано из куска рабочего кода)
template <>
inline size_t hash_function<string>::operator()(const string& key) const
{
static const size_t b = 27183;
size_t sum = 0;
size_t a = 31415;
for (size_t i = 0; i < key.length(); i++)
{
sum = a * sum + key[i];
a *= b;
}
return (sum % module);
}
Использует аналогичный rand() алгоритм генерации псевдо случайных чисел. Вообще, это стандартный метод, перемешивать псевдослучайными числами.
TM>И решил ее протестировать, заполнял строчки мусором хешировал и искл одинаковый хэш для разных строк
Тестируй
Только учти, для hash-функции важно не только распределение, но и скорость вычисления. Ты можешь придумать супер-надёжную функцию, которая будет просто долго работать. А вообще обсуждение хэш-функций и хэш-таблиц можно найти в любой хорошей книге алгоритмам, например Т.Кормен и др, "Алгоритмы, построение и анализ" (в народе "ослы" )
... TM>Так вот вопрос, есть ченибуть более надежное?
А чем вас не устраивает этот результат? Чего вы хотите от хэш-функции? Она как раз должна быть "абсолютно разрывной", т.е. выдавать совершенно разные значения для похожих строк.
Основная цель хеширования — разбить строки на непересекающиеся множества. Главное их требование — чтобы для любого набора строк они равномерно распределились по этим множествам.
создаётся массив, где индесксы — это хэш коды, а значения — списки строк с эти кодом. При этом время поиска в такой структуре = n*m, где n- колво возможных хэш-кодов, а m-кол-во элементов с таким же хэш-кодом.
Для простых случаем можно в качестве хэш-кода использовать первый символ в строке (как в словаре. Словарь — типичная отсортированная хэш-таблица). Всё зависит от задачи.
Вообще-то для строк (более-менее длинных) есть нормальный вариант : считаем сумму символов, а потом берем остаток от деления на кол-во необходимых хэш-кодов.
Здравствуйте the_moon, Вы писали:
TM>Привет, хочу вот зделать поиск через хэши, нашел в интернете типа такой функции
TM>Так вот вопрос, есть ченибуть более надежное?
Поищи в том же интернете на слово jenkins. Заодно почитай, что рядом написано.
Здравствуйте Евгений Коробко, Вы писали:
ЕК>Здравствуйте the_moon, Вы писали:
ЕК>... TM>>Так вот вопрос, есть ченибуть более надежное?
ЕК>А чем вас не устраивает этот результат? Чего вы хотите от хэш-функции? Она как раз должна быть "абсолютно разрывной", т.е. выдавать совершенно разные значения для похожих строк. ЕК>Основная цель хеширования — разбить строки на непересекающиеся множества. Главное их требование — чтобы для любого набора строк они равномерно распределились по этим множествам.
Спасибо — уговорили, не я просто незнаком с темой, но надо
чтобы избежать предварительного сканирования строки в ф-ции strlen.
2. Очень сомнительна необходимость использовать ф-цию Final, которая всего-навсего делает побитовый NOT и изменяет порядок байт в CRC на противоположный.
Тоже самое относится к XOR-у в GetCrc.
Таким образом можно переписать ф-цию GetHash следующим образом:
3. Неплохо реализовать все функции в header-е как inline, т.к. увеличение размер exe-шника за счет раскопирования таблицы по модулям, компенсируется преумуществами инлайна.
P.S. В принципе возможна и грамотная реализация без раскопирования таблицы за счет небольшого "утяжеления" констркутора.
Здравствуйте Евгений Коробко, Вы писали:
ЕК>Здравствуйте the_moon, Вы писали:
ЕК>... TM>>Так вот вопрос, есть ченибуть более надежное?
ЕК>А чем вас не устраивает этот результат? Чего вы хотите от хэш-функции? Она как раз должна быть "абсолютно разрывной", т.е. выдавать совершенно разные значения для похожих строк. ЕК>Основная цель хеширования — разбить строки на непересекающиеся множества. Главное их требование — чтобы для любого набора строк они равномерно распределились по этим множествам.
По-моему, если я правильно понял, что
-------2
это номера проходов, то одна-две коллизии на 100000 строк при ~4млрд. потенциальных значений хэша — это плохой результат.
Приведенный вами алгоритм применяется в java.lang.String (jdk 1.3) только с 31 вместо 131. Видимо люди из сана не нашли ничего более подходящего для общего случая.
А насчет Crc32 вообще очень интересный вопрос. По сложности алгоритма они одинаковы. Однако ведь не используют же crc в качестве хеша?! Было бы интересно узнать причины.
TM>>Так вот вопрос, есть ченибуть более надежное?
adb>Приведенный вами алгоритм применяется в java.lang.String (jdk 1.3) только с 31 вместо 131. Видимо люди из сана не нашли ничего более подходящего для общего случая.
adb>А насчет Crc32 вообще очень интересный вопрос. По сложности алгоритма они одинаковы. Однако ведь не используют же crc в качестве хеша?! Было бы интересно узнать причины.
Я как-то изучал этот вопрос.
1. 31*Hash == Hash<<5-Hash (java) или 33*Hash == Hash<<5+Hash (MFC), все-таки несколько попроще чем CRC, т.к в теле цикла идет только одно (причем последовательное) обращение к памяти (взять следующий символ), остальное наверняка ляжет в регистры. Да и формулы понагляднее
2. И это я думаю главное, используя данную формулу мы можем не задумываться ни о разрядности int(long), ни о разрядности char (например, unicode). При этом проигрыш по сравнению с CRC из-за небольшого увеличения числа коллизий будет минимален.