Re: A good hash algorithm

[Luiz Henrique de Figueiredo <lhf@...>]

>Now a comparison with existing Lua code.  In lstring.c (Lua v4.x) the hashing 
>algorithm for strings appears to be:
>
>  for (; l>=step; l-=step)
>    h = h ^ ((h<<5)+(h>>2)+(unsigned char)*(s++));
>
>Hmm ... this function has number "two character poles".  For example, let's say that 
>the table size is 256, and after some part of the string, the value of h is 1.  Then 
>inserting any even number of 'a' characters will map the hash value back to 1 
>(modulo 256.)

I haven't checked it, but have you taken into account that h is initialized
with the length of the string?

>So the code above is fast (for small strings)

It's fast for long strings as well, because in this case it does not look at all
the characters.

>My recommendation is that the Lua people at least consider using the Bob Jenkins 
>algorithm.

We're very satisfied with table performance in Lua. Of course, making it faster
would not hurt, *if* it can be done with more or less the same amount of code.
I don't know how large Jenkins's code is.

I propose that you try changing Lua to use Jenkins's algorithm and report the
results here. Roberto probably has testing code for table performance.

Thanks.
--lhf