Lua解释器源码（三）：Tables
目录

1. Tables

Lua中Talbes是关联数组(associative arrays)。 这也意味着Tables能被任何值(除了nil)索引，能够存储任何类型。 而且，当存入一个不存在的索引时，Tables能够自动扩展； 当删除一个索引时(置nil)，Tables能够自动收缩。

不像其它脚本语言，Lua中没有数组(arrays)类型(如Python中的[])，而是用整数索引的Tables表示数组。 这也表示数组为Lua带来了一些好处：

  • Lua不需要为arrays或tables维持两种集合操作，更加简洁；
  • 程序员不用在arrays和tables之间做选择；

在Lua中实现离散的数组是无关紧要的。 如在Perl中，$a[1000000000]=1将创建10亿个对象； 而在Lua中，a={[1000000000]=1}只是创建一个包含一个元素的table。

从Lua 5.0开始，Tables由一个混合数据结构实现，包含一个哈希部分和一个数组部分。 Tables自动动态地调整这两部分内容： 数组部分尽量存储1到n之间的整数索引，而哈希部分存储其它类型的索引和超出n部分的整数索引。 当table需要增长时，Lua重新计算它的哈希部分和数组部分长度。 这两部分都可能为空。 数组部分重新计算的长度n必须符合以下条件：

  • 1到n之间至少一半的槽被使用，这样避免离散的数组浪费空间；
  • n/2+1到n之间至少有一个槽被使用，这样避免当原数组长度为n/2时就要增长；

在计算新的长度后，Lua创建新的部分，把旧的部分中的元素插入到新的部分。

这种混合机制有两个优点：

  1. 整数索引不需要哈希，因此更快；
  2. 数组部分不需要记录索引键，因此比同样情况存入哈希部分省了一半内存；

因此，当Tables被用来做数组时，无论从内存占用上还是访问速度上来说，它更像真实的数组类型。 这时哈希部分是空的。 而当Tables被用作关联数组时，只使用哈希部分，数组部分是空的。 这样内存节省是必要的，因为在Lua中创建很多小tables是很常见的，例如用table来实现对象的时候。

2. 哈希表

Tables的哈希部分使用一种Brent改进的链状发散表(chained scatter table)。 这种哈希表插入新键key1的过程是：

  1. 首先，对key1做哈希，检查其主位置(main position)是否空闲，空闲就插入；
  2. 如果主位置不空闲，被key2占用，则测试key2是否是其它碰撞节点；
  3. 如果key2是碰撞节点，则把这个碰撞节点移至空闲位置，并把插入的key1插入到这个主位置；
  4. 如果key2不是碰撞节点占用，则说明key2也在其主位置，则把key1插入到空闲位置，并把key2->next指向key1。

这样，当发生碰撞时，不需额外分配新的空间，防止内存碎片。 并且next指针关联起了索引相同的节点，这样查找起来就像链表一样。 当哈希表比较满时，插入和查找较容易发生碰撞。 当整个哈希表被填满时，扩大哈希表，重新索引表内数据，从而降低了整体的碰撞次数。

另外，哈希表结构使用一个指针指向第一个空闲位置，这样保证插入时快速找到空闲位置。

3. 源码

Table结构：

typedef union TKey {
struct {
TValuefields;
struct Node *next;  /* for chaining */
} nk;
TValue tvk;
} TKey;

typedef struct Node {
TValue i_val;
TKey i_key;
} Node;

typedef struct Table {
CommonHeader;
lu_byte flags;                                          // 元表标记
lu_byte lsizenode;  /* log2 of size of `node' array */  // 哈希部分大小
struct Table *metatable;                                // 元表
TValue *array;  /* array part */                        // 数组部分
Node *node;                                             // 哈希部分
Node *lastfree;  /* any free position is before this position */ // 第一个空闲位置指针
GCObject *gclist;
int sizearray;  /* size of `array' array */             // 数组部分大小
} Table;

每个table结构最多由三块连续内存组成：

  • Table结构
  • 数组部分是TValue类型数组，长度为sizearray。
  • 哈希部分的Node键值对是<TKey,TValue>类型。 其中TKey包含一个TValue和指向下一个Node的指针（暂时还没看出定义TKey的写法有何深意）。 哈希部分长度为2的lsizenode次幂。

当哈希表没有插入元素时，node指向如下静态全局常量dummynode。

#define dummynode       (&dummynode_)

#define isdummy(n)      ((n) == dummynode)

static const Node dummynode_ = {
{NILCONSTANT},  /* value */
{{NILCONSTANT, NULL}}  /* key */
};

table按照Lua语言的定义，需要实现四种基本操作：读、写、迭代和获取长度。 Lua中并没有删除操作，而仅仅是把对应键位的值设置为nil 。

插入一个新key(即写操作)基本就是按照上面说的流程，注释已经很多了：

TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp;
if (ttisnil(key)) luaG_runerror(L, "table index is nil"); /* 检查key!=nil*/
else if (ttisnumber(key) && luai_numisnan(L, nvalue(key))) /* 检查key!=NaN*/
luaG_runerror(L, "table index is NaN");
mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || isdummy(mp)) {  /* main position is taken? 哈希表满了 */
/* !ttisnil(gval(mp)) 说明主位置被占 */
/* isdummy(mp) 说明table的哈希部分为空 */
node *othern;
Node *n = getfreepos(t);  /* get a free place */
if (n == NULL) {  /* cannot find a free place? */
rehash(L, t, key);  /* grow table */
/* whatever called 'newkey' take care of TM cache and GC barrier */
return luaH_set(L, t, key);  /* insert key into grown table */
}
lua_assert(!isdummy(n));
othern = mainposition(t, gkey(mp));
/* 检查mp是否在其主位置上 */
if (othern != mp) {  /* is colliding node out of its main position? */
/* yes; move colliding node into free position */
while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */
gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
*n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
gnext(mp) = NULL;  /* now `mp' is free */
setnilvalue(gval(mp));
}
else {  /* colliding node is in its own main position */
/* new node will go into free position */
gnext(n) = gnext(mp);  /* chain new position */
gnext(mp) = n;
mp = n;
}
}
setobj2t(L, gkey(mp), key);
luaC_barrierback(L, obj2gco(t), key);
lua_assert(ttisnil(gval(mp)));
return gval(mp);
}

再看一看table的调整部分。 在上一段代码里，如果table没有空闲位置，则要执行rehash(L, t, key)函数增长table。 Lua不会在设置key值为nil时而回收空间，而是在预先准备好的哈希空间使用完后惰性回收。 即在 lastfree 递减到哈希空间头时，做一次 rehash 操作。 rehash实现如下：

static void rehash (lua_State *L, Table *t, const TValue *ek) {
int nasize, na;
int nums[MAXBITS+1];  /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */
int i;
int totaluse;
for (i=0; i<=MAXBITS; i++) nums[i] = 0;  /* reset counts */
nasize = numusearray(t, nums);  /* count keys in array part */
totaluse = nasize;  /* all those keys are integer keys */
totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */
/* count extra key */
nasize += countint(ek, nums);
totaluse++;
/* compute new size for array part */
na = computesizes(nums, &nasize);
/* resize the table to new computed sizes */
luaH_resize(L, t, nasize, totaluse - na);
}

nums数组统计了table中所有key的分布情况， 这其中分别用到了numusearray和numusehash函数。 totaluse统计了总体key的使用个数。 nasize统计了数组部分key的使用个数。 na标识新的数组部分的长度，这是使用computesizes函数在不低于50%利用率下得出的结果。

最终通过lua_resize函数调整数组部分和哈希部分大小。

参考

boyxiaolong 于 2014-04-19 20:27 时评论：
额 是云风 不是风云
Ranler 于 2014-04-19 21:05 时评论：
@boyxiaolong 感谢指出错误

发表评论