【Lua源码赏析】第四章 Table 的实现

前言

table是Lua统一的数据结构，所有的数据结构都可以用table实现。
table是开发中最常用的一个lua语法，所以我最先开始看了table的实现

4.1 数据结构

首先我们了解一下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;
// lua table的基本数据结构
typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
  lu_byte lsizenode;  /* log2 of size of `node' array */
  struct Table *metatable;
  TValue *array;  /* array part */
  Node *node;     /* hash part */
  Node *lastfree;  /* any free position is before this position */
  GCObject *gclist;
  int sizearray;  /* size of `array' array */
} Table;

为了效率，Lua 的官方实现，又把 table 的储存分为 数组部分 和 哈希表部分

• 数组部分 ，从 1 开始作整数数字索引。这可以提供紧凑且高效的随机访问。

数组部分存储在TValue *array 中，其长度信息存于int sizearray 。

• 哈希表部分 ，唯一不能做哈希键值的是 nil ，这个限制可以帮助我们发现许多运行期错误。

哈希表存储在Node *node，哈希表的大小用lu_byte lsizenode 表示。lsizenode表示的是2的几次幂，而不是实际大小，因为哈希表的大小一定是2的整数次幂

每个 Table 结构，最多会由三块连续内存构成。

• 一个 table 结构，
• 一块存放了连续整数索引的 数组 ，
• 和一块大小为 2 的整数次幂的 哈希表 。

小优化 ：哈希表的最小尺寸为 2 的 0 次幂，也就是 1 。为了减少空表的维护成本，Lua在这里做了一点优化。

它定义了一个不可改写的空哈希表：dummynode 。让空表被初始化时，node 域指向这个 dummy 节点。它虽然是一个全局变量，但因为对其访问是只读的，所以不会引起线程安全问题。

#define dummynode		(&dummynode_)
static const Node dummynode_ = {
  {NILCONSTANT},  /* value */
  {{NILCONSTANT, NULL}}  /* key */
};

4.1.1 创建table

Table *luaH_new (lua_State *L) {
  Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h;
  t->metatable = NULL;
  t->flags = cast_byte(~0);
  t->array = NULL;
  t->sizearray = 0;
  setnodevector(L, t, 0);
  return t;
}

其中 setnodevector用来初始化哈希表部分。内存管理部分则使用了luaM 相关 API 。

4.1.2 销毁table

void luaH_free (lua_State *L, Table *t) {
  if (!isdummy(t->node))
    luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
  luaM_freearray(




    
L, t->array, t->sizearray);
  luaM_free(L, t);
}

4.2 算法

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

4.2.1 插入

/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
向哈希表插入一个新键:  首先检查一下新键的 mainposition 是否存在？
   若无人使用，则可以直接设置为这个新键。
   若之前有其它键占据了这个位置，则检查占据此位置的键的mainposition 是不是这里？     
      若两者位置冲突，则利用Node结构的next域，以一个单向链表的形式把它们链起来；     
      否则，新键占据这个位置，而老键更换到新位置并根据它的主键找到属于它的链的
            那条单向链表中上一个结点，重新链入。
TValue* luaH_newkey(lua_State* L, Table* t, const TValue* key) {
	Node* mp;
	if (ttisnil(key)) 
		luaG_runerror(L, "table index is nil");
	else if (ttisnumber(key) && luai_numisnan(L, nvalue(key)))
		luaG_runerror(L, "table index is NaN");
	mp = mainposition(t, key);
	if (!ttisnil(gval(mp)) || isdummy(mp))
	{  /* main position被占用 */
		Node* othern;
		Node* n = getfreepos(t);  /* 获取一个空闲的位置 */
		if (n == NULL) {  /* 没有空闲位置了 */
			rehash(L, t, key);  /* 扩容 */
			/* 调用'newkey'的时候注意缓存和GC边界*/
			return luaH_set(L, t, key);  /* 设置值 */
		lua_assert(!isdummy(n));
		othern = mainposition(t, gkey(mp));
		if (othern != mp) {
			/* 冲突节点不是在它自己的main position上 */
			while (gnext(othern) != mp) 
				othern = gnext(othern);  /* 找到main position的前一个节点 */
			//移动冲突节点到空闲位置
			gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
			*n = *mp;  /* 复制冲突节点到一个空闲位置 (mp->next also goes) */
			gnext(mp) = NULL;  /* now `mp' is free */
			setnilvalue(gval(mp));
		else {
			/* 冲突节点在它自己的main 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);
}

创建key的流程如下所示：

• 计要新建的key值为k，并计算k的hash值，记为k_hash
• 计算key应该落在hash表的哪个位置，计算方式为index = k_hash & (2^lsizenode-1)
• 如果hash[index]这个node的value值为nil，将node的key值设置为k的值，并返回value_对象指针，供调用者设置
• 如果hash[index]这个node的value值不为nil，需要分两种情况处理
• 计算node key的hash值，如果经过定位运算后，index的值不在自己所处的位置上，那么lastfree不断左移，直至找到一个空闲的节点，将其移动到这里，修改链表关系，令其上一个与自己计算得到相同index值的节点的next域指向自己（如果存在的话）。新插入的key和value设置到hash[index]节点上
• 计算node key的hash值，如果经过定位运算后，index的值在自己所处的位置上，那么lastfree不断左移，直至找到一个空闲的节点，将自己的key和value值设置到这个节点上，并调整链表关系，将与自己计算得到相同index值的上一个节点的key的next指向自己的位置。

接下来我们举个栗子，来理解一下插入操作

假设一个array的size为4，hash表的size为4的table，所有域的值都是nil，如图10所示，现在要向table塞入一个key值为5，value值为”xixi”的元素，由于key值5超出了array的size范围，那么程序首先会尝试去hash表中查找，我们可以得到最终index的值为1，由于hash[1]这个Node的key值为nil，与要更新元素的key值不相等，因此此时触发了插入操作，由于hash[1]这个Node的key和value均是nil，因此可以将该元素直接设置到这里。

与此同时，一个key值为13，value值为”manistein”的元素也要对table进行赋值，经过之前阐述过的方式计算，得到index值为1，在这种情况下直接在hash表中进行查找，因为hash[1]的value域的值为”xixi”并不是nil，key值为5，与13并不相等，于是此时 发生了hash碰撞 ，key值5经过转换运算，得到的hash表index的值为1，此时他就在这个位置上，因此 key值为13的新元素需要被移走 ，lastfree指针，此时向左移动，并且将key值为13，value值为”manistein”的元素，赋值到lastfree指向的位置上（即hash[3]的位置上），并且将hash[1]的key的next指向lastfree指针所指的位置，如图11所示：

又再次，一个key值为7，value值为”wu”的元素要对table进行赋值，经过计算得到其对应的hash表index值为3，此时hash[3]已经被占用， 此时需要计算，占据在这里的元素的key值，其真实对应的hash表index其实是1，因为hash[1]被占用才被移动到这里，因为这个元素计算得到的index与当前位置并不匹配 ，因此lastfree指针需要继续向左移动，并将key值为13的元素迁移到这里，并更新其前置节点的next域，最后将key值为7的元素，赋值到hash[3]的位置上，如图12所示：

至此，我们完成了整个插入流程。

4.2.2 查询部分

/*
** main search function
const TValue* luaH_get(Table* t, const TValue* key) {
	switch (ttype(key)) {
	case LUA_TNIL: return luaO_nilobject;
	case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key));
	case LUA_TNUMBER: {
		int k;
		lua_Number n = nvalue(key);
		lua_number2int(k, n);
		if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */
			return luaH_getint(t, k);  /* use specialized version */
		  /* else go through */
	default: {
		Node* n = mainposition(t, key);
		do {  /* check whether `key' is somewhere in the chain */
			if (luaV_rawequalobj(gkey(n), key))




    

				return gval(n);  /* that's it */
			else n = gnext(n);
		} while (n);
		return luaO_nilobject;
}

当查询键为整数键且在数组范围内时，在数组部分查询；

否则，根据键的哈希值去哈希表中查询。拥有相同哈希值的冲突键值对，在哈希表中由 Node 的 next 域单向链起来，所以遍历这个链表就可以了。

4.2.3 扩容部分：rehash

static void rehash(lua_State* L, Table* t, const TValue* ek) {
	int nasize, na;
	//创建一个nums[32]的数组，nums[i]表示key值为int型，且key值在(2i-1, 2i]范围内
	//(lua脚本里table的int型下标，如t[1]的key在(2-1, 20]这个区间)，并且value不为nil的元素个数
	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;  /* 初始化值 */
	nasize = numusearray(t, nums);  /* 统计array在nums数组中，不同区间的分布情况 */
	totaluse = nasize;  /* 所以int型key数量*/
	totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */
	/* count extra key */
	nasize += countint(ek, nums);
	totaluse++;//因为新插入一个元素，因此total_element += 1
	/* 计算数组部分的最新尺寸 */
	na = computesizes(nums, &nasize);
	/* 真正的扩容操作 */
	luaH_resize(L, t, nasize, totaluse - na);
void luaH_resize(lua_State* L, Table* t, int nasize, int nhsize) {
	int i;
	int oldasize = t->sizearray;
	int oldhsize = t->lsizenode;
	Node* nold = t->node;  /* save old hash ... */
	if (nasize > oldasize)  /* 数组部分需要变长 */
		setarrayvector(L, t, nasize);
	/* 创建一个合适长度的哈希部分 */
	setnodevector(L, t, nhsize);
	if (nasize < oldasize) {  
		/* 数组部分需要缩短 */
		t->sizearray = nasize;
		/* re-insert elements from vanishing slice */
		for (i = nasize; i < oldasize; i++) {
			if (!ttisnil(&t->array[i]))
				luaH_setint(L, t, i + 1, &t->array[i]);
		/* 缩短数组 */
		luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
	/* 把所有元素重新插入哈希部分*/
	for (i = twoto(oldhsize) - 1; i >= 0; i--) {
		Node* old = nold + i;
		if (!ttisnil(gval(old))) {
			/* doesn't need barrier/invalidate cache, as entry was
			   already present in the table */
			setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
	if (!isdummy(nold))
		luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* 释放旧的数组 */
}

rehash 的主要工作是统计当前 table中到底有多少有效键值对，以及决定数组部分需要开辟多少空间。其原则是 最终数组部分的利用率需要超过 50% 。

lua 使用一个 rehash函数中定义在栈上的 nums 数组来做这个整数键统计工作。这个数组按 2 的整数幂次来分开统计各个区段间的整数键个数。统计过程的实现见 numusearray 和 numusehash 函数。

最终，computesizes 函数计算出不低于 50% 利用率下，数组该维持多少空间。同时，还可以得到有多少有效键将被储存在哈希表里。

根据这些统计数据，rehash 函数调用 luaH_resize 这个 api 来重新调整数组部分和哈希部分的大小，并把不能放在数组里的键值对重新塞入哈希表。

4.2.4 表的迭代部分

遍历table主要是ipairs和pairs两个函数。这两个函数都会在vm内部临时创建出两个变量state和index，用于对lua表进行迭代访问，每次访问的时候，会调用luaH_next函数

int luaH_next(lua_State* L, Table* t, StkId key) {
	int i = findindex(L, t, key);  /* find original element */
	for (i++; i < t->sizearray; i++) {  /* 先遍历数组部分 */
		if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
			setnvalue(key, cast_num(i + 1));
			setobj2s(L, key + 1, &t->array[i]);
			return 1;
	for (i -= t->sizearray; i < sizenode(t); i++) {  /* 再遍历哈希部分 */
		if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
			setobj2s(L, key, gkey(gnode(t, i)));
			setobj2s(L, key + 1, gval(gnode(t, i)));
			return 1;
	return 0;  /* no more elements */
}

在大多数其它语言中，遍历一个无序集合的过程中，通常不允许对这个集合做任何修改。即使允许，也可能产生未定义的结果。在 lua 中也一样，遍历一个 table 的过程中，向这个 table 插入一个新键这个行为，将无法预测后续的遍历行为。 但是，lua 却允许在遍历过程中，修改 table 中已存在的键对应的值 。由于 lua 没有显式的从 table 中删除键的操作，只能对不需要的键设为空。

4.2.5 获取长度

lua 的 table 的长度定义只对序列表有效

它使用二分法，来快速在哈希表中快速定位一个非空的整数键的位置。

/*
** Try to find a boundary in table `t'. A `boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
int luaH_getn(Table* t) {
	unsigned int j = t->sizearray;
	if (j > 0 && ttisnil(&t->array[j - 1])) {
		/* there is a boundary in the array part: (binary) search for it */
		unsigned int i = 0;
		//二分查找
		while (j - i > 1) {
			unsigned int m = (i + j) / 2;
			if (ttisnil(&t->array[m - 1])) j = m;
			else i = m;
		return i;