Lua 5.4 Table

Question

如题所述

Answer 1

table在Lua 5.4中占据着重要的地位，内容丰富。本文将介绍其基础实现。

首先，Table是Lua的唯一数据结构。其次，下标从1开始。Lua内部通过数组和哈希表实现table，这使得table既可以作为字典使用，也可以作为数组，配合元表机制还能模拟面向对象。

例如，a和b都是table，a=b则是a的浅拷贝。

《Lua程序设计 第4版》中提到，Lua语言中的Table本质上是一种辅助数组，不仅可以使用数值作为索引，还可以使用字符串或其他任意类型的值作为索引（nil除外）。

在定义基础数据结构时，有一个i_val提供了快速访问val_的途径。

下面以一个例子说明table的创建过程：

第一步：新建table，调用luaH_new()，alimit=0，lsizenode=0，lastfree=NULL。

第二步：调用luaH_set() -> key=8，键值是int -> luaH_getint() -> key=8 > alimit -> 在哈希部分查找 -> hashint() hash=8%1 = 0 -> 现在哈希部分是空的没有找到 -> luaH_newkey() -> 因为lastfree=NULL -> rehash() -> 统计table的nums[]数组 -> 哈希部分增加 -> lsizenode=0 ([公式] 和新建table的区别在于lastfree!=NULL) -> 插入哈希表部分成功。

第三步：key=1，键值是int -> luaH_getint() -> key=1 > alimit -> 在哈希部分查找 -> hashint() hash=1%1 = 0 -> 因为lastfree=NULL -> rehash() -> 统计table的nums[]数组 -> 数组部分增加 -> alimit=1 -> 插入数组部分成功。

第四步：key=4，键值是int -> luaH_getint() -> key=4 > alimit -> 在哈希部分查找 -> hashint() hash=4%1 = 0 -> 因为lastfree=NULL -> rehash() -> 统计table的nums[]数组 -> 哈希部分增加 -> lsizenode=1 ([公式] ) -> 冲突 -> mainposition确实冲突 -> 把该节点放在lastfree里面，mainpostion的next=1 -> 插入哈希表部分成功。

第五步：key=5，键值是int -> luaH_getint() -> key=5 > alimit -> 在哈希部分查找 -> hashint() hash=5%2 = 1 -> 因为lastfree=NULL -> rehash() -> 统计table的nums[]数组 -> 哈希部分增加 -> lsizenode=2 ([公式] 向上取整 = 2) -> 冲突 -> mainposition不该在这个点的 -> 把冲突节点放在lastfree里面，把该节点放在index=1的地方 -> 修改冲突节点的链接节点的next为3。

table的遍历分为ipairs和pairs，ipairs遍历数组部分，pairs遍历整个table。遍历顺序是先遍历数组部分，然后遍历哈希表部分，哈希表部分实际上是把node顺序遍历一次。

在Lua中，删除操作不是真的删除，而是把对应键位的值设置为nil。

总结：

（1）操作table时，尽量减少rehash操作，因为其开销很大。在插入新的键值对时（key原来不在table中）可能会触发rehash操作，而直接修改已存在key对应的值，不会触发rehash操作，包括赋值为nil。

（2）遍历table时，不允许向table插入新键，否则无法预测后续的遍历行为。但Lua允许在遍历过程中修改table中已存在的键对应的值，包括修改后的值为nil，也是允许的。

（3）删除table元素等同于向对应key赋值为nil，等待垃圾回收。但删除table一个元素时，并不会触发表重构行为，即不会触发rehash操作。

（4）为了减少rehash操作，当构造数组时，如果预先知道其大小，可以预分配数组大小。在脚本层可以使用local t={nil,nil,nil}来预分配数组大小。在C语言层，可以使用接口void lua_createtable (lua_State *L, int narr, int nrec)来预分配数组大小。

（5）注意在使用长度操作符#对数组其长度时，数组不应该包含nil值，否则很容易出错。