Lua性能优化技巧（三）：关于表
一般情况下，你不需要知道Lua实现表的细节，就可以使用它。实际上，Lua花了很多功夫来隐藏内部的实现细节。但是，实现细节揭示了表操作的性能开销情况。因此，要优化使用表的程序（这里特指Lua程序），了解一些表的实现细节是很有好处的。
Lua的表的实现使用了一些很聪明的算法。每个Lua表的内部包含两个部分：数组部分和哈希部分。数组部分以从1到一个特定的n之间的整数作为键来保存元素（我们稍后即将讨论这个n是如何计算出来的）。所有其他元素（包括在上述范围之外的整数键）都被存放在哈希部分里。
正如其名，哈希部分使用哈希算法来保存和查找键。它使用被称为开放地址表的实现方式，意思是说所有的元素都保存在哈希数组中。用一个哈希函数来获取一个键对应的索引；如果存在冲突的话（意即，如果两个键产生了同一个哈希值），这些键将会被放入一个链表，其中每个元素对应一个数组项。当Lua需要向表中添加一个新的键，但哈希数组已满时，Lua将会重新哈希。重新哈希的第一步是决定新的数组部分和哈希部分的大小。因此，Lua遍历所有的元素，计数并对其进行归类，然后为数组部分选择一个大小，这个大小相当于能使数组部分超过一半的空间都被填满的2的最大的幂；然后为哈希部分选择一个大小，相当于正好能容纳哈希部分所有元素的2的最小的幂。
当Lua创建空表时，两个部分的大小都是0。因此，没有为其分配数组。让我们看一看当执行下面的代码时会发生什么：
locala={}
fori=1,3do
a[i]=true
end
这段代码始于创建一个空表。在循环的第一次迭代中，赋值语句
a[1]=true
触发了一次重新哈希；Lua将数组部分的大小设为1，哈希部分依然为空；第二次迭代时
a[2]=true
触发了另一次重新哈希，将数组部分扩大为2.最终，第三次迭代又触发了一次重新哈希，将数组部分的大小扩大为4。
类似下面的代码
a={}
a.x=1;a.y=2;a.z=3
做的事情类似，只不过增加的是哈希部分的大小。
对于大的表来说，初期的几次重新哈希的开销被分摊到整个表的创建过程中，一个包含三个元素的表需要三次重新哈希，而一个有一百万个元素的表也只需要二十次。但是当创建几千个小表的时候，重新哈希带来的性能影响就会非常显著。
旧版的Lua在创建空表时会预选分配大小（4，如果我没有记错的话），以防止在初始化小表时产生的这些开销。但是这样的实现方式会浪费内存。例如，如果你要创建数百万个点（表现为包含两个元素的表），每个都使用了两倍于实际所需的内存，就会付出高昂的代价。这也是为什么Lua不再为新表预分配数组。
如果你使用C编程，可以通过Lua的API函数lua_createtable来避免重新哈希；除lua_State之外，它还接受两个参数：数组部分的初始大小和哈希部分的初始大小[1]。只要指定适当的值，就可以避免初始化时的重新哈希。需要警惕的是，Lua只会在重新哈希时收缩表的大小，因此如果在初始化时指定了过大的值，Lua可能永远不会纠正你浪费的内存空间。
当使用Lua编程时，你可能可以使用构造式来避免初始化时的重新哈希。当你写下
{true,true,true}
时，Lua知道这个表的数组部分将会有三个元素，因此会创建相应大小的数组。类似的，如果你写下
{x=1,y=2,z=3}
Lua也会为哈希部分创建一个大小为4的数组。例如，执行下面的代码需要2.0秒：
fori=1,1000000do
locala={}
a[1]=1;a[2]=2;a[3]=3
end
如果在创建表时给定正确的大小，执行时间可以缩减到0.7秒：
fori=1,1000000do
locala={true,true,true}
a[1]=1;a[2]=2;a[3]=3
end
但是，如果你写类似于
{[1]=true,[2]=true,[3]=true}
的代码，Lua还不够聪明，无法识别表达式（在本例中是数值字面量）指定的数组索引，因此它会为哈希部分创建一个大小为4的数组，浪费内存和CPU时间。
两个部分的大小只会在Lua重新哈希时重新计算，重新哈希则只会发生在表完全填满后，Lua需要插入新的元素之时。因此，如果你遍历一个表并清除其所有项（也就是全部设为nil），表的大小不会缩小。但是此时，如果你需要插入新的元素，表的大小将会被调整。多数情况下这都不会成为问题，但是，不要指望能通过清除表项来回收内存：最好是直接把表自身清除掉。
一个可以强制重新哈希的猥琐方法是向表中插入足够多的nil。例如：
a={}
lim=10000000
fori=1,limdoa[i]=iend --创建一个巨表
print(collectgarbage("count")) -->196626
fori=1,limdoa[i]=nilend --清除所有元素
print(collectgarbage("count")) -->196626
fori=lim+1,2*limdoa[i]=nilend--创建一堆nil元素
print(collectgarbage("count")) -->17
除非是在特殊情况下，我不推荐使用这个伎俩：它很慢，并且没有简单的方法能知道要插入多少nil才够。
你可能会好奇Lua为什么不会在清除表项时收缩表。首先是为了避免测试写入表中的内容。如果在赋值时检查值是否为nil，将会拖慢所有的赋值操作。第二，也是最重要的，允许在遍历表时将表项赋值为nil。例如下面的循环：
fork,vinpairs(t)do
ifsome_property(v)then
t[k]=nil–清除元素
end
end
如果Lua在每次nil赋值后重新哈希这张表，循环就会被破坏。
如果你想要清除一个表中的所有元素，只需要简单地遍历它：
forkinpairs(t)do t[k]=nil end
一个“聪明”的替代解决方案：
whiletruedo localk=next(t) ifnotkthenbreakend t[k]=nil end
但是，对于大表来说，这个循环将会非常慢。调用函数next时，如果没有给定前一个键，将会返回表的第一个元素（以某种随机的顺序）。在此例中，next将会遍历这个表，从开始寻找一个非nil元素。由于循环总是将找到的第一个元素置为nil，因此next函数将会花费越来越长的时间来寻找第一个非nil元素。这样的结果是，这个“聪明”的循环需要20秒来清除一个有100,000个元素的表，而使用pairs实现的循环则只需要0.04秒。
[1]尽管重新哈希算法始终设置数组的大小为2的幂，数组的大小依然可以为任何自然数值。而哈希的大小必须为2的幂，所以第二个参数总是会被圆整为不小于原值的最小的2的幂。