Consider the case of a hash-table with 20 keys, each of which is a
string
of a million bytes. A "really good" hash algorithm would probably
succeed
in creating a unique hash for each string, but in O(1,000,000) time. The
Lua hash algorithm might hash all of them onto the same value; the cost
of
that would be that the table lookup would be essentially linear, or
O(20).
In practice, scanning 20 table entries on each lookup is probably faster
than computing 20 hashes of a million bytes, unless there are a lot of
lookups.
