lua-users home
lua-l archive

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

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
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?