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:

rs — simple hash function from Robert Sedgwicks book 'Algorithms in C'
js — bitwise hash function by Justin Sobel
pjw — algorithm based on work by Peter J. Weinberger
bkdr — hash function from Brian Kernighan and Dennis Ritchie's book 'The C Programming Language'
sdbm — algorithm of choice used in SDBM project
djb — algorithm produced by Professor Daniel J. Bernstein
dek — algorithm proposed by Donald E. Knuth in 'The Art Of Computer Programming'
ap — algorithm produced by Arash Partow

Another five variants:

faq6 — number 6 from FAQ by Bob Jenkins
lookup3 — author Bob Jenkins
ly — proposed by Leonid Yuriev (congruential generator)
rot13 — simple algorithm with circular shift, by Serge Vakulenko
crc32 — standard checksum with polynom x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1

Test 1

To measure the efficiency of hash functions I prepared the following test data:

American dictionary from Ispell project, 62075 words.
Russian dictionary from Ispell project, 128900 words.
A list of symbols, extracted from all libs on my linux workstation (libc.a and others), 136073 words.

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.

In 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.