用Lua实现插入、删除和查找时间复杂度为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
--]]