用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）
endprint（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.htmLua程序设计（第2版）中文 PDF http://www.linuxidc.com/Linux/2013-03/81833.htmLua程序设计（第二版）阅读笔记 http://www.linuxidc.com/Linux/2013-03/81834.htmNetBSD 将支持用 Lua 脚本开发内核组件 http://www.linuxidc.com/Linux/2013-02/79527.htmCentOS 编译安装 Lua LuaSocket http://www.linuxidc.com/Linux/2011-08/41105.htmLua 的详细介绍：请点这里
Lua 的下载地址：请点这里本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-05/102529.htm