用Lua實現插入、刪除和查找時間復雜度為O(1)的集合

利用下面代碼可以定義一個集合S，對該集合所有的操作，比如插入、刪除元素和查找元素都是O(1)，代碼如下：

function newset()
    local reverse = {} --以數據為key，數據在set中的位置為value
    local set = {} --一個數組，其中的value就是要管理的數據
    return setmetatable(set,{__index = {
          insert = function(set,value)
              if not reverse[value] then
                    table.insert(set,value)
                    reverse[value] = table.getn(set)
              end
          end,

          remove = function(set,value)
              local index = reverse[value]
              if index then
                    reverse[value] = nil
                    local top = table.remove(set) --刪除數組中最後一個元素
                    if top ~= value then
                        --若不是要刪除的值，則替換它
                        reverse[top] = index
                        set[index] = top
                    end
              end
          end,

          find = function(set,value)
              local index = reverse[value]
              return (index and true or false)
          end,
    }})
end

local s = newset()
s:insert("hi0")
s:insert("hi1")

for _,Value in ipairs(s) do
    print(Value)
end

print(s:find("hi0"))
s:remove("hi0")
print(s:find("hi0"))

--[[--output--
hi0
hi1
true
false
--]]

上面set之所以能做到插入、刪除和查找為O(1)，首先是lua中table實現的保證，另外一個是利用了一個額外的數組reverse，來保存數組s中每個數據在s中的位置，相當於以空間換時間。

ps:上面代碼是對luasocket源碼samples/tinyirc.lua中代碼的改寫。

Lua 語言 15 分鐘快速入門 http://www.linuxidc.com/Linux/2013-06/86582.htm

Lua程序設計（第2版）中文 PDF http://www.linuxidc.com/Linux/2013-03/81833.htm

Lua程序設計（第二版）閱讀筆記 http://www.linuxidc.com/Linux/2013-03/81834.htm

NetBSD 將支持用 Lua 腳本開發內核組件 http://www.linuxidc.com/Linux/2013-02/79527.htm

CentOS 編譯安裝 Lua LuaSocket http://www.linuxidc.com/Linux/2011-08/41105.htm

Lua 的詳細介紹：請點這裡
Lua 的下載地址：請點這裡