- 海之寻趣
- Ranler
- 2014-04-19 21:05
- CC BY-NC-SA
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创建新的部分,把旧的部分中的元素插入到新的部分。
这种混合机制有两个优点:
- 整数索引不需要哈希,因此更快;
- 数组部分不需要记录索引键,因此比同样情况存入哈希部分省了一半内存;
因此,当Tables被用来做数组时,无论从内存占用上还是访问速度上来说,它更像真实的数组类型。 这时哈希部分是空的。 而当Tables被用作关联数组时,只使用哈希部分,数组部分是空的。 这样内存节省是必要的,因为在Lua中创建很多小tables是很常见的,例如用table来实现对象的时候。
2. 哈希表
Tables的哈希部分使用一种Brent改进的链状发散表(chained scatter table)。 这种哈希表插入新键key1的过程是:
- 首先,对key1做哈希,检查其主位置(main position)是否空闲,空闲就插入;
- 如果主位置不空闲,被key2占用,则测试key2是否是其它碰撞节点;
- 如果key2是碰撞节点,则把这个碰撞节点移至空闲位置,并把插入的key1插入到这个主位置;
- 如果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
函数调整数组部分和哈希部分大小。
参考
- The implementation of Lua 5.0
- http://blog.codingnow.com/2005/10/lua_table.html
- 云风:Lua源码欣赏