Minimalna funkcja hash dla C?
Nie mogę używać boost:hash, ponieważ muszę trzymać się C i nie mogę używać c++.
Ale muszę hashować dużą liczbę (10K do 100K) ciągów tokenów (długość od 5 do 40 bajtów), aby wyszukiwanie w nich było najszybsze.
MD5, SHA1 lub jakakolwiek funkcja Long hash wydaje się zbyt ciężka do prostego zadania, nie robię kryptografii. Plus jest koszt przechowywania i przetwarzania.
Dlatego moje pytanie:
Jaki może być najprostszy algorytm hashowy, który zapewni zapobieganie kolizjom w najbardziej praktycznych przypadkach.
Ile bitów użyć dla wartości hash? Rozwijam dla systemów 32 bitowych. Czy algorytm hashowania w Perlu / Pythonie również używa 32-bitowych skrótów? Czy muszę skoczyć do 64?
Jeśli chodzi o implementację tabel hashowych w popularnych językach skryptowych: czy implementacja sprawdza kolizje, czy mogę całkowicie tego uniknąć?
6 answers
Można znaleźć dobrą (i szybką) funkcję hash, oraz ciekawą lekturę, na http://www.azillionmonkeys.com/qed/hash.html
Jedynym czasem, kiedy nie powinieneś sprawdzać kolizji, jest użycie idealnego hasha -- dobrej, staromodnej tabeli wyszukiwania, takiej jak gperf .
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-13 14:04:18
Poniżej {[4] } znajduje się przegląd najbardziej znanych funkcji skrótu.
32 bity powinny działać dobrze.
Zawsze musisz sprawdzić kolizje, chyba że chcesz napisać zabawny hashtable :)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-09-05 20:06:16
Ogólna funkcja hash dla Tabela hash . Określa nie używaj do celów kryptograficznych , ale ponieważ określiłeś, że nie masz zamiaru tego robić, powinieneś być w porządku.
Zawiera Przegląd funkcji Hashowych do wypróbowania
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-13 19:30:42
Jeśli korzystasz z systemu 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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-13 16:05:02
Xxhash jest dość szybką i łatwą opcją. Prosty kod użyłby funkcji XXH32:
unsigned int XXH32 (const void* input, int len, unsigned int seed);
Jest to 32-bitowy hash. Ponieważ len jest int, dla większych danych więcej niż 2^31-1 bajtów należy użyć tych:
void* XXH32_init (unsigned int seed);
XXH_errorcode XXH32_update (void* state, const void* input, int len);
unsigned int XXH32_digest (void* state);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-10-22 09:22:29