概述
Lua完全采用8位編碼，Lua字符串中的字符可以具有任何數(shù)值編碼，包括數(shù)值0。也就是說，可以將任意二進(jìn)制數(shù)據(jù)存儲(chǔ)到一個(gè)字符串中。Lua的字符串是不可變的值（immutable values）。如果修改，實(shí)質(zhì)上是新建一個(gè)字符串。根據(jù)上文《Lua中數(shù)據(jù)類型的源碼實(shí)現(xiàn)》中知道，在Lua中，字符串是自動(dòng)內(nèi)存管理機(jī)制所管理的對象，并且由聯(lián)合體TString來實(shí)現(xiàn)存儲(chǔ)字符串值的。下面將通過Lua 5.2.1的源碼來看字符串的實(shí)現(xiàn)以及總結(jié)了在Lua中使用字符串的注意事項(xiàng)。
源碼實(shí)現(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;
對這個(gè)聯(lián)合體定義，有幾點(diǎn)值得說明：
I、聯(lián)合體TString中成員L_Umaxalign dummy是用來保證與最大長度的C類型進(jìn)行對齊，其定義如下（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;
在其他可會(huì)回收的對象（比如table）的實(shí)現(xiàn)中，也可看到這個(gè)聯(lián)合體成員，這樣做的目的是通過內(nèi)存對齊，加快CPU訪問內(nèi)存的速度。
II、聯(lián)合體中成員tsv才是真正用來實(shí)現(xiàn)字符串的。其中成員CommonHeader用于GC，它會(huì)以宏的形式在所有的可回收對象中定義，代碼如下（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
這個(gè)宏對應(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對于短字符串，用來記錄這個(gè)字符串是否為保留字，對于長字符串，可以用于惰性求Hash值；unsigned int hash成員是字符串對應(yīng)的Hash值（在后面會(huì)具體講Lua是怎么計(jì)算字符串的Hash值的）；size_t len用來表示字符串的長度。
IV、上面的結(jié)構(gòu)體只是描述了一個(gè)字符串的結(jié)構(gòu)，真正的字符串?dāng)?shù)據(jù)保存是緊隨在結(jié)構(gòu)體后面保存。
在Lua5.2.1之前，不區(qū)分字符串長和短的字符串，所有的字符串保存在一個(gè)全局的Hash表中，對于Lua虛擬機(jī)來說，相同的字符串只有一份數(shù)據(jù)，從Lua5.2.1開始，只是把短的字符串字符串（當(dāng)前定義是長度小于等于40）放在全局Hash表中，而長字符串都是獨(dú)立生成，同時(shí)在計(jì)算Hash值時(shí)，引入一個(gè)隨機(jī)種子，這樣做的目的防止Hash Dos——攻擊者構(gòu)造出非常多相同Hash值的不同字符串，從而降低Lua從外部壓入字符串進(jìn)入全局的字符串Hash表的效率。下面是Lua5.2.1中，生成一個(gè)新字符串的步驟，其相應(yīng)的代碼都在lstring.c中：
（1）若字符串長度大于LUAI_MAXSHORTLEN（默認(rèn)值是40），則是長字符串，直接調(diào)用創(chuàng)建字符串接口的函數(shù)createstrobj（當(dāng)然字符串的長度需要能保存在成員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）若字符串是短字符串，首先計(jì)算字符串的Hash值，找到對應(yīng)的鏈表（短字符串的全局Hash表，使用的是鏈接法的方法，即把所有沖突的元素放在同一個(gè)鏈表中），查找當(dāng)前要?jiǎng)?chuàng)建的字符串是否已經(jīng)在Hash表中，若已經(jīng)存在，則直接返回這個(gè)字符串。否則會(huì)調(diào)用函數(shù)newshrstr，而函數(shù)newshrstr會(huì)調(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表是保存在虛擬機(jī)全局狀態(tài)成員strt中的（lstate.h）：
119 stringtable strt; /* hash table for strings */
而類型stringtable是一個(gè)結(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是一個(gè)指針數(shù)組，數(shù)組中每個(gè)成員實(shí)質(zhì)指向TString（注意TString中包括宏CommonHeader，該宏中的next成員可以構(gòu)造出Hash表中開散的鏈表）；nuse是數(shù)組hash中已經(jīng)被使用的元素個(gè)數(shù)；size是當(dāng)前數(shù)組hash的大小。
在函數(shù)newshrstr插入新的字符串前，都會(huì)判斷nuse值是否大于size，若大于，表明Hash表大小不夠需要擴(kuò)充，則把Hash表的大小擴(kuò)充到原來的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的時(shí)候，會(huì)判斷nuse是否比size/2還?。ㄔ贚ua 5.1中是把nuse與size/4比較），如果是的話就重新resize這個(gè)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ī)啟動(dòng)的時(shí)候就已經(jīng)放入到全局短的字符串Hash表，并且是不回收的。
（2）查找字符是比較高效的，但是修改或插入字符串都是比較低效的，這里面除了計(jì)算外，至少要把外面的字符串拷貝到虛擬機(jī)中。
（3）對應(yīng)長字符串的Hash值，Lua是不會(huì)考察每個(gè)字符的，因而能避免快速計(jì)算長字符串的散列值，其相應(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 ^ ((h5) + (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）當(dāng)有多個(gè)字符串連接時(shí)，不應(yīng)該直接用字符串連接運(yùn)算符”..”，而是用table.concat操作或者是string.format來加快字符串連接的操作。
（5）Lua中字符串Hash算法用的是JSHash，關(guān)于字符串的各種Hash函數(shù)，網(wǎng)絡(luò)有篇文章對它進(jìn)行了總結(jié)：https://www.byvoid.com/blog/string-hash-compare
以上所述誰就是本文的全部內(nèi)容了，希望能對大家學(xué)習(xí)lua有所幫助。
您可能感興趣的文章:- Lua中使用table.concat連接大量字符串實(shí)例
- Lua教程（五）：C/C++操作Lua數(shù)組和字符串示例
- Lua中字符串（string）淺析
- Lua字符串庫中的幾個(gè)重點(diǎn)函數(shù)介紹
- Lua函數(shù)與字符串處理簡明總結(jié)
- 使用lua實(shí)現(xiàn)split字符串分隔
- Lua中的string庫（字符串函數(shù)庫）總結(jié)
- Lua字符串模式匹配函數(shù)小結(jié)
- Lua字符串庫(string庫)學(xué)習(xí)筆記
