一、概述

string是Lua的一种数据类型，它不同于普通的基本类型，为了节约内存，多个相同的短字符串会共用一个，因而需要管理string的引用情况，从而实现在不被用时，能正确GC。

二、实现细节

1、字符串分类

Lua为了节省内存，Lua的字符串分为短字符串和长字符串。
短字符串： 长度小于等于40为短字符串。相同字符的短字符串是共用同一个的。
长字符串： 长度大于40为长字符串。相同的两个长字符串是两个独立的字符串。

2、string数据类型定义

string在Lua运行时里的数据结构是TString。具体的定义如下。

如上图，TString可以认为是一个GCObject的派生类（实际不是，只是有GCObject相同的数据成员），TString既用来表示短字符串也用来表示长字符串。主要记录了string的hash值，长度，如果是短字符串，还包含了指向hash表里下一个短字符串的指针。

3、短字符串管理

• 存储结构
  所有的短字符串sringtable来管理，存储在global_state里，字段名为strt，所有的短字符串用了一个hash表来管理，作为strt的一个成员，名字为hash。
  stringtable的数据结构如下图：
  
• hash表结构
  hash表的实现结构如下图，hash冲突的解决采用链地址法。
  
• hash算法
  根据原生字符串的数据来计算hash值，具体的hash算法如下：
  h = seed ^ l
  step = (l >> 5) + 1
  for (; l >= step; l -= step)
  h ^= ((h<<5) + (h>>2) + str[l - 1])
• hash表的扩容
  hash表的负载因子为1，也就是说当hash表里的元素数量除以hash表槽的数量所得的值大于等于1时，会对hash表进行扩容，扩容后槽的数量会扩大一倍。

三、关键实现

1、字符串创建

• 如果缓存里包含了该TString，就返回该TString
• 如果是短字符串，则看下短字符串hash表里是否存在，存在就返回该TString，没有就新建一个TString,放到字符串hash表里。
• 如果是长字符串，就直接创建TString

2、短字符串缓存

为了避免从链式hash里遍历查找和比较是否存在该字符串，Lua实现了一个字符串缓存，用来存储最近使用过的短字符串，优先去缓存里查下是否有该字符串。
缓存采用了53*2的数据，刚使用过的字符串会用hash值对53求模后，放到对应的位置里，最多保存两个，超过数量会移除最老的缓存字符串。
具体的数据结构如下图：

四、字符串GC

待补充