Re: tables as keys

["Alex Davies" <alex.mania@...>]

There would be no efficient way to do it. Two completely (contents) equal 
tables can have quite different hash and array sizes and layouts based on 
the order things were inserted in to them, meaning that you couldn't simple 
compare the raw contents. Serializing them to a string would be one 
(extremely slow) way, as you say, involving a complete traversal of a data 
structure who's size is only bounded by memory. Consider too, that the order 
of traversal of two equal tables is not guaranteed (as the size of their 
hash tables may be different). So you'd probably have to sort the hash 
portion.

There has been a few proposals of a __hash metamethod, so that you can 
return an alternative object, say a string or number to hash instead of the 
table, and to resolve collisions __eq would be called on each colliding 
table. (Your proposal turned upside down). This opens a whole new class of 
problems though, eg whenever a table is resized it needs to call the __hash 
of all tables it holds. This opens a yet another way for errors to be thrown 
from a simple settable, and then there's the additional overhead to 
consider.

Finally, there's the problem of tables getting -lost- inside a table. Eg

local bar = setmetatable({ greeting = "hello" }, { __hash = 
customhashfunction })
local foo = { [bar] = true }
assert(foo[bar]) -- passes
bar.greeting = "Bonjour"
assert(foo[bar]) -- sometimes will be able to find bar, othertimes it'll 
randomly fail!
assert(next(foo) == bar) -- bar still exists in the table though, whether it 
can be indexed or not

That's a pretty major flaw imo. All those problems still all exist for 
"makeASpecialTable", yet I think I'd prefer __hash despite not particularly 
liking either.

- Alex

----- Original Message ----- 
From: Matthew Armstrong
To: lua@bazar2.conectiva.com.br
Sent: Tuesday, March 11, 2008 11:48 AM
Subject: tables as keys

Normally, if I index a table with another table as a key, the keying is done 
by the table key's instance (essentially, its address).
What I want is for the keying to be defined by the table key's _contents_ 
(the structure of the table).

For instance, I want to do something like:

t = makeASpecialTable()
t[{a=1, b=2}] = 42
assert(t[{a=1, b=2}] == 42)

One way to solve this problem is to serialize the table key into string. 
This works, but probably isn't all that efficient ... or maybe making the 
generated string smaller would help?

Has anyone dealt with this problem before?