415
Lua數據結構 — Table（三）
作者： 羅日健
前麵（一）、（二）裏麵其實已經把一些常用的數據類型（數值、布爾、字符串）說明了，這次要描述的是Table，Table在Lua裏是一種常用的數據類型，是Lua裏的精髓之一，其效率必須得到保證，而實現這種支持任意類型key和value的Table也是較為複雜的。
一， Table的設計思想：
1， 首先，講一下Lua要設計的Table是怎麼樣子的：
Lua就是想做這種支持任意類型的key和任意類型val的table，並且要高效和節約內存。
2， 基本的實現（基於鏈表的實現）：
基於鏈表的實現是最簡單的，其實map就可以了，這樣實現是最容易的。但當遇到很多key的數組（如t[0]、t[1]、t[2]。。這種數值索引大數組）時，明明可以用O(1)查找的，卻要O(n)去查找。
3， 區分數字key和其它類型的key
經過改良的Table，除了有key鏈表之外，還有一個數組array專門存放key為數值的val。但是這種情況下，要保證數值部分是連續且從0開始的，如果出現t[100000000] = 1，則把這個離散的數據放到鏈表中：
4， 利用哈希表再度優化
區分了array和head之後，始終有個問題，對於鏈表部分的數據，查找始終是O(n)的，有沒有辦法優化這部分代碼呢，在Lua裏，利用哈希表再對這部分的Node進行查找。
每次計算一個key的哈希值是非常快的，哈希後直接映射到hashlist的某個位置。這裏已經很接近Lua Table的最終設計，但是這種方法仍然有個弊端，哈希表的大小無法較好地估計，hashlist的長度可能是一個固定的長度，無法動態擴容。
5， 動態擴容的Table設計
下麵用例子展示一下動態擴容的Table設計
1） 如下圖，現在初始狀態下，隻有[0]被使用了，裏麵放著A，其它都是空：
2） 現在要插入一個新的元素B，計算出其哈希值是0，即是說應該插入到節點[0]。這個時候發現節點[0]已經被使用，則會分配最後一個空閑塊lastfree給這個元素B，然後node[0]的next指向node[3]，即：
3） 然後再插入一個新的nodeC，計算出其哈希值是3，即是說應該插入到node[3]。這個時候發現node[3]已經被使用，但是元素B的哈希值是0，即本來應該插入到node[0]的，於是把node[3]的內容移到lastfree，然後再在node[3]插入新的nodeC，即：
4） 這是如果再往Table插入一個元素D，那麼必然最後一個空閑塊會被使用完，那麼就會把nodelist的大小擴大一倍，並且重新計算每個元素的哈希值並重新插值，可能的結果如下：
在最後一步的重新計算哈希值，不僅重新計算nodelist的哈希值，也會重新計算arraylist的哈希值，arraylist也是會動態擴大的，這就是lua中table的設計。
二， Lua裏麵的實現：
Table相關數據結構關係圖如下：
上圖中有Table、Node、TKey這3個數據結構，不用急，我們先從簡單的入手，看看Node數據結構：（lobject.h 332-335）
Node就是設計思想裏的key、value數據結構，包含ikey和ival兩個成員，這2個成員很好理解，一個就是table的key，另一個就是這個key的value。ival是一般值的TValue類型，而ikey的TKey類型的。可以看到Node並沒有next指針，其實它把next指針藏在TKey下麵了，請看TKey數據結構：（lobject.h 319-329）
可以看到TKey其實是一個支持TValue的數據結構外，還多了一個next指針。這個next指針就是用作同一個hash值下衝突時的鏈表指針。明白了Node結構之後，接下來看看Table數據結構：（lobject.h 338-348）
每個字段意義如下：
- CommonHeader：與TValue中的GCHeader能對應起來的部分
- flags：用於元表元方法的一些優化手段，一共有8位用於標記是否沒有某個元方法
- lsizenode：用於表示node的長度，如下圖所示
node成員其實是上麵討論的hashlist成員，是一個固定長度大小的數組，但是lsizenode的數據類型是lu_byte，隻有一個字節長，表示範圍隻有0~255，一般數組大小都會很大，所以這裏lsizenode用於表示整體長度的log2值，同時也表明了，hashlist的長度是2的冪，每次增長都會×2.
- metatable：元表指針
- array：這個成員就是上麵討論的array，用於給數值的索引
- node：上麵提到的hashlist成員
- lastfree：lastfree就是鏈表的最後一個空元素
- gclist：用於gc的，以後會有專門對GC的詳細討論
- sizearray：array數組的大小
離散數值key存儲的實現：
在luaH_getnum（ltable.c 432-449）函數中，實現了對數值key的獲取，可以看到第一個判斷：
即如果key在sizearray的範圍內，則直接用t->array成員來存儲，如果不是則計算key的哈希值，然後放到node裏。
還有一種情況，就是如果對某個連續數值的table賦值：t[2] = nil，那是否從2到後麵的key都會馬上放到哈希表裏呢？答案是否定的，不會馬上做，等到做完gc後，會進行table的resize。
Table的Rehash（重新計算大小）：
1） rehash的時機：
在newkey(ltable.c 399-429)函數中可以看到
n是hashlist中的一個沒使用的節點，當沒有空餘節點的時候，就會調用rehash進行grow table，這個可以參考本文上麵說到的動態擴容章節。
2） rehash函數(ltable.c 333-349)
table的這個rehash操作，代碼不多，但是卻十分複雜，接下來我們分解一下它所做的事：
a． 計算使用數值作為key的元素數量na、計算實際為數組申請的空間大小nasize、計算hashlist的元素數量nhsize。 這裏有點模煳，na和nasize的關係，下麵寫個例子更好說明一下：
沒錯，nasize一定要是2的冪，computesizes(ltable.c 189-208)通過特定算法，高效地計算出實際要使用的數組大小，舉下麵例子說明一下：
lua其實是用了一個條件來決定數組部分大小的：
如果數值key的元素個數大於對應個數冪大小的一半，則生成對應冪長度的數組鏈表。
很抽象，還是拿上麵的例子來說明：
整體算法如上圖所示，還是挺精致的，不太懂用語言描述，可以想象一個元素如果擁有tbl[10]到tbl[50]，那麼這個arraylist的長度是64，中間可能會多生成1~10和50~64這個區間的數組，但是這種方法既能動態擴容，又能提升效率，犧牲一點點還是值得的。
b． resize(ltable.c 300-327)函數，根據前麵計算出來的nasize和nhsize，realloc對應數組的大小，並對其中的元素重新計算哈希值和賦值。
哈希的實現：
主要可以看到mainposition（ltable.c 96-113）函數，用於計算哈希然後快速定位到某個Node上麵，可以看到它根據不同類型有不同的哈希計算：
元表的實現：
元表是metatable，可以綁定metatable的對象在lua中隻有table和userdata。這裏討論的是table中的metatable，在userdata中的其實也一樣。我們看到Table數據結構裏的struct Table* metatable指針，下麵以index操作為例，其它的話其實也一樣：
看luaV_gettable(lvm.c 108-131)，我們可以看到在取一個對應key後會有判斷：
這個判斷其實就是看看返回結果如果是空，就會去取元表的__index對象，取回來之後，下次循環就再次用這個tm來取key，如果在tm上找不到對應key，而且tm又有metatable，就會一直循環下去。
這裏fasttm做了一些優化，其實就是先用h->metatable的flags成員去判斷是否存在__index元方法，如果不存在馬上返回。flags隻有8位，用於存儲常用的元操作，可以在ltm.h 18-37看到，快速操作的常用元方法是index 、newindex、gc、mode、__eq，說明flags還有3位沒用到。
循環有個MAXTAGLOOP，這裏其實限製了元表的深度不能超過100（其實超過5個深度的元表已經很恐怖了）。元操作對象的獲取方法其實是luaTgettm（ltm.c 50-58）和luaTgettmbyobj（ltm.c 61-74）
總結：
對於Table，還有個弱表的特性，這個留待在說gc的時候再詳細討論。其實Table的實現還是挺多細節的，不過主要的思想和處理都說了（除了gc）。
最後更新：2017-04-03 08:26:25