Use a table's content as a key

Question

Is there an easy way to create a dictionary-like collection, i.e.

1. Tables can be used as keys
2. Tables with the same content are considered equivalent (instead of the default pointer comparison)

e.g. after

t = createCustomTable()
k1 = {'a','b','c'}
k2 = {'a','b','c'}
t[k1] = true

t[k2] should evaluate to true.
Also t itself should be usable as a key in the same way.

Is there any way to do this without

1. Re-implementing hash tables
2. Converting k1 and k2 to strings? (this is what I am currently doing.)

Answer 1

Serializing the two tables into strings is the solution Roberto Ierusalimschy (chief architect of Lua) recommends for indexing by content in Programming in Lua 2nd Edition.

If all of your key tables are arrays of strings (with no embedded nulls), this can be done quickly with table.concat(t,'\0'). (Obviously, your table will need to be sorted if you want index-independent identity.)

Answer 2

If the tables to be used as keys are fixed and their contents do not change you could build a SHA2 digest on demand in a newindex metamethod for t and use the digest as the real key. The digest would be cached in another table indexed by the real tables.

Answer 3

You can implement and set the __eq method in the metatable of the two tables.

k1 = {'a','b','c'}
k2 = {'a','b','c'}
mt1={__eq=function(a,b)
   for k,v in pairs(a) do
      if b[k]~=v then return false end
   end
   for k,v in pairs(b) do
      if a[k]~=v then return false end
   end
   return true
end
}
setmetatable(k1,mt1)
setmetatable(k2,mt1)

assert(k1==k2,"Table comparison failed")

function newDict(orig)
    if orig then
        return orig
    else
        local mt2={}
        local lookup ={} -- lookup table as upvalue to the metamethods
        mt2.__newindex = function(t,k,v) -- Registering a new table
            if type(k)~="table" then return end
            if v then   -- v ~= false
                local found
                for idx,val in pairs(lookup) do
                    if k==val then
                        found=1
                        break
                    end -- If already seen, skip.
                end
                if not found then
                    lookup[#lookup+1]=k -- not seen before, add
                end 
            else -- v == false or nil
                local to_erase
                for idx,val in pairs(lookup) do -- Assume there is only one match in the dict.
                    if k==val then
                        lookup[k]=nil
                        break
                    end --don't continue after this, next will be confused.
                end
            end         
        end

        mt2.__index = function(t,k) -- looking up a table
            for idx,val in pairs(lookup) do
                if k==val then 
                    return true
                end
            end
            return false
        end
        return setmetatable({},mt2)
    end
end

t1 = newDict()
t2 = newDict()

k1={1,2,3}
k2={"a"}
k3={"z","d","f"}

k1b={1,2,3}
k2b={"a"}
k3b={"z","d","f"}

setmetatable(k1,mt1)
setmetatable(k2,mt1)
setmetatable(k3,mt1)

setmetatable(k1b,mt1)
setmetatable(k2b,mt1)
setmetatable(k3b,mt1)

-- Test multiple entries in 1 dict
t1[k1]=true
t1[k2]=true
assert(t1[k1b],"t1[k1b] did not return true")
assert(t1[k2b],"t1[k2b] did not return true")
-- Test confusion between 2 dicts
t2[k3]=true
assert(not t1[k3b],"t1[k3b] did return true")
assert(not t2[k1b],"t2[k1b] did return true")

The comparison can be implemented faster because now common entries are checked twice, but you get the point.

I can't comment on performance as it does use metatable lookups rather heavily, and needs to go through all tables on each comparison or assignment, but since you don't want to hash the tables or convert them to strings (aka serialize them) it's the only way. If I were you I'd seriously consider checking against a serialization of the tables instead of the above approach though.