Hash Functions

A comprehensive collection of hash functions, a hash visualiser and some test<br>results [see Mckenzie et al. Selecting a Hashing Algorithm, SP&E<br>20(2):209-224, Feb 1990] will be available someday. If you just want to<br>have a good hash function, and cannot wait, djb2 is one of the best<br>string hash functions i know. it has excellent distribution and speed on many<br>different sets of keys and table sizes. you are not likely to do better with<br>one of the "well known" functions such as PJW, K&R[1], etc.<br>Also see tpop pp. 126 for<br>graphing hash functions.

djb2

this algorithm (k=33) was first reported by dan bernstein many years<br>ago in comp.lang.c. another version of this algorithm (now favored<br>by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i];<br>the magic of number 33 (why it works better than many other<br>constants, prime or not) has never been adequately explained.

unsigned long<br>hash(unsigned char *str)<br>unsigned long hash = 5381;<br>int c;

while (c = *str++)<br>hash = ((hash

sdbm

this algorithm was created for sdbm (a public-domain reimplementation of ndbm)<br>database library. it was found to do well in scrambling bits, causing better<br>distribution of the keys and fewer splits. it also happens to be a good<br>general hashing function with good distribution. the actual function is<br>hash(i) = hash(i - 1) * 65599 + str[i]; what is included below is the<br>faster version used in gawk. [there is even a faster, duff-device version] the<br>magic prime constant 65599 (2^6 + 2^16 - 1) was picked out of thin air while experimenting with many<br>different constants. this is one of the<br>algorithms used in berkeley db (see<br>sleepycat) and elsewhere.

static unsigned long<br>sdbm(str)<br>unsigned char *str;<br>unsigned long hash = 0;<br>int c;

while (c = *str++)<br>hash = c + (hash

lose lose

This hash function appeared in K&R (1st ed) but at least the reader was<br>warned: "This is not the best possible algorithm, but it has the merit of<br>extreme simplicity." This is an understatement; It is a terrible<br>hashing algorithm, and it could have been much better without sacrificing its<br>simplicity. [see the second edition!] Many C programmers used to<br>use this function without actually testing it, or checking something like<br>Knuth's Sorting and Searching, so it got around. It used to show up mixed in<br>with otherwise respectable code, eg. cnews. sigh.]

unsigned long<br>hash(unsigned char *str)<br>unsigned int hash = 0;<br>int c;

while (c = *str++)<br>hash += c;

return hash;