[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: A good hash algorithm
- From: Luiz Henrique de Figueiredo <lhf@...>
- Date: Sun, 14 Jul 2002 11:20:53 -0300
>variations on a simple old algorithm[1] turn out to have
>similar runtime performance, and significantly lower collision rates than
>Jenkins's
>
>[1] djb2 algorithm: http://www.cs.yorku.ca/~oz/hash.html
Lua's hash function for strings is similar to djb2.
The core of djb2 is
h = ((h << 5) + h) + c
The core of Lua's function
h = h ^ ((h<<5)+(h>>2)+c)
Of course, being similar does not guarantee anything about performance, but
we're very satisfied with the overall performance (code size and speed) of
Lua's hashing.
--lhf