![]() |
![]() |
![]() | ||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
Содержание
Hash Function Efficiency(This article is also available in Russian) In article of Arash Partow "General Purpose Hash Function Algorithms" several 32-bit algorithms are reviewed:
Another five variants:
Here are the C sources. Test 1To measure the efficiency of hash functions I prepared the following test data:
Total volume after merging is 326797 different words. For every word a 32-bit hash value was computed, and counted a number of collisions.
A list of collisions for rs, bkdr, sdbm, ap, ly, rot13, faq6, lookup3 and crc32 is available here. Algorithms with minimal collisions:
Results are presented on picture. Two outsiders — pjw and dek — exceed the limits of Y axis. Test 2In previous test, all data had MSB unchanged. For the second test another data set was selected:
Total volume after merging is 310595 different words. Algorithms js, pjw, djb и dek were excluded from testing.
Algorithms with minimal collisions:
Results are presented on picture. |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
![]() |