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評論的上半部分，但我沒有在這個時候的口碑這樣做。）