How to implement a map with unique keys that are themselves tables in Lua?

Question

Most languages offer some way to implements maps efficiently for ANY type of key either using an equivalence relation and a hashing function (with hash tables) or using an order relation (with trees).

However it seems Lua tables only offer this for strings. Specifically, if using a Lua table (implementing an "object" conceptually) as a key, it could only be looked up again with a reference to the same object, but not a new object with the same "contents".

This is kind of required to implement behavior similar to a database index or a cache for some value based on "unique" keys, at least without resorting to linear time lookup.

The only thing I could think of, is if the key object is made from fields f1,...,fn, we could make a bunch of nested maps and look it up like this T[f1][f2]...[fn] (at least if the fields are themselves integers or strings). This is kinda awful and breaks the intent of encapsulating f1,...,fn into an "object".

Any other ideas?

Answer 1

It looks like what you want may be something like this.

Otherwise a valid approach would be to serialize your key to a string in a deterministic way and use the result (or a hash of it) as the key.

Like SolarBear told you in a comment, you can then use methamethods to make it have the same interface as a regular table.