深度剖析Lua Table的運作方式

前言：本篇基于Lua-5.3.6源碼并配合《Lua 解釋器構建：從虛擬機到編譯器》一書進行Table的運作解讀。

一、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 */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;

如圖：

CommonHeader:? ?GC的公共頭部，標識是GC管理的對象，Table也是一個GC對象。

flags：標記缺失的元方法。比如：flags&(1<<TM_INDEX)為真表示缺少_index元方法。

lsizenode：哈希表大小的log2值，一來方便表示更大的存儲容量，二來哈希表的擴容是成2倍增長的。

arraysize：數值的大小。

array：數組部分的指針。

node：哈希表部分的指針。

lastfree：哈希表空閑位置標記（指向最后一個空閑節點）

metatable：Table的元表，用來定義特定對象的元方法（如 __index、__newindex、__add 等）。

gclist：GC鏈表指針。

可以看到Table實際上是由兩部分組成，數組部分和哈希表部分。

二、鍵值的哈希計算

在完成了對key的哈希運算以后，就需要根據得到的哈希值，將其換算成表結構node數組的索引值，計算的公式如下。

index=hash_value&( $2^{lsizenode}-1$ )

這里-1是希望hash的低位全是1。

舉例：假設有個字符串為"table"，計算它在大小為8的哈希表的索引。

假設根據方法已經得到哈希值，01101011 00100100 10001101 00101100

lsizenode= $\log_{2}8$ =3

那最終相與只看后四位的結果? 1100&0111=0100=4

key為“table"的node，將會被定位到hash[4]的位置上

三、Table查找元素

分兩種情況，key值是int和非int

a.key是int

1）令被查找元素的key值為k，表array數組的??為arraysize。

2）判斷被查找元素的key值是否在數組范圍內（即k≤arraysize是否成?）。

3）若key值在表的數組范圍內，則返回array[k-1]，流程終?。

4）若key值不在表的數組范圍內，計算key值在哈希表中的位置，計算?式為

index=k&( $2^{lsizenode}-1$ )，然后以hash[index]節點為起點，查找key值與k相等的node，如果沒找到則返回nil。

b.key是非int

1）計算被查詢元素的key值（記為k）的哈希值，記為key_hash。

2）計算key值在哈希表中的位置，計算?式為index=k&( $2^{lsizenode}-1$ )，然后以 hash[index]節點為起點，查詢key值與k相等的node，如果沒找到則返回nil。

四、Table更新和插入

1）假設要新建的key值為k，計算k的哈希（hash）值，記為k_hash

2）計算key值在哈希表的索引，計算?式為index=k_hash &（2lsizenode-1）。

3）如果hash[index]的value值為nil，將其的key值設置為k的值，并返回value_對象指針，供調 ?者設置。

4）如果hash[index]的value值不為nil，需要分以下兩種情況處理。

a. 計算node key的hash值，重新計算它的索引值。如果計算出來的索引位置不是hash[index]，那么lastfree不斷左移，直?找到?個空閑的節點。將其移動到這?，修改鏈表關系，令其上? 個與??索引值相同節點的next值指向??（如果存在的話）。新插?的key和value設置到 hash[index]節點上。

b. 計算node key的hash值，重新計算它的索引值，如果計算出來的索引位置就是hash[index]，那么lastfree不斷左移，直?找到?個空閑的節點。將新插?的key和value值設置到這個節點上，并調整鏈表關系，將hash[index]的key值的next值指向新插?的節點。

舉例:

向表插??個 key值為5、value值為“xixi”的元素。

由于key值5超出了數組的??范圍，那么程序?先會嘗試去哈希表中查找，可以得到最終index的值為1。hash[1]的key值為nil，與要更新元素的key值不相等，于是觸發了插?操作。由于hash[1]的key和value值均是nil，因此可以將該元素直接設置到這?。

向表插??個 key值為13、value值為“manistein”的元素。

根據公式算出index為1，因為hash[1]的value 域的值為“xixi”、key值為5，與k值13并不相等，于是便發?了哈希碰撞。key值5經過轉換運算得到的哈希表index的值為1，此時它就在這個位置上，因此key值為13的新元素需要被移?。 lastfree指針向左移動，并且將key值為13、value值為“manistein”的元素賦值到lastfree指向的位置上（即hash[3]的位置上），并且將hash[1]的key的next指向lastfree指針所指的位置。

注意：這里的next值指的是與當前index相隔的距離，而不是下一個節點的index值，因為這里的哈希表本身是個鏈表，存index值沒有意義

向表插??個 key值為7、value值為“wu”的元素。

經過計算得到其對應的hash表 index值為3，此時hash[3]已經被占?。此時需要計算占據在這?的元素的key值，其真實對應的hash表index其實是1，因為hash[1]被占?才被移動到這?。因為這個元素計算得到的index 與當前位置并不匹配，因此lastfree指針需要繼續向左移動，并將key值為13的元素遷移到這 ?，并更新其前置節點的next域。最后將key值為7的元素，賦值到hash[3]的位置上.

五、Table擴容機制

更新和插?的操作，均是在哈希表空間充?的情況下進?的，當哈希表已滿，且?有新的元素要插?哈希表時，將觸發表的resize操作。首先調整的是數組的大小

1）統計要調整??的Lua表、數組和哈希表中的有效元素（值類型不為nil的元素）的總數

2）創建?個int類型的數組，它的??為32，將其命名為nums。nums [i]表示的信息量?較 ?。?先i表示?個數值區間，這個區間是（ $2^{i-1}$ ， $2^{i}$ ]

3）統計數組的分布情況，假設arraysize是66，且每個Value都不為空，那么此時它的分布情況是

即 $66=2^{0}+2^{1}+2^{2}+2^{3}+2^{4}+2^{5}+3$

4）統計哈希表元素在nums [32]中不同區間的分布情況，偽代碼如下

//lsizenode是Table數據結構中衡量哈希表長度的變量
for(int i=0;i<pow(2,lsizenode);i++){if(hash[i].key!=null&&isInt(hash[i].key)){int k=ceillog2(hash[i].key);nums[k]++;}
}//找到hash key值在Nums數組中的下標
void ceillog2(int hashKey){for(int i=0;i<32;i++){if(pow(2,i)>=hash.key){return i;}}
}

5）判斷新插?元素new_element的key值是否為整類型，如果是則令

nums [FindIndex (new_element.key)]++。

6）完成數組nums的統計之后，根據nums計算新的數組??。在數組??范圍內，值不為nil的元素要超過數組??的?半，其計算公式如下。

int asize=0;
for(int i=0;i<32;i++){asize+=nums[i];if(asize>pow(2,i)/2){sizearray=pow(2,i); //sizearray是Table中衡量數組大小的變量}
}

7）計算在數組??范圍內有效元素的個數，記為array_used_num。

8）當數組???原來?時，擴展原來的數組到新的??，并將哈希表中key值≤arraysize，且 >0的元素轉移到數組中，并將哈希表??調整為ceillog2（total_element-array_used_num），同時對每個node進?重新定位位置。

數組擴大的簡單理解：數組部分加入哈希表里面可以轉移到數組里的鍵值對，此時數組部分超過一半都是不為nil。

示例：

9）當數組???原來?時，縮?原來的數組到新的??，并將數組中key值超過數組??的元素轉移到哈希表中。此時哈希表??調整為ceillog2（total_element-array_used_num），同時對每個node進?重新定位位置。

數組縮小的簡單理解：數組不連續的key轉移到哈希表，此時數組超過一半都是nil。

基于8-9至此我們可以推理到一個二級結論：

哈希表里最新的int的類型key值一定大于數組長度（sizearray）。

這個結論對于后續Table的遍歷起到了一定的理論依據。

六、Table遍歷

Lua提供了luaH_next函數來進?迭代操作，函數申明如下

方法中關鍵調用是findIndex方法，5.3源碼如下

/*
** returns the index of a 'key' for table traversals. First goes all
** elements in the array part, then elements in the hash part. The
** beginning of a traversal is signaled by 0.
*/
static unsigned int findindex (lua_State *L, Table *t, StkId key) {unsigned int i;if (ttisnil(key)) return 0;  /* first iteration */i = arrayindex(key);if (i != 0 && i <= t->sizearray)  /* is 'key' inside array part? */return i;  /* yes; that's the index */else {int nx;Node *n = mainposition(t, key);for (;;) {  /* check whether 'key' is somewhere in the chain *//* key may be dead already, but it is ok to use it in 'next' */if (luaV_rawequalobj(gkey(n), key) ||(ttisdeadkey(gkey(n)) && iscollectable(key) &&deadvalue(gkey(n)) == gcvalue(key))) {i = cast_int(n - gnode(t, 0));  /* key index in hash table *//* hash elements are numbered after array ones */return (i + 1) + t->sizearray;}nx = gnext(n);if (nx == 0)luaG_runerror(L, "invalid key to 'next'");  /* key not found */else n += nx;}}
}

細分key值四種情況：