Re: A good hash algorithm

[RLake@...]

> I ran across a paper that found that moving the last accessed entry to
> the front of the bucket significantly improved performance for typical
> usage cases. Does lua already use this trick?

That was a good question. I checked the v5 code, and as far as I can see,
the answer is no.

However, Lua hashes are not likely to contain long chains (or buckets)
because the key-val pairs are stored inside the hash array itself; a clever
trick is used which allows hash-tables to get quite full without impeding
performance. (This is part of the secret of Lua's success.) It is quite
common for hash lookups to succeed or fail on the first probe.

The only reason I know this stuff is that I was curious about how Lua
managed to do hash tables so fast. It's a really nice job. Congratulations,
guys!