|
最近遇到一件很郁闷的事情，游戏里面我老是当队长！后来发现是因为队伍里每个人的数据会以游戏的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。至此谜底完全解开。 |
|
|
