ФЫВАЫ (14.10.2010 12:37, просмотров: 1) ответил AlexandrY на Недавно натолкнулся на интересные варианты коротких хешей типа CRC - Adler32. У них немного другие свойства.
Коллизии Для сравнительной характеристики хэш-функции были выбраны следующие тестовые данные:
Американский словарь из проекта Ispell, 62 075 слов.
Русский словарь из проекта Ispell, 128 900 слов.
Список имен, извлеченный из всех библиотек в ОС linux (libc.a и прочие), 136 073 слов.
Общее количество после объедиения — 326 797 уникальных слов. При идеально равномерном распределении 32-битного хэша для достижения 50%-ной вероятности коллизии требуется 77 163 слова. Так что коллизии должны иметь место.
Для каждого из слов тестового набора было вычислено 32-битное значение хэш-функции и подсчитано количество коллизий. Для сравнения были взяты наиболее распространённые 32-битные функции.[1][2]
Алгоритм↓ Коллизии↓
rs 9
js 98
hashpjw 1315
bkdr 11
mabkdr 14
sdbm 14
djb 83
dek 308
ap 16
ly 9
rot13 7
faq6 14
OneAtTime 14
lookup3 9
crc32 13
MaHash4 4
MaHash8 7
MaHash11 10
MaHash5 7
fnv 10
fnv1 13
fnv1a 6
Murmur2 9
Murmur2a 18
SBOX 26
SuperFastHash 58
x31 85
x17 417
Fletcher 12950
Novak 16194
CrapWOW 73
Adler 53114
bp 254849
GoulburnHash 69
MaPrime 12