概述
Lua完全采用8位編碼，Lua字符串中的字符可以具有任何數(shù)值編碼，包括數(shù)值0。也就是說，可以將任意二進制數(shù)據(jù)存儲到一個字符串中。Lua的字符串是不可變的值（immutable values）。如果修改，實質(zhì)上是新建一個字符串。根據(jù)上文《Lua中數(shù)據(jù)類型的源碼實現(xiàn)》中知道，在Lua中，字符串是自動內(nèi)存管理機制所管理的對象，并且由聯(lián)合體TString來實現(xiàn)存儲字符串值的。下面將通過Lua 5.2.1的源碼來看字符串的實現(xiàn)以及總結(jié)了在Lua中使用字符串的注意事項。
源碼實現(xiàn)
首先來看字符串對應(yīng)的數(shù)據(jù)結(jié)構(gòu)TString，其源碼如下（lobject.h）：
410 /* 411 ** Header for string value; string bytes follow the end of this structure 412 */ 413 typedef union TString { 414 L_Umaxalign dummy; /* ensures maximum alignment for strings */ 415 struct { 416 CommonHeader; 417 lu_byte extra; /* reserved words for short strings; "has hash" for longs */ 418 unsigned int hash; 419 size_t len; /* number of characters in string */ 420 } tsv; 421 } TString; 對這個聯(lián)合體定義，有幾點值得說明：
I、聯(lián)合體TString中成員L_Umaxalign dummy是用來保證與最大長度的C類型進行對齊，其定義如下（llimits.h）：
48 /* type to ensure maximum alignment */ 49 #if !defined(LUAI_USER_ALIGNMENT_T) 50 #define LUAI_USER_ALIGNMENT_T union { double u; void *s; long l; } 51 #endif 52 53 typedef LUAI_USER_ALIGNMENT_T L_Umaxalign; 在其他可會回收的對象（比如table）的實現(xiàn)中，也可看到這個聯(lián)合體成員，這樣做的目的是通過內(nèi)存對齊，加快CPU訪問內(nèi)存的速度。
II、聯(lián)合體中成員tsv才是真正用來實現(xiàn)字符串的。其中成員CommonHeader用于GC，它會以宏的形式在所有的可回收對象中定義，代碼如下（lobject.h）：
74 /* 75 ** Common Header for all collectable objects (in macro form, to be 76 ** included in other objects) 77 */ 78 #define CommonHeader GCObject *next; lu_byte tt; lu_byte marked
這個宏對應(yīng)的結(jié)構(gòu)體形式如下（lobject.h）：
81 /* 82 ** Common header in struct form 83 */ 84 typedef struct GCheader { 85 CommonHeader; 86 } GCheader; 結(jié)構(gòu)體GCheader在通用的可回收對象union GCObject的定義中有用到。
III、lu_byte extra對于短字符串，用來記錄這個字符串是否為保留字，對于長字符串，可以用于惰性求Hash值；unsigned int hash成員是字符串對應(yīng)的Hash值（在后面會具體講Lua是怎么計算字符串的Hash值的）；size_t len用來表示字符串的長度。
IV、上面的結(jié)構(gòu)體只是描述了一個字符串的結(jié)構(gòu)，真正的字符串數(shù)據(jù)保存是緊隨在結(jié)構(gòu)體后面保存。
在Lua5.2.1之前，不區(qū)分字符串長和短的字符串，所有的字符串保存在一個全局的Hash表中，對于Lua虛擬機來說，相同的字符串只有一份數(shù)據(jù)，從Lua5.2.1開始，只是把短的字符串字符串（當前定義是長度小于等于40）放在全局Hash表中，而長字符串都是獨立生成，同時在計算Hash值時，引入一個隨機種子，這樣做的目的防止Hash Dos——攻擊者構(gòu)造出非常多相同Hash值的不同字符串，從而降低Lua從外部壓入字符串進入全局的字符串Hash表的效率。下面是Lua5.2.1中，生成一個新字符串的步驟，其相應(yīng)的代碼都在lstring.c中：
（1）若字符串長度大于LUAI_MAXSHORTLEN（默認值是40），則是長字符串，直接調(diào)用創(chuàng)建字符串接口的函數(shù)createstrobj（當然字符串的長度需要能保存在成員size_t len中，否則直接返回），代碼如下（lstring.c）：
95 /* 96 ** creates a new string object 97 */ 98 static TString *createstrobj (lua_State *L, const char *str, size_t l, 99 int tag, unsigned int h, GCObject **list) { 100 TString *ts; 101 size_t totalsize; /* total size of TString object */ 102 totalsize = sizeof(TString) + ((l + 1) * sizeof(char)); 103 ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; 104 ts->tsv.len = l; 105 ts->tsv.hash = h; 106 ts->tsv.extra = 0; 107 memcpy(ts+1, str, l*sizeof(char)); 108 ((char *)(ts+1))[l] = '/0'; /* ending 0 */ 109 return ts; 110 } 可以看到把傳入的字符串具體內(nèi)存放在緊隨結(jié)構(gòu)體TString內(nèi)存后面，并且注意108行，字符串以”/0”結(jié)束與C語言字符串兼容的。
（2）若字符串是短字符串，首先計算字符串的Hash值，找到對應(yīng)的鏈表（短字符串的全局Hash表，使用的是鏈接法的方法，即把所有沖突的元素放在同一個鏈表中），查找當前要創(chuàng)建的字符串是否已經(jīng)在Hash表中，若已經(jīng)存在，則直接返回這個字符串。否則會調(diào)用函數(shù)newshrstr，而函數(shù)newshrstr會調(diào)用上面的createstrobj函數(shù)創(chuàng)建新字符串，并把新創(chuàng)建的字符串放到Hash表中，代碼如下（lstring.c））：
130 /* 131 ** checks whether short string exists and reuses it or creates a new one 132 */ 133 static TString *internshrstr (lua_State *L, const char *str, size_t l) { 134 GCObject *o; 135 global_State *g = G(L); 136 unsigned int h = luaS_hash(str, l, g->seed); 137 for (o = g->strt.hash[lmod(h, g->strt.size)]; 138 o != NULL; 139 o = gch(o)->next) { 140 TString *ts = rawgco2ts(o); 141 if (h == ts->tsv.hash && 142 ts->tsv.len == l && 143 (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { 144 if (isdead(G(L), o)) /* string is dead (but was not collected yet)? */ 145 changewhite(o); /* resurrect it */ 146 return ts; 147 } 148 } 149 return newshrstr(L, str, l, h); /* not found; create a new string */ 150 } 全局的字符串Hash表是保存在虛擬機全局狀態(tài)成員strt中的（lstate.h）：
119 stringtable strt; /* hash table for strings */
而類型stringtable是一個結(jié)構(gòu)體，其定義如下（lstate.h）：
59 typedef struct stringtable { 60 GCObject **hash; 61 lu_int32 nuse; /* number of elements */ 62 int size; 63 } stringtable; 其中成員GCObject **hash是一個指針數(shù)組，數(shù)組中每個成員實質(zhì)指向TString（注意TString中包括宏CommonHeader，該宏中的next成員可以構(gòu)造出Hash表中開散的鏈表）；nuse是數(shù)組hash中已經(jīng)被使用的元素個數(shù)；size是當前數(shù)組hash的大小。
在函數(shù)newshrstr插入新的字符串前，都會判斷nuse值是否大于size，若大于，表明Hash表大小不夠需要擴充，則把Hash表的大小擴充到原來的2倍，對應(yīng)的代碼如下（lstring.c）:
121 if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) 122 luaS_resize(L, tb->size*2); /* too crowded */
在gc的時候，會判斷nuse是否比size/2還?。ㄔ贚ua 5.1中是把nuse與size/4比較），如果是的話就重新resize這個stringtable的大小為原來的一半。對應(yīng)的代碼如下（lgc.c）：
783 int hs = g->strt.size / 2; /* half the size of the string table */ 784 if (g->strt.nuse < cast(lu_int32, hs)) /* using less than that half? */ 785 luaS_resize(L, hs); /* halve its size */
對于字符串比較，首先比較類型，若是不同類型字符串，則肯定不相同，然后區(qū)分短字符串和長字符串，對于短字符串，若兩者指針值相等，則相同，否則不相同；對應(yīng)長字符串，則首先比較指針值，若不同，則比較長度值和內(nèi)容逐字符比較。
總結(jié)
（1）Lua中的保留字和元方法名都是做為短字符串的，他們在虛擬機啟動的時候就已經(jīng)放入到全局短的字符串Hash表，并且是不回收的。
（2）查找字符是比較高效的，但是修改或插入字符串都是比較低效的，這里面除了計算外，至少要把外面的字符串拷貝到虛擬機中。
（3）對應(yīng)長字符串的Hash值，Lua是不會考察每個字符的，因而能避免快速計算長字符串的散列值，其相應(yīng)的代碼如下（lstring.c）：
51 unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { 52 unsigned int h = seed ^ l; 53 size_t l1; 54 size_t step = (l >> LUAI_HASHLIMIT) + 1; 55 for (l1 = l; l1 >= step; l1 -= step) 56 h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1])); 57 return h; 58 } 21 /* 22 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to 23 ** compute its hash 24 */ 25 #if !defined(LUAI_HASHLIMIT) 26 #define LUAI_HASHLIMIT 5 27 #endif （4）當有多個字符串連接時，不應(yīng)該直接用字符串連接運算符”..”，而是用table.concat操作或者是string.format來加快字符串連接的操作。
（5）Lua中字符串Hash算法用的是JSHash，關(guān)于字符串的各種Hash函數(shù)，網(wǎng)絡(luò)有篇文章對它進行了總結(jié)：https://www.byvoid.com/blog/string-hash-compare
以上所述誰就是本文的全部內(nèi)容了，希望能對大家學習lua有所幫助。
新聞熱點
疑難解答
圖片精選
