string類型作為Lua中幾種基本數(shù)據(jù)類型之一运授，使用頻率那是相當(dāng)?shù)母哂匠ⅲ粤私釲ua中字符串的實(shí)現(xiàn)原理，能夠讓我們更合理褂傀、更高效的使用Lua中的字符串忍啤。避免一些誤區(qū)，提高程序效率仙辟。這里介紹的所有代碼都基于Lua5.1版本同波。

一、Lua中string的數(shù)據(jù)結(jié)構(gòu)

一般來說叠国，要表示一個(gè)字符串一般都需要兩個(gè)關(guān)鍵數(shù)據(jù)：
（1）字符串的長度
（2）指向字符串首地址的指針未檩。
Lua中的字符串結(jié)構(gòu)設(shè)計(jì)也是圍繞這兩個(gè)關(guān)鍵數(shù)據(jù)的。具體我們來看一下Lua中字符串的數(shù)據(jù)結(jié)構(gòu)：

//（lobject.h）
/*
** String headers for string table
*/
typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;
    unsigned int hash;
    size_t len;
  } tsv;
} TString;

接下來我們來理解一下這個(gè)共同體(union)中每個(gè)字段的含義：
dummy ：表示字符串最大的對(duì)齊長度粟焊。L_Umaxalign也是一個(gè)共同體冤狡，具體結(jié)構(gòu)如下：

//(llimits.h)
/* type to ensure maximum alignment */
typedef LUAI_USER_ALIGNMENT_T L_Umaxalign;

//(luaconf.h)
/*
@@ LUAI_USER_ALIGNMENT_T is a type that requires maximum alignment.
** CHANGE it if your system requires alignments larger than double. (For
** instance, if your system supports long doubles and they must be
** aligned in 16-byte boundaries, then you should add long double in the
** union.) Probably you do not need to change this.
*/
#define LUAI_USER_ALIGNMENT_T   union { double u; void *s; long l; }

上面的注釋解釋的非常清楚了校赤。可以根據(jù)系統(tǒng)需要在這個(gè)修改最大的對(duì)齊長度筒溃。
CommonHeader：表示string是需要加入到Lua的GC管理中的马篮。CommonHeader是個(gè)宏定義，具體的介紹可以看之前的Lua數(shù)據(jù)類型（源碼解析）
reserved：這個(gè)變量用于標(biāo)記這個(gè)字符串是不是Lua虛擬機(jī)中的保留字符串怜奖。如果這個(gè)值不為0浑测，那么將不會(huì)在GC階段被回收，而是一直保留在虛擬機(jī)中歪玲。只有Lua語言中的關(guān)鍵字才會(huì)是保留字符串（eg.local self function）
hash：該字符串的散列值迁央。
len：字符串的長度

二、Lua中string類型的實(shí)現(xiàn)

在Lua中滥崩，每個(gè)字符串?dāng)?shù)據(jù)都只有一份岖圈。每當(dāng)創(chuàng)建一個(gè)新的字符串的時(shí)候，首先會(huì)檢查當(dāng)前是否已經(jīng)存在這個(gè)字符串钙皮，如果存在就直接復(fù)用蜂科，讓字符串變量保存這個(gè)字符串的引用，不存在則創(chuàng)建一個(gè)新的字符串短条。例如：

a = "1"
a = a.."2"
b = "1"

在Lua中的表示如下圖：

Lua中字符串只有一份.png

那么這樣的話导匣，在Lua虛擬機(jī)中必然有一個(gè)全局的地方存放當(dāng)前系統(tǒng)中的所有字符串。這個(gè)地方就是global_State(lstate.h)的strt字段茸时。strt是個(gè)stringtable結(jié)構(gòu)體類型贡定，我們看一下stringtable的定義：

//(lstate.h)
typedef struct stringtable {
  GCObject **hash;
  lu_int32 nuse;  /* number of elements */
  int size;
} stringtable;

hash ：一個(gè)GCObject的二維指針，可以看作二維數(shù)組可都，根據(jù)字符串的離散值存放這我們創(chuàng)建的字符串缓待。
nuse ：當(dāng)前存放的數(shù)量
size ： hash至的大小
通過上面可以總結(jié)這么幾點(diǎn)：
（1）Lua中通過字符串的hash值來對(duì)字符串進(jìn)行查找，對(duì)比渠牲。
（2）Lua中的字符串變量存放的是字符串的引用旋炒，而不是字符串本身。
（3）同一個(gè)字符串在Lua虛擬機(jī)中只有一份嘱兼。
（4）Lua虛擬機(jī)中g(shù)lobal_State的strt字段存放著當(dāng)前系統(tǒng)中的所有字符串

下面通過具體的代碼分析來看看Lua中的具體實(shí)現(xiàn)：
創(chuàng)建字符串

//(lstring.h)
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  GCObject *o;
  //默認(rèn)的hash值
  unsigned int h = cast(unsigned int, l);  /* seed */
  //計(jì)算hash值時(shí)的步長国葬，如果字符串太長的話，沒有必要使用所有的字符來計(jì)算hash值芹壕，
  //只需要按照步長，取其中的一些字符來計(jì)算hash值
  size_t step = (l>>5)+1;  /* if string is too long, don't hash all its chars */
  size_t l1;
  for (l1=l; l1>=step; l1-=step)  /* compute hash */
    //計(jì)算字符串的hash值算法
    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
  //通過計(jì)算出來的hash值接奈，遍歷對(duì)應(yīng)的CGObject鏈表
  for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
       o != NULL;
       o = o->gch.next) {
    //GCObject類型轉(zhuǎn)換為TString類型
    TString *ts = rawgco2ts(o);
    //比較兩個(gè)字符串是否相等
    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
      /* string may be dead */
      //可能這個(gè)字符串正處于將要被CG回收的階段踢涌，重新設(shè)置GC狀態(tài)
      if (isdead(G(L), o)) changewhite(o);
      return ts;
    }
  }
  //如果該字符串還沒有保存在當(dāng)前的系統(tǒng)中，那么創(chuàng)建一個(gè)序宦。
  return newlstr(L, str, l, h);  /* not found */
}

//(lstring.h)
static TString *newlstr (lua_State *L, const char *str, size_t l,unsigned int h) {
  TString *ts;
  stringtable *tb;
  //判斷字符串是不是超過了最大范圍
  if (l+1 > (MAX_SIZET - sizeof(TString))/sizeof(char))
    luaM_toobig(L);
  //分配內(nèi)存
  ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString)));
  //給TString賦值
  ts->tsv.len = l;
  ts->tsv.hash = h;
  //新創(chuàng)建的GC都標(biāo)志為白色
  ts->tsv.marked = luaC_white(G(L));
  ts->tsv.tt = LUA_TSTRING;
  //表示不是Lua中保留字符串
  ts->tsv.reserved = 0;
  //拷貝字符
  memcpy(ts+1, str, l*sizeof(char));
  //在末尾加上'\0'標(biāo)志
  ((char *)(ts+1))[l] = '\0';  /* ending 0 */
  //將新創(chuàng)建的字符串加入到離散表中
  tb = &G(L)->strt;
  h = lmod(h, tb->size);
  ts->tsv.next = tb->hash[h];  /* chain new entry */
  tb->hash[h] = obj2gco(ts);
  tb->nuse++;
  //判斷是否需要擴(kuò)容
  if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
    luaS_resize(L, tb->size*2);  /* too crowded */
  return ts;
}

重新分配字符串的離散數(shù)據(jù)

//(lstring.h)
void luaS_resize (lua_State *L, int newsize) {
  //新的離散列表指針
  GCObject **newhash;
  stringtable *tb;
  int i;
  //判斷是否在CG回收階段
  if (G(L)->gcstate == GCSsweepstring)
    return;  /* cannot resize during GC traverse */
  //給新的離散列表分配內(nèi)存
  newhash = luaM_newvector(L, newsize, GCObject *);
  //獲取全局的stringTable
  tb = &G(L)->strt;
  //新的離散列表初始化
  for (i=0; i<newsize; i++) newhash[i] = NULL;
  /* rehash */
  //遍歷整個(gè)離散列表睁壁，重新計(jì)算hash索引
  for (i=0; i<tb->size; i++) {
    //同一個(gè)hash值鏈表的首個(gè)元素
    GCObject *p = tb->hash[i];
    //遍歷整個(gè)鏈表的元素
    while (p) {  /* for each node in the list */
      //保存一下下一個(gè)元素，防止操作next指針導(dǎo)致鏈表斷開
      GCObject *next = p->gch.next;  /* save next */
      //將GCObject轉(zhuǎn)換為TString，獲取之前的hash值
      unsigned int h = gco2ts(p)->hash;
      //用之前的hash值在新的size中取余潘明，得到新的hash值行剂。
      int h1 = lmod(h, newsize);  /* new position */
      lua_assert(cast_int(h%newsize) == lmod(h, newsize));
      //下面兩步就是鏈表的插入操作，將p加到新的hash鏈表中
      p->gch.next = newhash[h1];  /* chain it */
      newhash[h1] = p;
      //讓指針指向下一個(gè)钳降，繼續(xù)循環(huán)
      p = next;
    }
  }
  //釋放之前hash列表之內(nèi)存
  luaM_freearray(L, tb->hash, tb->size, TString *);
  //更新新的hash列表的大小
  tb->size = newsize;
  //更新新的hash列表的引用
  tb->hash = newhash;
}

luaS_resize 操作都是Lua自身觸發(fā)厚宰，無需我們手動(dòng)維護(hù)。主要有3個(gè)地方調(diào)用：
（1）f_luaopen(lstate.c)在lua虛擬機(jī)初始化的時(shí)候會(huì)給size設(shè)置一個(gè)默認(rèn)的大小MINSTRTABSIZE = 32

static void f_luaopen (lua_State *L, void *ud) {
  global_State *g = G(L);
  UNUSED(ud);
  stack_init(L, L);  /* init stack */
  sethvalue(L, gt(L), luaH_new(L, 0, 2));  /* table of globals */
  sethvalue(L, registry(L), luaH_new(L, 0, 2));  /* registry */
  luaS_resize(L, MINSTRTABSIZE);  /* initial size of string table */
  luaT_init(L);
  luaX_init(L);
  luaS_fix(luaS_newliteral(L, MEMERRMSG));
  g->GCthreshold = 4*g->totalbytes;
}

（2）newlstr(lstring.c)創(chuàng)建新的字符串時(shí)遂填，判斷size是不是不夠铲觉，如果夠則擴(kuò)容1倍。

if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
    luaS_resize(L, tb->size*2);  /* too crowded */

（3）checkSizes(lgc.c)在CG回收階段會(huì)判斷元素的個(gè)數(shù)是不是比size的1/4還小吓坚，如果是則將size縮小為原來的1/2.

 /* check size of string hash */
  if (g->strt.nuse < cast(lu_int32, g->strt.size/4) &&
      g->strt.size > MINSTRTABSIZE*2)
    luaS_resize(L, g->strt.size/2);  /* table is too big */

保留字符串初始化

//(llex.h)
/*
* WARNING: if you change the order of this enumeration,
* grep "ORDER RESERVED"
*/
//保留字的枚舉
enum RESERVED {
  /* terminal symbols denoted by reserved words */
  TK_AND = FIRST_RESERVED, TK_BREAK,
  TK_DO, TK_ELSE, TK_ELSEIF, TK_END, TK_FALSE, TK_FOR, TK_FUNCTION,
  TK_IF, TK_IN, TK_LOCAL, TK_NIL, TK_NOT, TK_OR, TK_REPEAT,
  TK_RETURN, TK_THEN, TK_TRUE, TK_UNTIL, TK_WHILE,
  /* other terminal symbols */
  TK_CONCAT, TK_DOTS, TK_EQ, TK_GE, TK_LE, TK_NE, TK_NUMBER,
  TK_NAME, TK_STRING, TK_EOS
};

//(llex.c)
/* ORDER RESERVED */
//枚舉對(duì)應(yīng)的保留字字符串
const char *const luaX_tokens [] = {
    "and", "break", "do", "else", "elseif",
    "end", "false", "for", "function", "if",
    "in", "local", "nil", "not", "or", "repeat",
    "return", "then", "true", "until", "while",
    "..", "...", "==", ">=", "<=", "~=",
    "<number>", "<name>", "<string>", "<eof>",
    NULL
};

/* number of reserved words */
#define NUM_RESERVED    (cast(int, TK_WHILE-FIRST_RESERVED+1))

void luaX_init (lua_State *L) {
  int i;
  for (i=0; i<NUM_RESERVED; i++) {
    TString *ts = luaS_new(L, luaX_tokens[i]);
    //標(biāo)記字符串的GC回收狀態(tài)
    luaS_fix(ts);  /* reserved words are never collected */
    lua_assert(strlen(luaX_tokens[i])+1 <= TOKEN_LEN);
    //標(biāo)記該字符串為保留字字符串
    ts->tsv.reserved = cast_byte(i+1);  /* reserved word */
  }
}

luaX_init 是在虛擬機(jī)初始化的時(shí)候調(diào)用的撵幽。f_luaopen(lstate.c)在分配了stringTable的內(nèi)存后調(diào)用。

三礁击、分析與總結(jié)

在Lua字符串這一塊最主要的是要理解下面幾個(gè)東西：
（1）Lua字符串是會(huì)被GC的
（2）每個(gè)字符串在Lua內(nèi)存中只存在一份
（3）Lua通過一個(gè)全局的散列桶(stringTable)管理所有的字符串
下面一張圖幫助理解一下Lua字符串存儲(chǔ)的結(jié)構(gòu)：

strt結(jié)構(gòu)示意圖.png

在我們平時(shí)的使用中盡量避免循環(huán)拼接字符串盐杂，因?yàn)闆]拼接一次就是重新創(chuàng)建一個(gè)新的字符串。

a = os.clock()
local s = ""
for i = 1, 100000 do
    s = s.."a"
end
b = os.clock()
print(b-a)
--2.1309999999939s

a = os.clock()
local s = ""
local t = {}
for i = 1, 100000 do
    t[#t+1] = "a"
end
s = table.concat(t,"")
b = os.clock()
print(b-a)
--0.01600000000326s

我們可以看到這差距非常的夸張哆窿。第一種方法需要?jiǎng)?chuàng)建大量的字符串况褪，而第二種方法直接使用memcpy拷貝，所以相差巨大更耻。
最后测垛，Lua5.2之后的版本在字符串的實(shí)現(xiàn)上有些許的不同，增加長字符串和短字符串的概念秧均，但是大體的設(shè)計(jì)概念還是一樣食侮，之后有時(shí)間再補(bǔ)充5.2之后版本的字符串實(shí)現(xiàn)。