lua 的 table 处理

lua 的整体效率是很高的，其中，它的 table 实现的很巧妙为这个效率贡献很大。

lua 的 table 充当了数组和映射表的双重功能，所以在实现时就考虑了这些，让 table 在做数组使用时尽量少效率惩罚。

lua 是这样做的。它把一个 table 分成数组段和 hash 段两个部分。数字 key 一般放在数组段中，没有初始化过的 key 值全部设置为 nil 。当数字 key 过于离散的时候，部分较大的数字 key 会被移到 hash段中去。这个分割线是以数组段的利用率不低于 50% 为准。 0 和 负数做 key 时是肯定放在 hash 段中的。

string 和 number 都放在一起做 hash ，分别有各自的算法，但是 hash 的结果都在一个数值段中。hash 段采用闭散列方法，即，所有的值都存在于表中。如果hash 发生碰撞，额外的数据记在空闲槽位里，而不额外分配空间存放。当整个个表放满后，hash 段会扩大，所有段内的数据将被重新 hash ，重新 hash 后，冲突将大大减少。

这种 table 的实现策略，首先保证的是查找效率。对于把 table 当数组使用时将和 C 数组一样高效。对于 hash 段的值，查找几乎就是计算 hash 值的过程（其中string 的 hash 值是事先计算好保存的），只有在碰撞的时候才会有少许的额外查找时间，而空间也不至于过于浪费。在 hash 表比较满时，插入较容易发生碰撞，这个时候，则需要在表中找到空的插槽。lua 在table 的结构中记录了一个指针顺次从一头向另一头循序插入来解决空槽的检索。每个槽点在记录 next 指针保存被碰撞的 key 的关联性。

整个来说，这种解决方法是非常不错的。

关于映射表的实现，我前段时间也做过一个别的研究。贴在留言本上：

<a href="http://www.codingnow.com/2004/board/view.php?paster=777&reply=0">树表结合的一种映射表实现</a>

<a href="http://www.codingnow.com/2004/board/view.php?paster=776&reply=0">在 vector , map , list 间取得平衡</a>

able 的构造器指的是创建 table 的表达式。每当对构造器进行求值,一个新的 table 就 被创建了。构造器可以创建一个空表或带有初始域的表。构造器的一般语法是:

tableconstructor ::= ‘{‘ [fieldlist] ’}’

fieldlist ::= field {fieldsep field} [fieldsep]

field ::= ‘[‘ exp ‘]’‘=’exp | exp | Name ‘=’exp | exp

fieldsep ::= ‘,’ | ‘;’

每一个形式如[exp1] = exp2 的域都会向新的表添加一个入口 ,它的键是 exp1,值是 exp2。

形式 name = exp 的域等同于形式[“name”] = exp 的域。最后,形式为 exp 的域等同于[i] = exp,

i 是从 1 开始的连续的整数,其它形式的域不会影响到 i 的计数。比如:

a = { [f(1)] = g; "x", "y"; x = 1, f(x), [30] = 23; 45 }

等同于

do

local t = {}

t[f(1)] = g

t[1] = "x"

t[2] = "y"

t.x = 1

t[3] = f(x)

t[30] = 23

t[4] = 45

a=t

end

-- 1st exp

-- 2nd exp

-- t["x"] = 1

-- 3rd exp

-- 4th exp

如果表中最后一个域的形式是一个函数调用表达式或者是一个变参表达式 ,那么这个表

达式返回的所有值都会紧接着前面的域而进入到表中(参考 3.4.9)。

在域列表的最后可以添加一个可选的分隔符,这样做是为了方便代码的机器生成

长度操作符为一元操作符 #。字符串的长度是它的字节数(即当每个字符是一个字节时 的传统长度含义 )。

程序可以通过__len 元方法(参考 2.4)去修改除了字符串外的其它数值求长度操作的行 为。

除非定义了__len 元方法,否则只有当表是一个顺序表时它的长度才能明确 ,也就是说, 表的正整数键值是{1..n},这种情况下,n 就是表的长度。如果一个表为

{10, 20, nil, 40}

这样的表不是一个顺序表 ,因为键 4 有值但键 3 没有值。(这个表没有像{1..n}这样的正

整数键值。)注意,非数字类型的键不会影响到一个表是否是一个顺序表。 

在Lua 5.1中，长度操作符“#”用于返回一个数组或线性表的最后一个索引值。在实际项目中，我们经常使用该操作符来获取数组或线性表的长度。但是使用该操作符是存在陷阱的，比如下面一段代码：

local a = {}
a[1000] = 1
print(#a)           

local a = {}
a[1000] = 1
print(table.maxn(a)) -->1000           

local a = {} -- 创建一个table，并将它的引用存储在a
a["x"] = 10
local b = a -- b与a引用同一个table
print(b["x"])
b["x"] = 20
print(a["x"])

b = nil -- 现在只有a还在引用table
-- 错误：print(b["x"])
print(a["x"])
a = nil -- 现在不存在对table的引用