Lua數據結構 — TString（二）

存儲lua裏麵的字符串的TString數據結構:（lobject.h 196-207）

其它結構中也會有L_Umaxalign dummy這個東西，來看看L_Umaxaliagn:

從字麵意思上就是保證內存能與最大長度的類型進行對齊，事實上也是做這件事，這裏感覺lua想給各種不同設備做一種嵌入式腳本，這裏要保證與最大的長度對齊能保證CPU運行高效不會罷工。

tsv才是TString的主要數據結構：

1. CommonHeader：這個是和GCObject能對應起來的GCheader
2. reserved：保留位
3. hash：每個字符串在創建的時候都會用有衝突的哈希算法獲取哈希值以提高性能
4. len：字符串長度

哈希是lua裏一個很重要的優化手段，具體的哈希算法相關知識在文章最後會補充說明一下，字符串的hast表放在L->l_G->strt中，這個成員的類型是stringtable，我們再來看看stringtable數據結構：（lstate.h 38-42）

stringtable結構很簡單：

1. hash：一個GCObject的表，在這裏其實是個TString*數組
2. nuse：已經有的TString個數
3. size：hash表的大小(可動態擴充)

接下來看看stringtable是怎麼動態調整大小的:

1 動態擴充stringtable：(lstring.c 60-70)

每次newlstr的之後，都會判斷nuse是否已經大於table的size，如果是的話就會重新resize這個stringtable的大小為原來的2倍。

2 動態濃縮stringtable：(lgc.c 433-436)

在gc的時候，會判斷nuse是否比size/4還小，如果是的話就重新resize這個stringtable的大小為原來的1/2倍。

3 resize算法：(lstring.c 22-47)

resize時，需要根據每個節點的哈希值重新計算新位置，然後放到newhash裏。

字符串在哪裏？ 看完TString和stringtable，大家都沒有發現究竟字符串放在哪裏，從內存上看其實字符串直接放在了TString後麵，這樣還能省掉一個成員：(lstring.c 56)

性能問題：

在這裏說一點lua的性能問題，雖然不在這個主題的討論範圍。由上麵可以知道lua的字符串是帶hash值的，所以我們拿著一個字符串去做比較、查詢、傳遞等操作都是非常高效的。

但是我們也可以看到每次創建一個新的字符串都會做很多操作，所以這裏不建議頻繁做字符串創建、連接、銷毀等操作，最好能緩存一下。

補充：字符串的哈希算法：

常用的字符串哈希函數比較如下：

其中數據1為100000個字母和數字組成的隨機串哈希衝突個數。數據2為100000個有意義的英文句子哈希衝突個數。數據3為數據1的哈希值與1000003(大素數)求模後存儲到線性表中衝突的個數。數據4為數據1的哈希值與10000019(更大素數)求模後存儲到線性表中衝突的個數。

經過比較，得出以上平均得分。平均數為平方平均數。可以發現，BKDRHash無論是在實際效果還是編碼實現中，效果都是最突出的。APHash也是較為優秀的算法。DJBHash,JSHash,RSHash與SDBMHash各有千秋。PJWHash與ELFHash效果最差，但得分相似，其算法本質是相似的。

在Lua中使用到的是JSHash算法：

具體JS Hash算法的衝突性解決和性能上麵，我也不懂，具體要找paper看看，但是從數據比較上看，JSHash是屬於較好的算法，可也有比JSHash算法更好的字符串哈希算法。