Lua 字符串的实现非常简单，核心字段就只有：字符串内容、长度、哈希值，下面将结合源码对其做下解析。
字符串的内化 (Internation)
首先要介绍一个非常重要的概念：Lua 中取值相同的字符串，有且只有一个实例，这种机制被称为「内化」。在 Lua 的全局状态表中，存在一个 strt 字段，该字段即存放了当前所有的字符串实例。
当一个新的字符串被（尝试）创建时，Lua 会先计算出其哈希值并在 strt 中查找。如果找到了，将直接使用已有的字符串；如果未找到，才会真正创建新的字符串实例。也就是说，Lua 里所有的字符串都是「引用」。
备注一：因此，请不要在 Lua 中进行频繁的字符串拼接操作，因为每一次字符串拼接都会生成新的字符串实例。首先性能上会很差，其次也会给 GC 带来较大的负担。
备注二：Python 也有类似的机制，可以看看这个有名的 wtfpython 项目里给出的实例与解释：https://github.com/satwikkansal/wtfpython#-explanation-2
数据结构
全局字符串表的结构
一言以蔽之，就是哈希桶+链表的实现。请看代码：
typedef struct stringtable {
GCObject **hash;
lu_int32 nuse; /* number of elements */
int size; // hash桶数组大小
} stringtable;
typedef struct global_State {
stringtable strt; /* hash table for strings */
// ... 其他字段省略
} global_State;各个字段的说明如下：
hash：GCObject*数组，也就是哈希桶，数组的每一项即是相同哈希的字符串构成的链表；nuse：字符串实例数量；size：hash哈希桶的数组大小；
注意到 hash 字段不直接引用 TString，而是 GCObject。虽然不知道作者最开始的意图，但 GCObject 背后也是 CommonHeader，同时 TString 也是以 CommonHeader 开头的，并不影响数据的存取。关于这几个数据结构，可参考我的这篇文章：Lua 数据类型的通用表示结构。
同时，TString 自身并没有直接可用来制作链表的字段。但其 CommonHeader，也就是 GCObject 里有一个 next 字段，链表正是由此 next 字段构成的。
另外，size 字段在某种意义上来说，并不是全局字符串表的容量上限。它的真正含义是构成哈希桶那个「数组」的大小。鉴于数组的每一项都可以是任意长度的链表，size 并不能限制字符串总计数量的上限。但是，size 会影响到 strt 这个哈希桶的扩容、缩容流程，从某种意义上来说，确实也在「间接」控制着其上限，具体后文会阐述。
字符串实例的结构
typedef union TString {
L_Umaxalign dummy; /* ensures maximum alignment for strings */
struct {
CommonHeader;
lu_byte reserved;
unsigned int hash;
size_t len;
} tsv;
} TString;其中 L_Umaxalign 用来强制编译器做内存对齐，其定义如下：
#define LUAI_USER_ALIGNMENT_T union { double u; void *s; long l; }
typedef LUAI_USER_ALIGNMENT_T L_Umaxalign;也就是 double、void*、long 里边的最长者，大多数场景下即是 double，即 TString 的各个字段将被对齐到 double 类型的大小。这种内存对齐可以加快在部分体系架构下的内存存取速度。
里层的 tsv 结构，以 CommonHeader 打头，也就是几个 GC 相关的字段。剩下的几个字段含义都很易懂，如下：
reserved：是否为 Lua 内部的保留字符串。如果是，意味着不会被 GC 回收；hash：哈希值；len：字符串长度（注意这里是不包括空字符的长度）；
字符串的创建流程
// 在全局字符串表中查找
// 如果已存在相同的字符串，直接返回已有实例；
// 如果没有，则调用 newlstr 真正进行创建，插入全局字符串表中，并返回此新对象
// 三个参数分别为：Lua 虚拟机状态信息，字符串内容，字符串长度
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
GCObject *o;
// 字符串长度作为 hash 算法的一部分参与计算
unsigned int h = cast(unsigned int, l); /* seed */
// 计算哈希值过程中使用的步长
// 当长度小于 64 时，step 为 1，也就是每一个字符都会参与哈希的计算
// 当长度大于等于 64 时，每 step 个字符之中只有 1 个参与了哈希的计算，减少计算量
// 虽然有小概率的哈希碰撞的可能，但并不影响功能
size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */
size_t l1;
// 每隔 step 取一个字符计算哈希
for (l1=l; l1>=step; l1-=step) /* compute hash */
h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
// 初始化：计算此哈希对应哪一个链表，取出链表上的首个对象（若有）
// 条件判断：对象是否为空
// 迭代方法：往链表的下一个对象移动
for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
o != NULL;
o = o->gch.next) {
TString *ts = rawgco2ts(o);
// 判断当前对象是否与正欲创建的字符串相等
// 条件1：长度相等（可以快速失败）；条件2：字符串内容相等
if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
/* string may be dead */
// 字符串可能正要被回收，若如此，将其设置为白色，以脱离此轮 GC
// 可详见我后续的 Lua GC 文章
if (isdead(G(L), o)) changewhite(o);
return ts;
}
}
// 现有的字符串中没有相等的，将真正地创建一个新的字符串
return newlstr(L, str, l, h); /* not found */
}// 真正创建一个新的字符串实例
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);
// 申请一块新内存用以放置新的字符串对象
// 此内存的长度为 TString 的大小 + 字符串大小
// 字符串被紧挨着 TString 结构存放
ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString)));
ts->tsv.len = l;
ts->tsv.hash = h;
// 设置颜色为当前白色，以供 GC 系统跟踪
ts->tsv.marked = luaC_white(G(L));
ts->tsv.tt = LUA_TSTRING;
// 此处创建的都是非保留字符串
ts->tsv.reserved = 0;
// 将字符串内容拷贝到新内存中紧挨着 TString 的地方
memcpy(ts+1, str, l*sizeof(char));
((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++;
// 在hash桶数组大小小于MAX_INT/2的情况下，
// 只要字符串数量大于桶数组数量就开始成倍的扩充桶的容量
// 可见下文详细介绍
if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
luaS_resize(L, tb->size*2); /* too crowded */
return ts;
}关于全局字符串表的 resize
resize 的时机
在一些特定时机，全局字符串表会发生扩容与缩容。具体地，目前有以下两种情况：
时机一：创建字符串后，发现表里「太拥挤」时，进行扩容
具体在 lstring.c 中的 newlstr 函数里，在 return 之前的这两行：
if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
luaS_resize(L, tb->size*2); /* too crowded */也即是，如果表里保存的对象数量大于 size，也就是数组大小时，就翻一倍进行扩容。除非翻一倍之后数组的长度将达到 MAX_INT 或更大，就不再扩容。
时机二：GC 过程中，发现表里「太稀疏」时，进行缩容
具体在 lgc.c 中的 checkSizes 函数里：
static void checkSizes (lua_State *L) {
global_State *g = G(L);
/* 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 */
// ... 省略后续无关代码
}如果表里的对象数量小于 size 的 1/4，将缩容到原本的一半。除非缩一半之后比 MINSTRTABSIZE（大小为 32） 还要小，就不再缩容。
此函数全局仅有一处调用，发生在 GC 单步过程 singlestep 的 GCSsweep 状态中。此状态下，GC 将对之前流程中收集到的垃圾执行清理操作，在将待清理列表全部清理完成后，就会借助 checkSizes 来确认是否需要触发缩容操作。
resize 的过程
一句话概况，就是遍历各个对象，将哈希值 mod 新的长度，放入新的链表即可。
// 对保存string的hash桶进行resize
void luaS_resize (lua_State *L, int newsize) {
GCObject **newhash;
stringtable *tb;
int i;
// 当前处在清理字符串的 GC 状态时，不能做 resize 操作
// 直接返回，等待下一次触发即可
if (G(L)->gcstate == GCSsweepstring)
return; /* cannot resize during GC traverse */
// 申请承载新的哈希桶的数组，大小即为 newsize
newhash = luaM_newvector(L, newsize, GCObject *);
tb = &G(L)->strt;
// 清空新的哈希桶
for (i=0; i<newsize; i++) newhash[i] = NULL;
/* rehash */
// 逐项遍历旧表里的每一个链表与链表上的每一个对象
for (i=0; i<tb->size; i++) {
GCObject *p = tb->hash[i];
while (p) { /* for each node in the list */
GCObject *next = p->gch.next; /* save next */
unsigned int h = gco2ts(p)->hash;
// 重新计算hash桶索引，这次需要mod新的hash桶大小
int h1 = lmod(h, newsize); /* new position */
lua_assert(cast_int(h%newsize) == lmod(h, newsize));
// 链到新表里对应的链表上
p->gch.next = newhash[h1]; /* chain it */
newhash[h1] = p;
p = next;
}
}
// 释放原有哈希桶占用的内存
luaM_freearray(L, tb->hash, tb->size, TString *);
tb->size = newsize;
// 注意：strt 这个结构体仍然不动，仅修改其中的 size 跟 hash 字段
// 也就是说，nuse 仍保持旧值
tb->hash = newhash;
}值得一提的是，全局字符串表的创建也是由
luaS_resize函数代劳，其发生在f_luaopen这个函数中，逻辑很简单，这里就不展开了。
参考资料
- 《Lua 设计与实现》第三章
- https://github.com/lichuang/Lua-5.1.4-codedump
Pingback引用通告： Lua 数据类型的通用表示结构 | chenxy.me