• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

lua的table实现以及遍历方式

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

最近遇到一件很郁闷的事情,游戏里面我老是当队长!后来发现是因为队伍里每个人的数据会以游戏的ID为key,其余要用到的数据为value,放在一个table里面。然后用pairs遍历这个table,一个个加入队伍,所以谁当队长实际上和pairs的遍历顺序有关,具体来说是和pairs找到的第一个元素有关。一时兴起,重新看了一下lua的table的实现,终于找到原因!
一如既往,先报源码:
Ltable.c     table的主要代码在这里
Lobject.h     lua的基础对象的定义,包括table
假设我的ID是100005(纯粹是个假设,我当然不可能把我真的ID报出来啦,不过我的ID和这个100005一样苦逼啊有木有)。假设队员的ID是100001,100002,100003,100004,经过试验用pairs来遍历这些key的顺序是100005,100002,100003,100004,100001,下面就看看为什么遍历顺序是这样的。
先看看在Lobject.h中的关键数据结构:
/*
** 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
....
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;
Node *lastfree;  /* any free position is before this position */
GCObject *gclist;
int sizearray;  /* size of `array' array */
} Table;
lua的table实际上是一个数组和hash表的结合体,定义中我们只关心lsizenode,array,node,lastfree和sizearray,其余的部分是每个lua基本类型都有的部分。lsizenode,node,lastfree这三个属性存储的就是哈希表部分;array和sizearray存储的就是数组部分。数组部分比较简单,array就是数组本身,sizearray是数组的大小;哈希表部分的话,node指向哈希表起始地址,lsizenode是log2(node指向的哈希表节点数目),注意2^lsizenode不等于哈希表中存储变量的数目,因为哈希表是有可能有冲突的,所以一个哈希表节点是一个链表的表头,他可能对应多个存储变量。lastfree指向node里面最后一个未用的节点(这个用法很特别,后面会详细说)。
/*
** Tagged Values
*/
#define TValuefields     Value value; int tt
....
typedef struct lua_TValue {
TValuefields;
} TValue;
...
typedef union TKey {
struct {
TValuefields;
struct Node *next;  /* for chaining */
} nk;
TValue tvk;
} TKey;
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
Node是哈希表中节点的结构,i_val是这个节点对应value,i_key是节点对应的key,其类型为TKey。TKey的定义很巧究(也很坑爹),这是一个union,TValue的定义实际上也是TValuefields这个宏,所以TKey的内存分布如下所示。
|------------------------------|
|value; |           |            |
|----------   tvk   |            |
|tt;       |           |      nk   |
|-------------------|             |
|next    |   next |             |
|-------------------------------|
画得很丑,将就着看吧。简单来说如果有TKey  a;那么
a.tvk.value == a.nk.value
a.tvk.tt == a.nk.tt
lua之所以用这种方式来表示Node,感觉一个很重要的原因是为了适应不同参数类型的接口。
TKey中tvk是这个key的值,nk中的next则指向key冲突的下一个节点。lua的hash表的hash算法比较特别,一般的hash表都是根据key算出hash(key),然后把这个key放在hash表的hash(key)位置上,如果有冲突的话,就放在hash(key)位置的链表上。
但是lua的hash表中,如果有冲突的话,lua会找hash表中一个空的位置(从后往前找,假设为x),然后把新的key放在这个空的位置x上,并且让hash表中hash(key)处的节点的nk.next指向x。这个意思就是,假如有冲突的话,不用重新分配空间来存储冲突的key,而是利用hash表上未用过的空格来存储。但是这样会引入另外一个问题,本来key是不应该放在x的,假设有另外一个key2,hash(key2)算出来的位置也在x的话,那就表示本来x这个位置应该是给key2的,但是由于x被key占用了,导致key2没地方放了。这时候lua的处理方式是把key放到另外一个空格,然后让key2占回x。当hash表已经没有空格的时候,lua就会resize这个hash表。这样做的好处主要是不用动态申请内存空间,hash表初始化的时候有多少内存空间就用多少,不够就resize这个hash表。
下面来看看table的具体实现,见Ltable.c:
初始化table:
Table *luaH_new (lua_State *L, int narray, int nhash) {
Table *t = luaM_new(L, Table);
luaC_link(L, obj2gco(t), LUA_TTABLE);
t->metatable = NULL;
t->flags = cast_byte(~0);
/* temporary values (kept only if some malloc fails) */
t->array = NULL;
t->sizearray = 0;
t->lsizenode = 0;
t->node = cast(Node *, dummynode);
setarrayvector(L, t, narray);
setnodevector(L, t, nhash);
return t;
}
一目了然,无需多说,array和hash部分默认都是0,然后用narray和nhash来初始化array和hash部分。array部分就初始化为narray长度的数组,hash部分就初始化为2^ceil(log2(nhash))长度的哈希表。table的哈希表的长度必须是2的幂,至于增长规则会在后面说到。
table插入key:
/*
** 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.
*/
static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || mp == dummynode) {
Node *othern;
Node *n = getfreepos(t);  /* get a free place */
if (n == NULL) {  /* cannot find a free place? */
rehash(L, t, key);  /* grow table */
return luaH_set(L, t, key);  /* re-insert key into grown table */
}
lua_assert(n != dummynode);
othern = mainposition(t, key2tval(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;
}
}
gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
luaC_barriert(L, t, key);
lua_assert(ttisnil(gval(mp)));
return gval(mp);
}
之前已经说过了,就是一个利用哈希表空洞来存储冲突节点的算法。其中有一些要注意的地方,首先是getfreepos这个函数:
static Node *getfreepos (Table *t) {
while (t->lastfree-- > t->node) {
if (ttisnil(gkey(t->lastfree)))
return t->lastfree;
}
return NULL;  /* could not find a free place */
}
这个函数会从后往前搜索hash表的空洞,找到的话就返回指向这个空洞的指针。lastfree在创建hash表的时候指向hash表最后一个元素。通过getfreepos可以知道hash表究竟还有没有空洞,如果没有的话,就要调用rehash来重新调整哈希表的大小了:
static void rehash (lua_State *L, Table *t, const TValue *ek) {
int nasize, na;
int nums[MAXBITS+1];  /* nums[i] = number of keys between 2^(i-1) and 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 */
resize(L, t, nasize, totaluse - na);
}
rehash中,nums是用来统计key的数量分布的,他的定义也说的很清楚
int nums[MAXBITS+1];  /* nums[i] = number of keys between 2^(i-1) and 2^i */
numusearray和numusehash的目的是统计数组和hash表部分key的使用情况,把它更新到nums里面去。然后根据nums计算要申请多大的数组部分以及多大的hash表,算法在computesizes处:
static int computesizes (int nums[], int *narray) {
int i;
int twotoi;  /* 2^i */
int a = 0;  /* number of elements smaller than 2^i */
int na = 0;  /* number of elements to go to array part */
int n = 0;  /* optimal size for array part */
for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
if (nums[i] > 0) {
a += nums[i];
if (a > twotoi/2) {  /* more than half elements present? */
n = twotoi;  /* optimal size (till now) */
na = a;  /* all elements smaller than n will go to array part */
}
}
if (a == *narray) break;  /* all elements already counted */
}
*narray = n;
lua_assert(*narray/2 <= na && na <= *narray);
return na;
}
nums就是key的分布情况,narray是所有key里面,可以放在array里面的key的个数(array大小最大只能到2^26,并且如果key不是整数不能放在array里)。computesizes的算法,简单来说就是找出一个最小的i,使其满足小于2^i的key的个数大于2^(i-1),这个2^i就是数组部分的大小。如果找不到满足条件的i,数组部分长度为0。这样做的话,就保证了数组部分包含尽量多的元素,同时使用率在一半以上。
computesizes算完之后就调用resize把hash表和array都重新分配一次,lua的resize和redis相比简单很多,一次过就把元素都重新插入到新的hash表和数组里面去了。注意:由于插入元素会导致rehash,rehash会重新调整元素是放在数组还是放在hash表,所以一个元素无论原来是在数组还是hash表,rehash后都不能确定它是在数组还是hash表,这就说明了为啥对一个当作数组使用的table的指定key赋值后,ipairs遍历这个table的结果通常不靠谱。
table的查找:
/*
** main search function
*/
const TValue *luaH_get (Table *t, const TValue *key) {
switch (ttype(key)) {
case LUA_TNIL: return luaO_nilobject;
case LUA_TSTRING: 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_getnum(t, k);  /* use specialized version */
/* else go through */
}
default: {
Node *n = mainposition(t, key);
do {  /* check whether `key' is somewhere in the chain */
if (luaO_rawequalObj(key2tval(n), key))
return gval(n);  /* that's it */
else n = gnext(n);
} while (n);
return luaO_nilobject;
}
}
}
如果key是string就调用luaH_getstr,如果是整数就调用luaH_getnum,默认的情况下找到key所在的节点,然后找到节点指向的链表中这个key的位置返回。luaH_getstr和luaH_getnum其实也是这个过程,只不过对string和number的哈希算法不同,number也有可能会放在数组部分而已。
table的遍历:
table的遍历分为ipairs和pairs,ipairs遍历数组部分,pairs遍历整个table。ipairs遍历顺序就是从0开始一次加1往后遍历table的数组部分。pairs的遍历实际上是调用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++) {  /* try first array part */
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++) {  /* then hash part */
if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
setobj2s(L, key, key2tval(gnode(t, i)));
setobj2s(L, key+1, gval(gnode(t, i)));
return 1;
}
}
return 0;  /* no more elements */
}
算法一目了然,先查数组部分,然后查哈希表,找到当前key的下一个key。所以遍历的结果是先遍历数组部分,然后遍历哈希表部分,哈希表部分实际上就是把node顺序遍历一次。
分析到这里,已经基本知道原因了。number在lua里面是用double表示的,100001,100002,100003,100004,100005必定不能满足数组部分50%使用率的要求,所以都是放在哈希表里面。容纳这5个元素的哈希表的大小是8。lua的哈希number的哈希算法如下所示:
/*
** hash for lua_Numbers
*/
static Node *hashnum (const Table *t, lua_Number n) {
unsigned int a[numints];
int i;
if (luai_numeq(n, 0))  /* avoid problems with -0 */
return gnode(t, 0);
memcpy(a, &n, sizeof(a));
for (i = 1; i < numints; i++) a[0] += a[i];
return hashmod(t, a[0]);
}
其中hashmod是计算a[0]%(哈希表大小-1)然后取t中这个位置的元素。所以100005之所以排在第一位是因为hashmod中计算出来100005的位置比其他元素的位置靠前,所以他放在靠前的位置,这样在pairs的时候,会首先遍历到100005。至此谜底完全解开。
http://yulinlu.blog.163.com/blog/static/5881569820117351731462/


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Lua之math Lua之math函数:发布时间:2022-07-22
下一篇:
spf13-vim 显示neocomplete requires ...th Lua support发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap