本文來自《Lua設計與實作》的閱讀筆記，推薦Lua學習者可以購買一本，深入淺出講解lua的設計和實作原理，很贊，哈哈
Lua中對于表的設計，是基于數組和散清單，和其他語言不同，對于數組的下标是從1開始的，對于散清單而言，隻要其鍵值補位nil，都可以存儲在其中。
一、table的基本類型定義
首先看看table的資料定義，參考源碼lobject.h
CommonHeader, 參看專欄前面的文章；
flags 這是一個lua的byte類型的資料，用于表示表中提供了哪些元方法，比如是否提供了元方法_index，該資料最開始設定為1，如果進行查找一次，比如_index，如果存在，這該元方法對應的flag bit設定為0，在下一次查找的時候，隻需要比較這個bit即可，對應的元方法在ltm.h中
lsizenode，為散清單的大小，必定為2的幂對應的數字；
metatable，該table的元表；
array，該table的數組的指針
node, 該table的散清單的起始位置的指針；
lastfree, 該散清單的最後位置的指針
gclist， gc相關的連結清單
sizearray， 數組的大小，不一定為2的幂對應的數字
對于node資料，類似于其他語言中的字典設計\hash設計，就是一個鍵值對集合，其定義為：
需要提一下的是對于key的設計采用的是union，也就是說Lua的散清單的key，可以為nk對應的struct，也可以是TValue類型
二、table相關的操作的實作原理
1、查找算法的實作原理
借用原文的僞代碼：
if 輸入的key為整數 && key >= 0 && key <= 數組的大小
嘗試在數組部分查找
else 在散清單部分查找
計算出該key的散列值，據其查找對應的node所在散清單中的位置，然後周遊其對應的連結清單，查找是否有該key對應的元素
舉例：
local t = {}
t[1] = 0
t[100] = 0
那麼1是在數組中查找，100就是在散清單中去查找了（100大于數組的len）
2、新增元素的實作原理
給lua中添加新元素的時候，會有可能觸發重新配置設定table中的數組和散清單，其本質來自于散清單的rehash（由于lua對于下标超過數組的大小的數字，都會存儲在散清單部分去，是以數組部分的插值不會觸發rehash）
散清單的組織，就是多個mainposition，每個單獨的mainposition會對應一個資料連結清單，當插入一個key的時候，會調用luaHset\luaH_setnum\luaH_setstr，來獲得該key對應的TValue指針，如果沒有，則調用内部的newkey函數來配置設定一個新的key：
基本的實作過程看源代碼寫的比較詳細，這兒說一下rehash部分的操作，在ltable.c中：
1) nums中存放的是元素的數量
2）分表周遊數組(numusearray)和散清單(numusehash)，統計更新nums中的數量大小
3) 重新計算數組和hash部分的大小，數組大小的計算規則：逐個周遊nums數組，獲得其範圍區間内所包含的整數數量大于50%的最大索引，作為rehash後的數組大小，這個索引值來自與computesizes函數：
可能看了會有點迷糊，那我就用大白話說一下吧：
首先nums數組在統計後，每個下标對應的是處于目前2^(i -1) - 2^i中的元素的個數，然後不斷的累加計算，求得滿足 sum > 2^n/2的最大下标值(這個下标值是nums數組中的)
是以，在不同的rehash階段，table中的同一個key可能會在數組部分和散清單部分交替出現，也是可能的。
由于rehash會帶來較大的性能消耗，是以一般都盡量避免，比如在建立表的時候，就采用預填充的算法
3、取長度算法的原理
如果table中元表沒有重載len方法，則調用的是luaH_getn方法，其基本的僞代碼為：
if 表中存在數組部分：
初始化i = 0, j = sizearray
while(j - i > 1){
m = (j + i)/2
if(array[m-1] == nil)
j = m
else
i = m
}
return i
else
查找表中散清單長度，算法同數組部分
對于表中隻有散清單的時候，其實質就是對鍵值為正整數的部分進行長度操作，如果既有數組，又有散清單，則優先對數組部分進行長度操作