[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: A good hash algorithm
- From: Luiz Henrique de Figueiredo <lhf@...>
- Date: Wed, 3 Jul 2002 11:05:01 -0300
>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
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
>My recommendation is that the Lua people at least consider using the Bob Jenkins
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.