кстати, дарю полезное. быстрая, маленькая и качественная хэш-функция, которая не даёт дубликатов на штуках типа имён файлов. мне тут понадобилось в форт-системе для «include-once». можно, конечно, и полностью имена хранить, но жаба душит же. прогнал на базе mlocate с тремя миллионами уникальных имён (имена без путей, в смысле) — коллизий нет.
сердце и печень — one-at-a-time Боба Дженкинса. лучшая хэш-функция в классе «32 бита на внутреннее состояние», и вообще очень-очень хорошая. в отличие от многих других (типа того же мурмура) — буквально три асм-инструкции, и никакого умножения в цикле. я к ней добавил простенькую контрольную сумму, которая обеспечивает уникальность. без контрольной суммы на трёх миллионах имён у нас было ~4100 коллизий (что само по себе впечатляет), с контрольной суммой — 0.
на сишечке, потому что мне надо было на сишечке, но транслировать на кп проблем не составит.
hash1p на входе инициализируется любой константой, хоть нулём. это ни на что не влияет. я обычно беру 0x29a, потому что кросивое.
на выходе имеем уникальный 64-битный идентификатор. плюс *hash1p — качественный хэш, который отлично подходит для хэш-табличек. имейте в виду, что у *hash2p аваланч совершенно никакой, так что именно как полноценную 64-битную хэш-функцию это применять нельзя.
если вам где-то надо списки имён файлов хранить/сличать, то их вполне можно заменить на кучку лонгинтов. вероятность коллизий настолько статистически мала, что её можно не принимать во внимание. конечно, какой-нибудь криптографический хэш справится намного лучше, но сложность реализации (да и скорость)…
Код:
static void joaat2x (const void *buf, size_t len, uint32_t *hash1p, uint32_t *hash2p) {
uint32_t hash1 = *hash1p, hash2 = 0;
const uint8_t *s = (const uint8_t *)buf;
while (len--) {
hash1 += *s;
hash1 += hash1<<10;
hash1 ^= hash1>>6;
hash2 -= hash1;
s += 1u;
}
hash1 += hash1<<3;
hash1 ^= hash1>>11;
hash1 += hash1<<15;
hash2 -= hash1;
*hash1p = hash1;
*hash2p = hash2;
}
p.s.: с идентификаторами во всяких таблицах имён справится нисколько не хуже.