Lua：如何在表格中查找表格（或对象）

Question

我想存储一个lua表格，其中的关键字是其他lua表格。我知道这是可能的，但我希望能够使用这些表的副本在表中查找。具体而言，我希望能够做到：

t = {} 
key = { a = "a" } 
t[key] = 4 
key2 = { a = "a" } 

，然后我希望能够查找：

t[key2] 

，并得到4

我知道，我可以把key放入一个字符串并放入表t。我也想过编写一个自定义哈希函数或者通过嵌套表来做这件事。有没有一种最好的方式来获得这种类型的功能？我还有什么其他选择？

Answer 1

在Lua中，分别创建了两个表被认为是“不同”。但是如果你创建一个表格，你可以将它分配给你想要的任何变量，当你比较它们时，Lua会告诉你它们是平等的。换句话说：

t = {} 
key = { a = "a" } 
t[key] = 4 
key2 = key 
... 
t[key2] -- returns 4 

所以，这是做你想做的简单，干净的方法。在某处存储key，因此您可以使用它恢复4。这也是非常快的。

如果你真的不想这样做......好吧，有一种方法。但它是低效率和丑陋的。

第一部分是制作一个函数来比较两个单独的表。如果两个表是“等价的”，它应该返回true，否则返回false。我们称之为等同的。它应该是这样的：

equivalent({a=1},{a=1})   -- true 
equivalent({a=1,b=2}, {a=1})  -- false 
equivalent({a={b=1}}, {a={b=2}}) -- false 

的功能必须是递归的，处理包含表本身的表。如果其中一个表格“包含”另一个表格，但具有更多元素，则它也不能被愚弄。我推出了这个实现;可能有更好的那里。

local function equivalent(a,b) 
    if type(a) ~= 'table' then return a == b end 

    local counta, countb = 0, 0 

    for k,va in pairs(a) do 
    if not equivalent(va, b[k]) then return false end 
    counta = counta + 1 
    end 

    for _,_ in pairs(b) do countb = countb + 1 end 

    return counta == countb 
end 

我不打算在这里解释这个函数。我希望它足够清楚它的作用。

拼图的另一部分是让t在比较键时使用equivalent函数。这可以通过仔细的metatable操作和一个额外的“存储”表来完成。

我们基本上将t转换为冒名顶替者。当我们的代码告诉它在一个键下存储一个值时，它不会自动保存它;相反，它将它提供给额外的表格（我们将称之为store）。当代码询问t的值时，它在store中搜索它，但使用equivalent函数获取它。

这是代码：

local function equivalent(a,b) 
... -- same code as before 
end 

local store = {} -- this is the table that stores the values 

t = setmetatable({}, { 
    __newindex = store, 
    __index = function(tbl, key) 
    for k,v in pairs(store) do 
     if equivalent(k,key) then return v end 
    end 
    end 
}) 

用例：

t[{a = 1}] = 4 

print(t[{a = 1}]) -- 4 
print(t[{a = 1, b = 2}]) -- nil 

Answer 2

我不确定你能做到这一点。您可以使用metatable为表定义相等性，但无法定义散列函数，并且我怀疑单独定义相等性会执行您所需的操作。你显然可以定义相等性，然后使用pairs()并自己比较键来遍历表，但是这会将O(1)查找变成O(n)。

Answer 3

这在Lua中是不可能的。如果你使用表格作为关键字，关键是表格的特定“实例”。即使您使用相同的内容制作不同的表格，实例也不同，因此它是不同的关键。

如果你想做这样的事情，你可以创建一种散列函数，它遍历表作为一个键（如果需要，甚至可以递归），并构造表内容的字符串表示。只要它对于不同的内容是不同的并且对于具有相同内容的表是相同的，它不需要是可读的。除了使用pairs()来遍历表，还需要将键插入表中并使用table.sort()对它们进行排序，因为pairs()以任意顺序返回它们，并且要求“相等”表的相同字符串。

一旦你建立这样的字符串，你可以使用它作为一个重点：

function hash(t) ... end 
t = {} 
key1 = { a = "a", b = "b" } 
t[hash(key1)] = 4 
key2 = { a = "a", b = "b" } 
print(t[hash(key2)]) -- should print "4" if the hash function works correctly 

在我看来，这一切都是建立索引的简单的任务太复杂，你可能要重新思考您希望使用表格副本进行索引。你为什么要这样的功能？

更新

如果你只需要使用短语的工作，我认为它们串联比创建这样的通用Hash函数容易。如果你需要它的短语序列，你实际上不需要遍历表格并对键进行排序，只需从每个短语中收集主要信息即可。你还需要使用一个辅助功能，它可以为你创造一个合适的键：

function pkey(...) 
    local n, args = select('#', ...), { ... } 
    for i=1,n do args[i] = args[i].value end -- extract your info here 
    return table.concat(args, ' ') -- space or other separator, such as ':'   
end 
tab[pkey(phrase1, phrase2, phrase3)] = "value" 

Answer 4

我不知道了很多关于语言处理，以及有关目标，你想你的程序达成，但如何收集这样的标记：使用一个嵌套的表结构，例如索引表只存储由第一个词组标记索引的表，然后每个子表包含由第二个词语标记索引的值...等...直到您到达短语最终标记将索引与他对应的数字值短语的ce。

也许会更清晰与为例，如果你有以下两个短语：

• 我喜欢香蕉。
• 我喜欢辣妹。

你的索引将具有以下结构：

index["I"] = { 
    ["like"] = { 
     ["banana"] = 1, 
     ["hot"] = { 
      ["chick"] = 1 
     } 
    }  
} 

这样，你就可以用一个遍历步数frenquencies，在你索引的同时计数出现次数，但正如我之前所说的，这取决于你的目标是什么，它意味着重新分割你的短语，以便通过你的索引找到出现的地方。

Answer 5

kikito的回答是不错的，但有一些缺陷：

• 如果执行t[{a=1}] = true两次，store将包含两个表（内存泄漏的哈希表的寿命）
• 修改值一次你已经存储它不起作用，你也不能删除它。尝试改变它会导致检索过程中返回您分配给该键的任何值。访问性能为O（n）（n为存储条目的数量，假设lua从表中检索到的值为O（1））;结合第一点，这个哈希表的性能将在使用

（另请注意，kikito的“等效”功能将导致无限循环，如果任何表具有循环引用。）

如果降级永远不需要更改/删除表中的任何信息，那么kikito的答案就足够了。否则，元表必须改变，这样__newindex确保该表不存在：

t = setmetatable({}, { 
    __newindex = function(tbl, key, value) 
     for k,v in pairs(store) do 
      if equivalent(k,key) then 
       tbl[k] = value 
       return 
      end 
     end 
     store[key] = value 
    end, 
    __index = function(tbl, key) 
     for k,v in pairs(store) do 
      if equivalent(k, key) then return v end 
     end 
    end 
}) 

正如你所说，一个完全不同的选择是编写一个自定义的散列函数。这里有一个哈希表，可以利用的是：

local function HashTable(Hash, Equals) 
    --Hash is an optional function that takes in any key and returns a key that lua can use (string or number). If you return false/nil, it will be assumed that you don't know how to hash that value. 
    -- If Hash is not provided, table-keys should have a GetHash function or a .Hash field 
    --Equals is an optional function that takes two keys and specify whether they are equal or not. This will be used when the same hash is returned from two keys. 
    -- If Equals is not provided, items should have a Equals function; items are in this case assumed to not be equal if they are different types. 
    local items = {} --Dict<hash, Dict<key, value>> 
    local function GetHash(item) 
     return Hash and Hash(item) or type(item) == "table" and (item.GetHash and item:GetHash() or item.Hash) or item 
    end 
    local function GetEquals(item1, item2) 
     if Equals then return Equals(item1, item2) end 
     local t1, t2 = type(item1), type(item2) 
     if t1 ~= t2 then return false end 
     if t1 == "table" and item1.Equals then 
      return item1:Equals(item2) 
     elseif t2 == "table" and item2.Equals then 
      return item2:Equals(item1) 
     end 
     return false 
    end 
    return setmetatable({}, { 
     __newindex = function(_, key, value) 
      local hash = GetHash(key) 
      local dict = items[hash] 
      if not dict then 
       if value ~= nil then --Only generate a table if it will be non-empty after assignment 
        items[hash] = {[key] = value} 
       end 
       return 
      end 
      for k, v in pairs(dict) do 
       if GetEquals(key, k) then --Found the entry; update it 
        dict[k] = value 
        if value == nil then --check to see if dict is empty 
         if next(dict) == nil then 
          items[hash] = nil 
         end 
        end 
        return 
       end 
      end 
      --This is a unique entry 
      dict[key] = value 
     end, 
     __index = function(_, key) 
      local hash = GetHash(key) 
      local dict = items[hash] 
      if not dict then return nil end 
      for k, v in pairs(dict) do 
       if GetEquals(key, k) then 
        return v 
       end 
      end 
     end 
    }) 
end 

用例：

local h = HashTable(
    function(t) return t.a or 0 end, --Hash 
    function(t1, t2) return t1.a == t2.a end) --Equals 
h[{a=1}] = 1 
print(h[{a=1}]) -- 1 
h[{a=1}] = 2 
print(h[{a=1}]) -- 2 
print(h[{a=1,b=2}]) -- 2 because Hash/Equals only look at 'a' 

当然，你会希望得到更好的散列/的Equals功能。

只要你的密钥的哈希值很少碰撞，这个类的性能应该是O（1）。

（注：我已经把这个答案，kikito评论的上半部分，但我没有在这个时候的口碑这样做。）