требуется 32битная хэш-функция для строк

F(const char *) -> unsigned int32_t.
главное - минимум коллизий( при количестве обрабатываемых строк от 100 000 и при их длине от 2 до 64 символов) , ну а уже потом быстродействие алгоритма.

 

Код (Text):

1. uint32_t fnv32( const void *buf, size_t len )
2. {
3.   const unsigned char *data = (const unsigned char *)(buf);
4.   uint32_t crc = 2166136261UL;
5.   while ( len-- )
6.     crc = ( crc * 16777619 ) ^ ( *data++ );
7.   return crc;
8. }

Подробнее тут: http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

 

Ага. спасибо.

 

вот такая штука одной из лучших считается.

Код (Text):

1. pow=1,hash=0
2. for(i=0; i<s.len(); ++i)
3. {
4.     hash+= s[i]*pow;
5.     pow *= p;
6. }
7. return hash;

 

Proteus
pow, p_pow, p, has, hash. Откуда вы это взяли?

 

опечатки... поправил... хотя там и так догадаться можно, как полином такой считать...
P число простое, можно небольшое брать двух-значное...

p.s.
можно так и воообще просто crc32 делать для строки, чем не идеальная сумма.. будет таблица в памяти на 256 чисел, а так код даже проще станет.. по крайней мере быстрее...
без таблицы даже можно так сделать, тоже на глазз набираю:

Код (Text):

1. dword CRC(const char *txt)
2. {
3.     dword hash=(dword)-1;
4.     while(*txt) {
5.         hash^=*txt++;
6.         for(n=0;n<8;n++) hash=(-(hash&1)&0xDB710641)^(hash>>1);
7.     }
8.  return hash;
9. }

 

Proteus

это вроде у тя FNV-1a hash.
Я пришел к выводу, что для надежности нужно пройтись 2 вариантами хеш функции по строке:
FNV-1

Код (Text):

1. hash = FNV_offset_basis
2.    for each octet_of_data to be hashed
3.     hash = hash * FNV_prime
4.     hash = hash XOR octet_of_data
5.    return hash

FNV-1a

Код (Text):

1. hash = FNV_offset_basis
2.    for each octet_of_data to be hashed
3.     hash = hash XOR octet_of_data
4.     hash = hash * FNV_prime
5.    return hash

 

Кстати вдогонку, позволяет ли openmp распараллелить эти 2 алго на 2 ядра.

 

хз =)

Позволяет. crc32 никак не распаралелишь. Чётные не чётные байты можно отельно во всех слуячаях считать, потом сшить результат. Можно отрезки побольше складывать, тут никаких сложностей не видно. Только толку тоже не заметно, такие простые операции ускорять... даже если будешь строки по 10 метров кидать, всё равно непонятно зачем (либо больше кеш промахиваться будет либо ещё что-то).. Проще разные строки на разных ядрах считать...

 

1 ядро - FNV-1 2 ядро - FNV-1a. При чтении строки они будут мешать друг другу? Как то слабо представляю этот момент.

 

здесь куча хэш-функций с исходниками и тестами http://amsoftware.narod.ru/algo.html

 

h**p://w*w.azillionmonkeys.com/qed/hash.html

 

Мда. Побегал я по ссылкам. Получается, Fnv совсем не айс по сравнению с crc32.
Кол-во коллизий у crc32 на всех тестах ровно, как и у хеш-функций автора кстати.
А вот fnv1 и fnv1a впадают в маразм при длинных строках тесты E и F. По видимому, изза инструкции умножения качество хеша постепенно падает.
По скорости Crc32 уступает, но ненамного. То есть, fnv1a fnv-1 можно смело выкидывать и использовать crc32.

 

Код (Text):

1. class CRC32 {
2.     dword table[256];
3. public:
4.     CRC32(dword polynom=0xDB710641); // 0xEDB88320 0x04C11DB7 0x1EDC6F41
5.     dword Calc(char*);
6. };
7.  
8. CRC32::CRC32(dword polynom) // Init - один раз на всю программу
9. {
10.     for(int n=0;n<256;n++) {
11.         dword c=n;
12.         for(int k=0;k<8;k++) c=c>>1^(-(int)(c&1)&polynom);
13.         table[n]=c;
14.     }
15. }
16.  
17. dword CRC32::Calc(char *str)
18. {
19.     dword hash=(dword)-1;
20.     while(*str) hash=(hash>>8)^table[(char)hash^*str++];
21.     return hash;
22. }

скорость проверять вообще не имеет смысла...=)

 

В FNv применяется умножение. Так что их можно сравнивать.
В CRC нет умножения но зато используется таблица(задействуется ОЗУ).

 

а как эти алгоритмы представить в виде макроса FASM?

 

как устроен fnv?

 

Охтыж! Как раз такую функцию искал.
edemko, благодарю что подняли тему =)

 

RtlHashString

 

Можно предположить, что существующие криптохеши дают минимальные коллизии