нормальная HASH функция для строк
От: the_moon  
Дата: 20.09.02 05:59
Оценка:
Привет, хочу вот зделать поиск через хэши, нашел в интернете типа такой функции



unsigned long mHash( const char* string )
{
    unsigned long Hash = 0;
    for( Hash = 0; *string; string++ ) Hash = (131 * Hash + *string);
    return Hash;
}


И решил ее протестировать, заполнял строчки мусором хешировал и искл одинаковый хэш для разных строк
за 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


Так вот вопрос, есть ченибуть более надежное?
KOPOTbILLIKA KPbIC
Re: нормальная HASH функция для строк
От: ToShA_2K Россия  
Дата: 20.09.02 06:10
Оценка:
Здравствуйте the_moon, Вы писали:

TM>Привет, хочу вот зделать поиск через хэши, нашел в интернете типа такой функции


TM>


TM>
TM>unsigned long mHash( const char* string )
TM>{
TM>    unsigned long Hash = 0;
TM>    for( Hash = 0; *string; string++ ) Hash = (131 * Hash + *string);
TM>    return Hash;
TM>}
TM>


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>Так вот вопрос, есть ченибуть более надежное?


Есть. Архиваторы.

О какой надежности может идти речь в твоем примере, если точно известно что для любого значения хэша существует множество элементов которые ему соответствуют. Вот только осмысленных среди них должно быть оооочень мало. А мусору с одинаковым хешем наковырять конечно можно.....
Re: нормальная HASH функция для строк
От: orangy Россия
Дата: 20.09.02 06:11
Оценка:
Здравствуйте 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-функции важно не только распределение, но и скорость вычисления. Ты можешь придумать супер-надёжную функцию, которая будет просто долго работать. А вообще обсуждение хэш-функций и хэш-таблиц можно найти в любой хорошей книге алгоритмам, например Т.Кормен и др, "Алгоритмы, построение и анализ" (в народе "ослы" )
... << J 1.0 alpha 4 >>
"Develop with pleasure!"
Re: нормальная HASH функция для строк
От: Flamer Кипр http://users.livejournal.com/_flamer_/
Дата: 20.09.02 06:12
Оценка:
Здравствуйте the_moon, Вы писали:

TM>Привет, хочу вот зделать поиск через хэши, нашел в интернете типа такой функции


TM>


TM>
TM>unsigned long mHash( const char* string )
TM>{
TM>    unsigned long Hash = 0;
TM>    for( Hash = 0; *string; string++ ) Hash = (131 * Hash + *string);
TM>    return Hash;
TM>}
TM>



[покоцано]

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


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

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

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

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

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

Вообще-то для строк (более-менее длинных) есть нормальный вариант : считаем сумму символов, а потом берем остаток от деления на кол-во необходимых хэш-кодов.
Евгений Коробко
Re: нормальная HASH функция для строк
От: Alex Fedotov США  
Дата: 20.09.02 06:28
Оценка: 3 (1)
Здравствуйте the_moon, Вы писали:

TM>Привет, хочу вот зделать поиск через хэши, нашел в интернете типа такой функции


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


Поищи в том же интернете на слово jenkins. Заодно почитай, что рядом написано.
-- Alex Fedotov
Re[2]: нормальная HASH функция для строк
От: the_moon  
Дата: 20.09.02 07:48
Оценка:
Здравствуйте Евгений Коробко, Вы писали:

ЕК>Здравствуйте the_moon, Вы писали:


ЕК>...

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

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

ЕК>Основная цель хеширования — разбить строки на непересекающиеся множества. Главное их требование — чтобы для любого набора строк они равномерно распределились по этим множествам.

Спасибо — уговорили, не я просто незнаком с темой, но надо
KOPOTbILLIKA KPbIC
Re: нормальная HASH функция для строк
От: MichaelP  
Дата: 20.09.02 08:56
Оценка:
Здравствуйте the_moon, Вы писали:

TM>Привет, хочу вот зделать поиск через хэши, нашел в интернете типа такой функции


TM>


TM>
TM>unsigned long mHash( const char* string )
TM>{
TM>    unsigned long Hash = 0;
TM>    for( Hash = 0; *string; string++ ) Hash = (131 * Hash + *string);
TM>    return Hash;
TM>}
TM>

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

Где-то видел результаты тестов из которых следовало, что CRC32 дает наименьшее кол-во коллизий.

Т.ч. присоединяюсь к Flamer-у.

Правда, есть несколько замечаний по указанному им коду.




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

ЕК>Здравствуйте the_moon, Вы писали:


ЕК>...

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

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

ЕК>Основная цель хеширования — разбить строки на непересекающиеся множества. Главное их требование — чтобы для любого набора строк они равномерно распределились по этим множествам.

По-моему, если я правильно понял, что
-------2
это номера проходов, то одна-две коллизии на 100000 строк при ~4млрд. потенциальных значений хэша — это плохой результат.
Re: нормальная HASH функция для строк
От: adb Россия  
Дата: 30.09.02 04:38
Оценка:
Здравствуйте the_moon, Вы писали:

TM>
TM>unsigned long mHash( const char* string )
TM>{
TM>    unsigned long Hash = 0;
TM>    for( Hash = 0; *string; string++ ) Hash = (131 * Hash + *string);
TM>    return Hash;
TM>}
TM>


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


Приведенный вами алгоритм применяется в java.lang.String (jdk 1.3) только с 31 вместо 131. Видимо люди из сана не нашли ничего более подходящего для общего случая.

А насчет Crc32 вообще очень интересный вопрос. По сложности алгоритма они одинаковы. Однако ведь не используют же crc в качестве хеша?! Было бы интересно узнать причины.
Re[2]: нормальная HASH функция для строк
От: MichaelP  
Дата: 30.09.02 07:00
Оценка:
Здравствуйте adb, Вы писали:

adb>Здравствуйте the_moon, Вы писали:


TM>>
TM>>unsigned long mHash( const char* string )
TM>>{
TM>>    unsigned long Hash = 0;
TM>>    for( Hash = 0; *string; string++ ) Hash = (131 * Hash + *string);
TM>>    return Hash;
TM>>}
TM>>


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 из-за небольшого увеличения числа коллизий будет минимален.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.