Re: why lua table don't use prime number to hash

[Roberto Ierusalimschy <roberto@...>]

> I found that lua table use 2^n to hash key. normaly we use the prime number to prevent hash collision.
> now I use lua-5.3.4, and the code below will cost about 6 second because the hash table degenerates into a linked list
> so why lua table don't use prime number to hash?

Hashing with 2^n has the advantage that we can compute the modulo
with (x & (size - 1)) (see macro 'lmod'), which is much cheaper
than the '%' operator.

Nontheless, for several types (all types that use addresses as hashes
plus floats), Lua hashes with Mersenne numbers (2^n - 1), which are a
"good approximation" for primes. The choice between the two hashes is
based on how good we consider the initial hash (before the modulo).

Integer keys tend to be sequential, which gives sequential keys
after the modulo, which is good for hashes. So, for this quite
common case, it is not worth paying the price of '%'.

Of course, the worst-case for any hashing algorithm for unknown keys is
O(n), even with prime sizes.

Is yours a real problem? Do you have a program that does something
useful to someone that is having performance problems because of
this hashing?

-- Roberto