string类型作为Lua中几种基本数据类型之一，使用频率那是相当的高，所以了解Lua中字符串的实现原理，能够让我们更合理、更高效的使用Lua中的字符串。避免一些误区，提高程序效率。这里介绍的所有代码都基于Lua5.1版本。
一、Lua中string的数据结构
一般来说，要表示一个字符串一般都需要两个关键数据： （1）字符串的长度 （2）指向字符串首地址的指针。 Lua中的字符串结构设计也是围绕这两个关键数据的。具体我们来看一下Lua中字符串的数据结构：
//（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;接下来我们来理解一下这个共同体(union)中每个字段的含义：dummy ：表示字符串最大的对齐长度。L_Umaxalign也是一个共同体，具体结构如下：
//(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; }上面的注释解释的非常清楚了。可以根据系统需要在这个修改最大的对齐长度。CommonHeader：表示string是需要加入到Lua的GC管理中的。CommonHeader是个宏定义，具体的介绍可以看之前的Lua数据类型（源码解析）reserved：这个变量用于标记这个字符串是不是Lua虚拟机中的保留字符串。如果这个值不为0，那么将不会在GC阶段被回收，而是一直保留在虚拟机中。只有Lua语言中的关键字才会是保留字符串（eg.local self function）hash：该字符串的散列值。len：字符串的长度
二、Lua中string类型的实现
在Lua中，每个字符串数据都只有一份。每当创建一个新的字符串的时候，首先会检查当前是否已经存在这个字符串，如果存在就直接复用，让字符串变量保存这个字符串的引用，不存在则创建一个新的字符串。例如：
a = "1" a = a.."2" b = "1"在Lua中的表示如下图：
Lua中字符串只有一份.png
那么这样的话，在Lua虚拟机中必然有一个全局的地方存放当前系统中的所有字符串。这个地方就是global_State(lstate.h)的strt字段。strt是个stringtable结构体类型，我们看一下stringtable的定义：
//(lstate.h) typedef struct stringtable { GCObject **hash; lu_int32 nuse; /* number of elements */ int size; } stringtable;hash ：一个GCObject的二维指针，可以看作二维数组，根据字符串的离散值存放这我们创建的字符串。nuse ：当前存放的数量size ： hash至的大小 通过上面可以总结这么几点： （1）Lua中通过字符串的hash值来对字符串进行查找，对比。 （2）Lua中的字符串变量存放的是字符串的引用，而不是字符串本身。 （3）同一个字符串在Lua虚拟机中只有一份。 （4）Lua虚拟机中global_State的strt字段存放着当前系统中的所有字符串
下面通过具体的代码分析来看看Lua中的具体实现：创建字符串
//(lstring.h) TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { GCObject *o; //默认的hash值 unsigned int h = cast(unsigned int, l); /* seed */ //计算hash值时的步长，如果字符串太长的话，没有必要使用所有的字符来计算hash值， //只需要按照步长，取其中的一些字符来计算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 */ //计算字符串的hash值算法 h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1])); //通过计算出来的hash值，遍历对应的CGObject链表 for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)]; o != NULL; o = o->gch.next) { //GCObject类型转换为TString类型 TString *ts = rawgco2ts(o); //比较两个字符串是否相等 if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) { /* string may be dead */ //可能这个字符串正处于将要被CG回收的阶段，重新设置GC状态 if (isdead(G(L), o)) changewhite(o); return ts; } } //如果该字符串还没有保存在当前的系统中，那么创建一个。 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); //分配内存 ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString))); //给TString赋值 ts->tsv.len = l; ts->tsv.hash = h; //新创建的GC都标志为白色 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'标志 ((char *)(ts+1))[l] = '\0'; /* ending 0 */ //将新创建的字符串加入到离散表中 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++; //判断是否需要扩容 if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2) luaS_resize(L, tb->size*2); /* too crowded */ return ts; }重新分配字符串的离散数据
//(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 */ //给新的离散列表分配内存 newhash = luaM_newvector(L, newsize, GCObject *); //获取全局的stringTable tb = &G(L)->strt; //新的离散列表初始化 for (i=0; i<newsize; i++) newhash[i] = NULL; /* rehash */ //遍历整个离散列表，重新计算hash索引 for (i=0; i<tb->size; i++) { //同一个hash值链表的首个元素 GCObject *p = tb->hash[i]; //遍历整个链表的元素 while (p) { /* for each node in the list */ //保存一下下一个元素，防止操作next指针导致链表断开 GCObject *next = p->gch.next; /* save next */ //将GCObject转换为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; //让指针指向下一个，继续循环 p = next; } } //释放之前hash列表之内存 luaM_freearray(L, tb->hash, tb->size, TString *); //更新新的hash列表的大小 tb->size = newsize; //更新新的hash列表的引用 tb->hash = newhash; }luaS_resize 操作都是Lua自身触发，无需我们手动维护。主要有3个地方调用： （1）f_luaopen(lstate.c)在lua虚拟机初始化的时候会给size设置一个默认的大小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)创建新的字符串时，判断size是不是不够，如果够则扩容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回收阶段会判断元素的个数是不是比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 */ //枚举对应的保留字字符串 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]); //标记字符串的GC回收状态 luaS_fix(ts); /* reserved words are never collected */ lua_assert(strlen(luaX_tokens[i])+1 <= TOKEN_LEN); //标记该字符串为保留字字符串 ts->tsv.reserved = cast_byte(i+1); /* reserved word */ } }luaX_init 是在虚拟机初始化的时候调用的。f_luaopen(lstate.c)在分配了stringTable的内存后调用。
三、分析与总结
在Lua字符串这一块最主要的是要理解下面几个东西： （1）Lua字符串是会被GC的 （2）每个字符串在Lua内存中只存在一份 （3）Lua通过一个全局的散列桶(stringTable)管理所有的字符串 下面一张图帮助理解一下Lua字符串存储的结构：
strt结构示意图.png在我们平时的使用中尽量避免循环拼接字符串，因为没拼接一次就是重新创建一个新的字符串。
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我们可以看到这差距非常的夸张。第一种方法需要创建大量的字符串，而第二种方法直接使用memcpy拷贝，所以相差巨大。 最后，Lua5.2之后的版本在字符串的实现上有些许的不同，增加长字符串和短字符串的概念，但是大体的设计概念还是一样，之后有时间再补充5.2之后版本的字符串实现。
