lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Tuesday, June 18, 2002, at 12:51  PM, wrote:
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

But don't you still need to do a O(1,000,000) string compare on potentially each of the 20 strings?