Minimalna funkcja skrótu dla C?

Question

Nie mogę użyć boost: hash, ponieważ muszę trzymać się C i nie mogę używać C++.

Ale potrzebuję dużej liczby (od 10K do 100k) znaków tokenów (długość od 5 do 40 bajtów), aby wyszukiwanie w nich było najszybsze.

MD5, SHA1 lub jakakolwiek długa funkcja hash wydaje się zbyt ciężka dla prostego zadania, nie robię kryptografii. Plus jest koszt przechowywania i przetwarzania.

Stąd moje pytanie:

1. Co może być najprostszy algorytm mieszania, która zapewni zapobiegania kolizji w większości praktycznych przypadków.

2. Ile bitów użyć do wartości mieszania? Pracuję dla systemów 32-bitowych. Czy algorytm mieszania w Perlu/Pythonie również używa 32-bitowych skrótów? Czy muszę przeskoczyć do 64?

3. Jeśli chodzi o implementację tabel mieszania w popularnych językach skryptowych: czy sprawdzanie implementacji powoduje kolizje, czy mogę omijać tę część w ogóle?

Answer 1

można znaleźć dobry (i szybki) funkcji skrótu i ​​ciekawe brzmienie, w http://www.azillionmonkeys.com/qed/hash.html

Jedynym przypadkiem, w którym nie należy sprawdzać kolizji, jest użycie idealnego skrótu - dobrego staromodnego tabeli odnośników, np. gperf.

Answer 2

Ogólna funkcja skrótu dla hash table lookup. Określa ona NIE używać do celów kryptograficznych, ale ponieważ określiłeś, że nie masz na to zamiaru, powinieneś być w porządku.

on wliczony jest sondażu funkcje skrótu wypróbować

Answer 3

1. Here jest ładny przegląd najważniejszych znanych funkcji skrótu.

2. 32bit powinien działać dobrze.

3. Zawsze trzeba sprawdzić kolizje, chyba że chcesz napisać zabawną hashtable :)

Answer 4

Wypróbuj Adler32 dla długich ciągów lub Murmur2 dla krótkich łańcuchów.

Answer 5

Jeśli korzystasz z systemu podobnego do posix i trzymasz się zwykłego C, po prostu użyłbym tego, co system ma już do zaoferowania. man 3 hcreate oferuje wszystkie szczegóły lub można znaleźć wersję online tutaj http://linux.die.net/man/3/hcreate

Answer 6

xxhash to dość szybka i łatwa opcja. Prosty kod będzie używać XXH32 funkcję:

unsigned int XXH32 (const void* input, int len, unsigned int seed); 

To jest 32-bitowy hash.Od len jest int, dla większych danych ponad 2^31-1 bajtów z nich korzystać:

void*   XXH32_init (unsigned int seed); 
XXH_errorcode XXH32_update (void* state, const void* input, int len); 
unsigned int XXH32_digest (void* state);