Lua中Table数据结构的定义、初始化、查找等。

Table数据结构的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef union TKey {
struct {
TValuefields;
int next; /* for chaining (offset for next node) */
} nk;
TValue tvk;
} TKey;

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

typedef struct Table {
CommonHeader;
lu_byte flags; /* 1<<p means tagmethod(p) is not present */
lu_byte lsizenode; /* log2 of size of 'node' array */
unsigned int sizearray; /* size of 'array' array */
TValue *array; /* array part */
Node *node;
Node *lastfree; /* any free position is before this position */
struct Table *metatable;
GCObject *gclist;
} Table;
  • Table的结构中有CommonHeader成员,这是一个在lObject.h中定义的宏,包含了一些成员,所有受gc管理的对象均含有CommonHeader,其继承自GObject对象。CommonHeader 相当于来自父类的数据,在整个结构的最前面,其他成员相当于子类数据。通过这种方式可以让GCObject 指针指向所有受gc管理的lua的对象,并且CommonHeader 结构中还有当前对象的类型,可以转换成具体类型的对象。
1
2
3
4
5
/*
** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/
#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked

TValue是所有lua数据类型的集合,其包含一个类型_tt和一个value,Value类型是一个union,可以是lua的任意类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
** Tagged Values. This is the basic representation of values in Lua,
** an actual value plus a tag with its type.
*/

#define TValuefields Value value_; int tt_

typedef struct lua_TValue TValue;

union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Integer i; /* integer numbers */
lua_Number n; /* float numbers */
};


struct lua_TValue {
TValuefields;
};

Table主要有两部分,数组和哈希

  1. array和node是两个一维数组,array是普通的数组,成员为TValue,node是一个hash表存放key,value键值对。node的key为TKey类型,Tkey是一个union,当没有hash冲突的时候是一个TValue,当有hash冲突的时候TKey是一个struct,多一个next值,指向下一个有冲突的节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    typedef union TKey {
    struct {
    TValuefields;
    int next; /* for chaining (offset for next node) */
    } nk;
    TValue tvk;
    } TKey;


    /* copy a value into a key without messing up field 'next' */
    #define setnodekey(L,key,obj) \
    { TKey *k_=(key); const TValue *io_=(obj); \
    k_->nk.value_ = io_->value_; k_->nk.tt_ = io_->tt_; \
    (void)L; checkliveness(G(L),io_); }


    typedef struct Node {
    TValue i_val;
    TKey i_key;
    } Node;
  2. sizearray:是数组array的大小

  3. lsizenode:2^lsizenode 的值为node 的大小

  4. lastfree:lastfree 指针的右边均由非空的或者不能访问的node (即不属于自己的空间,访问会越界)组成

  5. metatable :元表

  6. gclist:与gc 有关,将table加入到gray表中时,gclist指向gray表中的下一个元素或者NULL

  7. flags : 这是一个byte类型的数据,用于表示这个表中提供了哪些元方法,最开始的flag为1,当查找了一次之后,如果该表中存在某个元方法,那么将该元方法对应的flag bit置为0,这样下一次查找时只需要比较这个bit就行了。每个元方法对应的bit定义在ltm.h中 。

68747470733a2f2f7261772e6769746875622e636f6d2f6c69636875616e672f4c75612d536f757263652d496e7465726e616c2f6d61737465722f7069632f7461626c652e706e67.png
68747470733a2f2f7261772e6769746875622e636f6d2f6c69636875616e672f4c75612d536f757263652d496e7465726e616c2f6d61737465722f7069632f7461626c652e706e67.png

Table的初始化:

1
2
3
4
5
6
7
8
9
10
Table *luaH_new (lua_State *L) {
GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
Table *t = gco2t(o);
t->metatable = NULL;
t->flags = cast_byte(~0);
t->array = NULL;
t->sizearray = 0;
setnodevector(L, t, 0);
return t;
}

首先,为Table开辟空间,然后将其加到allgc链表上通过gc进行管理,之后初始化Table的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
static void setnodevector (lua_State *L, Table *t, unsigned int size) {
int lsize;
if (size == 0) { /* no elements to hash part? */
t->node = cast(Node *, dummynode); /* use common 'dummynode' */
lsize = 0;
}
else {
int i;
lsize = luaO_ceillog2(size);
if (lsize > MAXHBITS)
luaG_runerror(L, "table overflow");
size = twoto(lsize);
t->node = luaM_newvector(L, size, Node);
for (i = 0; i < (int)size; i++) {
Node *n = gnode(t, i);
gnext(n) = 0;
setnilvalue(wgkey(n));
setnilvalue(gval(n));
}
}
t->lsizenode = cast_byte(lsize);
t->lastfree = gnode(t, size); /* all positions are free */
}

#define dummynode (&dummynode_)

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

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

flag设置为全1表示没有元方法,node指向的不是NULL而是dummynode,dummynode是一个全局共享的对象(key和value均为nil),这样做可以减少NULL的判断:例如,刚初始化完table,需要查找一个key为“test”的对象,因为lsizenode为0,所以经过运算确定的位置肯定为node[0],然后读取node[0].i_key和“test”的TKey进行比较,判断是否相同,node[0]是dummynode,所以比较结果肯定不相同,所以返回nil;如果node[0]为NULL,访问node[0]的时候必须先判断node[0]是否为NULL,否则直接访问会越界,dummynode的设计省去了NULL的判断。

Table的查找:

因为table有两部分,数组和hash表,所以查找也分为两部分来进行:

  1. 在数组中查找,如果传入的key是integer类型,而且其值-1小于sizearray的话,在数组中查找。
  2. 其他情况在hash表中查找:计算出该key的散列值,根据此散列值访问Node数组得到散列桶所在的位置,遍历该散列桶下的所有链表元素,直到找到该key为止。

在Lua中除了nil,其他类型均可以作为表的key,那么table的key是如何与其array数组与hash表的下标对应的呢?

对于array数组,如果是上述的第一种情况,则直接将key-1即得到了下标,对于hash表则需要将key转换成uint类型,然后通过计算得到下标。

通过运算将各类型转换为uint 类型的值,如将LUA_TNUMFLT 类型二进制数值转成以uint 型类 型表示,将LUA_TTABLE 的gc 指针转换为uint 类型, LUA_TSHRSTR 类型直接取其hash值,因为短字符串在构造时会计算其hash值,LUA_TLNGSTR 类型则需要通过hash函数计算其hash值。在 完成了对key 的hash运算以后,需要根据key 的hash值计算该key对应hash表中的哪个下标,计算的公式是:

1
index = hash_value & ((2^lsizenode) - 1)

其中2^lsizenode - 1 为一个二进制低位全为1 的值,和hash_value 相与可以保证hash_value超过2^lsizenode - 1 的部分为0,则得到的值一定在[0,(2^lsizenode) - 1] 区间内,此时key和hash 表的下标就对应了起来,并且不会越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
** main search function
*/
const TValue *luaH_get (Table *t, const TValue *key) {
switch (ttype(key)) {
case LUA_TSHRSTR: return luaH_getstr(t, tsvalue(key));
case LUA_TNUMINT: return luaH_getint(t, ivalue(key));
case LUA_TNIL: return luaO_nilobject;
case LUA_TNUMFLT: {
lua_Integer k;
if (numisinteger(fltvalue(key), &k)) /* index is int? */
return luaH_getint(t, k); /* use specialized version */
/* else go through */
}
default: {
Node *n = mainposition(t, key);
for (;;) { /* check whether 'key' is somewhere in the chain */
if (luaV_rawequalobj(gkey(n), key))
return gval(n); /* that's it */
else {
int nx = gnext(n);
if (nx == 0) break;
n += nx;
}
};
return luaO_nilobject;
}
}
}

/*
** search function for integers
*/
const TValue *luaH_getint (Table *t, lua_Integer key) {
/* (1 <= key && key <= t->sizearray) */
if (l_castS2U(key - 1) < t->sizearray)
return &t->array[key - 1];
else {
Node *n = hashint(t, key);
for (;;) { /* check whether 'key' is somewhere in the chain */
if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
return gval(n); /* that's it */
else {
int nx = gnext(n);
if (nx == 0) break;
n += nx;
}
};
return luaO_nilobject;
}
}

Table的更新:

table 更新也分两种情况:

  1. 通过上述查找的 value 如果不是 luaO_nilobject ,直接将 value 更改即可,即table的修改和删除(将值置为nil)
  2. 查找返回的是 luaO_nilobject ,即 key 在 table 中不存在时( table 的插入操作)需要先找一个空的槽,然后完成插入操作,如果找不到空槽则需要扩容。

散列表部分的数据组织是,首先计算数据的key所在的桶数组位置,这个位置称为mainposition。相同mainposition的数据以链表形式组织:

FlowchartDiagram1.png
FlowchartDiagram1.png

这部分的API包括luaH_set、luaH_setnum、luaH_setstr 这三个函数,它们的实际行为并不在其函数内部对 key 所对应的数据进行添加或者修改,而是返回根据该 key 查找到的 TValue 指针,由外部的使用者来进行实际的替换操作。

当找不到对应的 key 时,这几个 API 最终都会调用内部的 newkey 函数分配一个新的 key 来返回。

具体的更新操作如下:

TableUpdate.png
TableUpdate.png
  1. 如果查找一个空槽:

    在lua Table中有一个lastfree指针,在更新时通过该指针寻找一个空槽,lastfree 指针在最开始的时候指向NULL ,当空间不够rehash 时,lastfree 指针指向 node 数组中最后不可用的空间,如node 数组size为4 其指向的就是4 的位置(从0开始)。当需要找一个空槽时,lastfree指针向左移,判断当前位置有没有被占用,即key 是否为nil ,如果被占用则继续左移,直到找到一个空槽,或者地址大于node 的地址,即移动到了node 的前一个,表示没有找到。这种方式可以保证lastfree的右边和当前指向的位置均不可用或者被占用,可以减少在查找空槽时对非nil元素的遍历。

  2. 冲突时谁移动:

    记冲突位置为index ,找到的空槽位置为freeindex ,发生冲突位置的key 为oldkey , 新的key 为newkey 。发生冲突时计算oldkey 的下标,如果值为index ,则将newkey 建立 到freeindex 位置处,如果oldkey 计算后不是index ,而是因为冲突被移动到index 位置的,则移动oldkey 的node到新的槽。

  3. Tkey的Next如何设置:

    lua 中的Tkey 中添加了一个next 成员,通过next 可以查找冲突位置的所有元素。比如两个元素冲突了,冲突位置为index (下标,后面的freeindex 也是下标),这两个元素分别 为node1 、node2 ,假设将node1 移动到了另一个位置freeindex ,那么node2 则在index位置,node2 的next 为freeindex 减去index ,当需要查找node1 时,通过hash 运算找到是node2 ,比较发现不是要找的元素,此时可以通过index + next 找到freeindex 的位置,继续比较判断发现是node1 则返回结果。这种方式可以减少查找时对非冲突元素的遍 历,加快查找效率,不过也有弊端就是每个节点占用的空间会增减四个字节。

Table的扩容:

rehash操作是hash 表不可避免的,当空间不够时就需要进行扩容,而扩容后每个元素的下标就需要重新计算。对于一般的开放地址法会有一个负载因子 ,当负载因子大于某个值的时候就需要扩容,这个是为了考虑效率问题,当负载因子越来越大的时候,元素之间冲突的可能性会越来越大,导致插入和查找的时间复杂度会增大所以需要扩容降低负载因子。lua 的table没有负载因子,而是当node 的所有空间都用完的时候才会扩容(被置为nil 也算,lastfree指针不会向右移动,而判断满的条件就是lastfree 已经到了第一个元素的位置)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
*/
static void rehash (lua_State *L, Table *t, const TValue *ek) {
unsigned int nasize, na;
unsigned int nums[MAXABITS + 1];
int i;
int totaluse;
for (i = 0; i <= MAXABITS; 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);
}

扩容前会先统计table中的数量,将其存至nasize中;建立了一个大小为32的数组并且初始化为0,然后统计array数组中不为nil的元素个数,统计时通过分段的方式进行统计,将所有的元素按(2^(i-1),2^i]分段,分为32 个区间段:(0.5, 1]、(1, 2]、(2, 4]、 (4, 8] ……,统计步骤如下:

  1. 分配一个位图 nums,将其中的所有位置 0。这个位图的意义在于:nums 数组中第 i 个元素存放的是 key 在 2^(i-1)和 2^i 之间的元素数量。
  2. 遍历 Lua 表中的数组部分,计算其中的元素数量,更新对应的 nums 数组中的元素数量(numusearray函数)。
  3. 遍历 Lua 表中的散列桶部分,因为其中也可能存放了正整数,需要根据这里的正整数数量更新对应的 nums 数组元素数量(numusehash 函数)。
  4. 此时nums 数组已经拥有了当前这个 Table 中所有正整数的分配统计,逐个遍历 nums 数组,获得其范围区间内所包含的整数数量大于 50%的最大索引,作为重新散列之后的数组大小,超过这个范围的正整数,就分配到散列桶部分了(computesizes 函数)
  5. 根据上面计算得到的调整后的数组和散列桶大小调整表(resize 函数)。

调整标准:希望在调整过后,数组在每一个二次方位置容纳的元素数量都超过该范围的 50%。能达到这个目标的话,我们就认为这个数组范围发挥了最大的效率

重新散列的代价与解决:

1
2
3
4
local a = {}
for i = 1,3 do
a[i] = true
end
  1. 最开始,Lua 创建了一个空表
  2. 在第一次迭代中,a[1]为 true 触发了一次重新散列操作,将数组部分长度设置为 2^0,即 1,散列表部分仍为空。
  3. 在第二次迭代中,a[2]为 true 触发了一次重新散列操作,将数组部分长度设置为 2^1,即 2。
  4. 最后一次迭代中,a[3]又触发了一次重新散列操作,将数组部分长度设置为 2^2,即 4。

如果有很多很小的表要进行创建,则会对开销造成巨大的影响——可以预先填充以避免重新散列操作。

Table 的迭代:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int luaH_next (lua_State *L, Table *t, StkId key) {
unsigned int i = findindex(L, t, key); /* find original element */
for (; i < t->sizearray; i++) { /* try first array part */
if (!ttisnil(&t->array[i])) { /* a non-nil value? */
setivalue(key, i + 1);
setobj2s(L, key+1, &t->array[i]);
return 1;
}
}
for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */
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 */
}

/*
在数组部分查找数据:
查找成功,则返回该 key 的下一个数据
否则在散列桶部分查找数据:
查找成功,则返回该 key 的下一个数据
*/

一开始进入 findindex 函数,返回一个整数索引,如果这个索引在表的 sizearray 之内,则说明落入到数组部分,否则就落入到散列桶部分。

Table 取长度操作:

对Lua 中的表进行取长度的操作时,如果没有提供该表的原方法 _len,那么该操作只针对该表的序列部分进行——序列指的是该表的一个子集{1…n},n是一个正整数,其中每个键对应的数据都不为 nil。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 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;
}
/* else must find a boundary in hash part */
else if (isdummy(t->node)) /* hash part is empty? */
return j; /* that is easy... */
else return unbound_search(t, j);
}

Table的元表:

注意事项:

  • 尽量不要在一个表中混用数组和散列桶部分,即一个表最好只存放一类数据。Lua 的实现上确实提供了两者统一表示的遍历,但这并不意味着使用者就应该混用这两种方式。
  • 尽量不要在表中存放 nil 值,这会让取长度操作的行为不稳定。
  • 尽量避免重新散列操作,因为这个操作的代价极大,通过预分配、只使用数组部分等策略规避这个 Lua 解释器背后的动作,能提升不少效率。

参考:

  • 《lua 设计与实现》codedump 著