lua-users home
lua-l archive

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

Lars Doelle wrote:
> local basekeys = {}
> setmetatable( basekeys, { __mode = "k" }) -- ephemeron
> local function pair_key(k,v)
>   if not basekeys[k] then basekeys[k] = math.random() end
>   if not basekeys[v] then basekeys[v] = math.random() end
>   return (907+basekeys[k])*(103 + basekeys[v])
> end
> local function table_key(tbl)
>   local hash_key = 401
>   for k,v in pairs(tbl) do
>     hash_key = hash_key + pair_key(k,v)
>   end
>   return hash_key
> end

Beware of floating point non-associativity here. (k, v) pairs can come
in different order depending on the table's usage history. Combined with
non-associativity of addition, this can theoretically result in
different hashes for identical tables. Of course, this problem is not
likely to occur, but I wouldn't use such solution in a critical part of

You should probably use math.random(N) with some integer N instead of
math.random() and carry out addition by some integer modulo instead of
just hash_key = hash_key + pair_key(k,v).