1.Table的幾個小知識點
- table使用關(guān)聯(lián)數(shù)組惧盹，我們可以使用任意類型的值來作為數(shù)組的索引（不能使用nil）
- table沒有固定的大小乳幸，可以動態(tài)的添加元素
2.table的構(gòu)造
//初始化表
//1
mytable = {}
//2
_mytable = {a=100,b="123"}
//使用.號賦值
_mytable.a = 110
//使用索引賦值
_mytable["c"]=139
思考一下：如果現(xiàn)在定義了一個table a，將table a賦值給table b钧椰，此時它們的內(nèi)存情況是什么樣呢反惕？
ab都會指向同一個內(nèi)存塊，如果a設(shè)置為nil演侯，b依舊能訪問該內(nèi)存塊的元素姿染，直到b設(shè)置為nil后，Lua的垃圾回收機制會清理相應(yīng)的內(nèi)存秒际。所以當(dāng)b在更改table內(nèi)的值后悬赏，a再去訪問的時候，值也是改變的娄徊。
table的for循環(huán)寫法
for k,v in pairs(mytable) do
print(i,v)
end
3. 從table結(jié)構(gòu)體分析table屬性
typedef struct Table {
CommonHeader;
lu_byte flags; /* 1<<p means tagmethod(p) is not present */
lu_byte lsizenode; /* 以2的lsizenode次方作為哈希表長度 */
struct Table *metatable /* 元表 */;
TValue *array; /* 數(shù)組 */
Node *node; /* 哈希表 */
Node *lastfree; /* 指向最后一個為閑置的鏈表空間 */
GCObject *gclist;
int sizearray; /* 數(shù)組的大小 */
} Table;
先解釋一下上面的各個變量
- CommonHeader 為所有可回收資源提供標(biāo)記頭
- lu_byte其實是 typedef unsigned char lu_byte闽颇，lu_byte flags用于表示表中提供了哪些元方法（元方法是什么？我們下面和元表一起解釋）
- lu_byte lsizenode 它的值就是表的長度寄锐，但是散列表大小的擴增一定是2的冪兵多，如果散列桶數(shù)組要擴展的話尖啡，也是每次在原大小的基礎(chǔ)上乘以2的形式擴展。
- struct Table *metatable 也就是元表剩膘。
3.1 元表
3.1.1 為什么要用元表
在table中衅斩，我們無法對兩個table之間進行操作，比如：table a+ table b怠褐。為了解決這個問題畏梆，就引入了元表的概念，它允許我們改變table的行為奈懒。
3.1.2 元表的操作流程
當(dāng)我們在進行表a+b的時候：
- 檢查兩者中是否至少有一者是有元素
2.查找是否有"_add"字段奠涌，如果有，就取得它的值磷杏，此時這個值就是我們的元方法溜畅，里面編寫了add函數(shù)
其實逼逼了這么多，我覺得元表和元方法其實就相當(dāng)于重載极祸，比如_add慈格，我們就是重載了+操作符
也可以將它理解成事件驅(qū)動，元表中的鍵對應(yīng)著不同的事件名贿肩，關(guān)聯(lián)的值是元方法峦椰，元方法里就是我們事件對應(yīng)的操作。
繼續(xù)接上面的分析
- TValue *array是指向數(shù)組的指針
TValue是一個結(jié)構(gòu)體汰规，里面保存著TValuefields汤功，它是一個宏定義，包含value和int值溜哮，而value是一個聯(lián)合體滔金，它可以是指針、數(shù)字等等茂嗓。
typedef struct lua_TValue {
TValuefields;
} TValue;
TValuefields:
#define TValuefields Value value; int tt
Value:
typedef union {
GCObject *gc;
void *p;
lua_Number n;
int b;
} Value;
- Node *node 是指向該表的散列桶數(shù)組起始位置的指針
3.2 Node類型
每個Node都是一個鍵值對,里面包含了key和value餐茵。tvk是key的值，但是當(dāng)我們出現(xiàn)hash沖突述吸，此時lua的hash算法比較特殊忿族，一般情況下，我們的hash算法都是根據(jù)key算出hash蝌矛，然后如果有沖突的話道批，就放在改位置的鏈表上。而lua不同入撒，當(dāng)它出現(xiàn)hash沖突的時候隆豹，會在hash表中找到一個空的位置x，來存放key茅逮，并且讓沖突處的節(jié)點的nk.next指向x璃赡。
這意味著什么呢判哥？發(fā)生沖突我們無需重新分配空間來存儲沖突的key，而是利用hash表上未用過的空白處來存儲碉考。剛才我們將key放在了空位置x塌计，如果此時存在另一個key2，它算出的hash值是空位置x豆励，而我們剛才的key只是因為hash沖突了夺荒，占用了其他key的位置瞒渠，這個時候我們就講key2放在x上良蒸，將key再放到另一個空白處。
忍不住想總結(jié)一波table的實現(xiàn)伍玖，和上面我們的Node類型進行對照
3.3 table的實現(xiàn)
lua的table其實由數(shù)組段和hash兩部分組成嫩痰，當(dāng)你的key值不會過于離散的時候，lua就會將它存儲在數(shù)組段（也就是下圖的array）窍箍，反正會存儲在hash段（也就是下圖的node）串纺，這個分割線是以數(shù)組段的利用率不低于50%為準(zhǔn)。hash段采用閉散列的算法椰棘，它將有沖突的key存儲在空閑槽中纺棺，而不額外分配內(nèi)存。
在我們table結(jié)構(gòu)體中邪狞，array和sizearray都是表示數(shù)組段祷蝌。
而lsizenode和node，lastfree是表示hash段帆卓。node指向hash表的起始位置巨朦，lsizenode是log2(node指向的哈希表的節(jié)點數(shù)目)，lastfree指向node里面最后一個未使用的節(jié)點（因為我們在hash沖突的時候剑令，是從后往前查找未使用的節(jié)點糊啡，lastfree存儲最后一個未使用節(jié)點就可以方便查找）
如果此時hash表中已經(jīng)沒有空格了，那么lua就會resize這個hash表（等會再談lua的動態(tài)擴增）
typedef union TKey {
struct {
TValuefields;
struct Node *next; /* for chaining */
} nk;
TValue tvk;
} TKey;
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
4. table的創(chuàng)建吁津、查找棚蓄、動態(tài)分配
4.1 table的創(chuàng)建
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;
}
lua創(chuàng)建新表的時候先為新表分配內(nèi)存Table * t = luaM_new(L, Table)，然后將表連接到gc上并設(shè)置標(biāo)志位luaC_link(L, obj2gco(t), LUA_TTABLE)碍脏，然后初始化一些必要的屬性梭依，使用setarrayvector為數(shù)組段分配內(nèi)存，setnodevector為hash部分分配內(nèi)存潮酒，最后返回表指針睛挚。
4.2 table的查找
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;
}
}
}
table的查找會根據(jù)key進行判斷，如果key為空就直接返回空急黎，key為字符串就調(diào)用luaH_getstr(t, rawtsvalue(key))扎狱，key為數(shù)字則根據(jù)它是否整數(shù)調(diào)用luaH_getnum(t, k)侧到，否則，計算出key的位置淤击，遍歷table的node節(jié)點匠抗，找到對應(yīng)鍵所在的節(jié)點返回。
因為key為數(shù)字比較特殊污抬，所以研究一把luaH_getnum函數(shù)的實現(xiàn)
const TValue *luaH_getnum (Table *t, int key) {
/* (1 <= key && key <= t->sizearray) */
if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
return &t->array[key-1];
else {
lua_Number nk = cast_num(key);
Node *n = hashnum(t, nk);
do { /* check whether `key' is somewhere in the chain */
if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
return gval(n); /* that's it */
else n = gnext(n);
} while (n);
return luaO_nilobject;
}
}
如果key大于等于1汞贸，小于數(shù)組的長度，則從數(shù)組中取出對應(yīng)的鍵值印机，否則利用hashnum找到key對應(yīng)的node位置矢腻，遍歷node鏈表，返回對應(yīng)的值
4.3 table的賦值
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);
}
dummynode是帶頭結(jié)點的指針射赛。
往table中插入新值多柑，先檢測key的主位置（main position）是否為空，主位置就是key的哈希值在node中的位置楣责。
如果主位置為空竣灌，就直接插入，主位置不為空秆麸，檢查占領(lǐng)該位置的key的主位置是不是在這個地方初嘹，如果不在，則將該key移動到其他空閑位置沮趣，將要插入的key插入到這個位置中屯烦。如果在這個地方，則將要插入的key插入到一個空槽中兔毒。
如果找不到空閑位置放新鍵值漫贞，就rehash函數(shù)，擴增hash表的大小育叁，再找出新位置迅脐，再調(diào)用luaH_set把要插入的key插入到新的哈希表中，直接返回LuaH_set的結(jié)果豪嗽。
4.4 table的動態(tài)增長
4.4.1 rehash
//加入key谴蔑，重新分配hash與array的空間
static void rehash (lua_State *L, Table *t, const TValue *ek) {
int nasize, na;//nasize前期累計整數(shù)key個數(shù)，后期做為數(shù)組空間大小龟梦，na表示數(shù)組不為nil的個數(shù)
int nums[MAXBITS+1]; /* 累計各個區(qū)間整數(shù)key不為nil的個數(shù)隐锭，包括hash, 例如nums[i]表示累計在[2^(i-1)，2^i]區(qū)間內(nèi)的整數(shù)key個數(shù)*/
int i;
int totaluse;//記錄所有已存在的鍵计贰，包括hash和array钦睡，即table里的成員個數(shù)
for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* 初始化所有計數(shù)區(qū)間*/
nasize = numusearray(t, nums); /* 以區(qū)間統(tǒng)計數(shù)組里不為nil的個數(shù)，并獲得總數(shù)*/
totaluse = nasize; /* all those keys are integer keys */
totaluse += numusehash(t, nums, &nasize); /* 統(tǒng)計hash表里已有的鍵躁倒，以及整數(shù)鍵的個數(shù)已經(jīng)區(qū)間分布*/
//如果新key是整數(shù)類型的情況
nasize += countint(ek, nums);
//累計新key
totaluse++;
/* 重新計算數(shù)組空間 */
na = computesizes(nums, &nasize);
/* 重新創(chuàng)建內(nèi)存空間, nasize為新數(shù)組大小
//totaluse - na表示所有鍵的個數(shù)減去新數(shù)組的個數(shù)荞怒，即為新hash表需要存放的個數(shù) */
resize(L, t, nasize, totaluse - na);
}
4.2 resize
static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
int i;
int oldasize = t->sizearray;
int oldhsize = t->lsizenode;
Node *nold = t->node; /* 保存當(dāng)前的hash表洒琢，用于后面創(chuàng)建新hash表時，可以重新對各個node賦值*/
if (nasize > oldasize) /* 是否需要擴展數(shù)組 */
setarrayvector(L, t, nasize);
/* 重新分配hash空間*/
setnodevector(L, t, nhsize);
if (nasize < oldasize) { /* 小于之前大小褐桌，即有部分整數(shù)key放到了hash里 */
t->sizearray = nasize;
/* 超出部分存放到hash表里*/
for (i=nasize; i<oldasize; i++) {
if (!ttisnil(&t->array[i]))
setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]);
}
/* 重新分配數(shù)組空間衰抑，去掉后面溢出部分*/
luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
}
/* 從后到前遍歷，把老hash表的值搬到新表中*/
for (i = twoto(oldhsize) - 1; i >= 0; i--) {
Node *old = nold+i;
if (!ttisnil(gval(old)))
setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
}
//釋放老hash表空間
if (nold != dummynode)
luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */
}
