хеш для строк

Нужен алгоритм для расчета хеша строки такой, чтобы удаление/добавление символа мало изменяла хеш.
Например, хеши для строк: abcdefgh abdefgh abcdefqgh должны быть похожи.

Куда копать?

 

Алгоритм Цезаря. :P

 

в сторону простого суммирования байт

 

На выходе должно быть число.

Сорри, не указал сразу - нужно избегать коллизий с другими строками.

 

Rodin
Ну так и сделай себе два хеша. Первый - MD5, второй простым суммированием.

 

я не гуру криптографии, но по-моему ты требуешь взаимоисключающие понятия

 

MSoft

согласен.

Booster

CRC32 имхо лучше для этой цели. И насколько я помню афтор требовал число.

 

SPA
>CRC32 имхо лучше для этой цели.
Не суть, пусчай ТС выберет что его душе угодно.

>И насколько я помню афтор требовал число.
Вообще-то в компе всё представлено числами.

 

Booster
Я не заканчивал школу шаманства, но я думаю что афтор имел в виду int32 с вероятностью 90%. Rodin не так ли?

 

SPA
Я ничего против не имею. CRC32 так CRC32. ^)

 

В общем вот: http://www.insidepro.com/hashes.php?lang=eng
Посмотри и выбири подходящий.

 

вот пример реализации алгоритма CRC32 на C:

Код (Text):

1. unsigned long Crc32(const char *buf)
2. {
3.     // generate CRC32 hash
4.    
5.     unsigned long len;
6.     unsigned long crc_table[256];
7.     unsigned long crc;
8.    
9.     len = strlen(buf);
10.  
11.     for (int i = 0; i < 256; i++)
12.     {
13.         crc = i;
14.         for (int j = 0; j < 8; j++)
15.             crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
16.  
17.         crc_table[i] = crc;
18.     };
19.  
20.     crc = 0xFFFFFFFFUL;
21.  
22.     while (len--)
23.         crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);
24.  
25.     return crc ^ 0xFFFFFFFFUL;
26. }