Lua：Table 浅析

本文的分析基于 OpenResty 的 Lua 分支（https://github.com/openresty/luajit2）。

核心 API#

table 的 API 定义在 src/lib_table.c 中，API 分为三个部分：

标准库函数：

table.insert() - 向 table 插入元素
table.remove() - 移除 table 元素
table.concat() - 连接 table 元素为字符串
table.sort() - 对 table 进行排序
table.maxn() - 找到 table 中最大数字键
table.move() - 移动 table 元素

LuaJIT 扩展函数：

table.new() - 预分配指定大小的 table

OpenResty 扩展函数：

table.clear() - 清空 table 内容
table.clone() - 克隆 table
table.nkeys() - 获取 table 键的数量
table.isarray() - 检查是否为数组
table.isempty() - 检查 table 是否为空

数据结构#

typedef struct Node {
  TValue val;         // 值对象，必须是第一个字段
  TValue key;         // 键对象
  MRef next;          // 哈希链指针
#if !LJ_GC64
  MRef freetop;       // 32位架构下的空闲节点顶部指针(存储在node[0])
#endif
} Node;

typedef struct GCtab {
  GCHeader;           // GC 通用头部：nextgc, marked, gct
  uint8_t nomm;       // 元方法负缓存掩码
  int8_t colo;        // 数组共址标记 (-1表示已分离, >0表示共址大小)
  MRef array;         // 数组部分指针
  GCRef gclist;       // GC 链表指针
  GCRef metatable;    // 元表引用
  MRef node;          // 哈希部分指针
  uint32_t asize;     // 数组部分大小 [0, asize-1]
  uint32_t hmask;     // 哈希掩码 (哈希部分大小-1)
#if LJ_GC64
  MRef freetop;       // 64位架构下的空闲节点顶部指针
#endif
} GCtab;

可以看到，GCtab 中同时定义了数组部分 array 和哈希部分 node。

table 的创建#

Lua 的标准语义中，table 的创建如下：

# 空表的初始化
local t = {}

# 非空表的初始化
local t2 = {[1] = 2, "hello" = "world"}

空表的初始化编译成一条 TNEW，运行时直接调用 lj_tab_new，通常不分配数组/哈希内存（asize=0，hbits=0），哈希部分指向全局 nilnode，数组指针为 NULL。首次插入时会触发扩容/重哈希。

 BCPos pc = bcemit_AD(fs, BC_TNEW, freg, 0);
  ...
  if (!t) {  /* Construct TNEW RD: hhhhhaaaaaaaaaaa. */
    BCIns *ip = &fs->bcbase[pc].ins;
    if (!needarr) narr = 0;
    ...
    setbc_d(ip, narr|(hsize2hbits(nhash)<<11));
  }

//

注意，hhhhhaaaaaaaaaaa 是位布局（不是作者胡乱写的注释：）），低11位是数组段的预估大小，上限0x7ff，高5位是哈希段大小的指数（hsize2hbits(nhash)），实际哈希桶数是 1 « h。非空表的初始化编译器会统计 narr（数组位数）与 nhash（哈希键数量），设置初值以减少运行期扩容：

若有数组项且 narr < 3，则 narr 强制提升到 3（小数组的经验最优）。
hbits = hsize2hbits(nhash)。如果表的所有键和值都为编译期常量，编译期会先构建“模板表”，字节码用 TDUP，运行时调用 lj_tab_dup 直接复制模板。否则仍然会编译成 TNEW 指令，然后发起若干 TSET* 指令逐个填充。

 if (!t) {  /* Create template table on demand. */
    t = lj_tab_new(fs->L, needarr ? narr : 0, hsize2hbits(nhash));
    kidx = const_gc(fs, obj2gco(t), LJ_TTAB);
    fs->bcbase[pc].ins = BCINS_AD(BC_TDUP, freg-1, kidx);
  }

创建入口函数（TNEW）：

/* Create a new table.
**
** IMPORTANT NOTE: The API differs from lua_createtable()!
**
** The array size is non-inclusive. E.g. asize=128 creates array slots
** for 0..127, but not for 128. If you need slots 1..128, pass asize=129
** (slot 0 is wasted in this case).
**
** The hash size is given in hash bits. hbits=0 means no hash part.
** hbits=1 creates 2 hash slots, hbits=2 creates 4 hash slots and so on.
*/
GCtab *lj_tab_new(lua_State *L, uint32_t asize, uint32_t hbits)
{
  GCtab *t = newtab(L, asize, hbits);
  clearapart(t);                    // 清空数组部分
  if (t->hmask > 0) clearhpart(t);  // 清空哈希部分
  return t;
}_

在 LuaJIT 中，提供了一个新的表初始化方法 table.new：

local tnew = require "table.new"
local t = tnew(100000, 2000000)

标准 Lua table 初始化方法存在的一个问题是，当需要创建一个大表时，往往需要经历多次的扩容和重哈希，涉及到多次内存的拷贝与回收。造成性能损失。 table.new 则在初始化时指定 a/h 参数，一次性分配内存，规避了这个问题。需要注意的是，table.new 的 a/h 参数是 API 语义的，即 a 表示 1…narr，以 1 为基，h 表示预估的 hash 键数量，而不是以位表示。

JLIB_NOREG LJLIB_CF(table_new) LJLIB_REC(.)
{
  int32_t a = lj_lib_checkint(L, 1);
  int32_t h = lj_lib_checkint(L, 2);
  lua_createtable(L, a, h);
  return 1;
}

table.new 的调用链：lua_createtable(L, a, h) -> lj_tab_new_ah(L, a, h) -> lj_tab_new(asize=(a>0 ? a+1 : 0), hbits=hsize2hbits(h))

在最终调用 lj_tab_new 时，数组转换成了 C 的 0 基。

键值的插入与删除#

主要插入函数 lj_tab_set。

TValue *lj_tab_set(lua_State *L, GCtab *t, cTValue *key) {
  Node *n;
  t->nomm = 0; /* Invalidate negative metamethod cache. */
  if (tvisstr(key)) {
    return lj_tab_setstr(L, t, strV(key));
  } else if (tvisint(key)) {
    return lj_tab_setint(L, t, intV(key));
  } else if (tvisnum(key)) {
    lua_Number nk = numV(key);
    int32_t k = lj_num2int(nk);
    if (nk == (lua_Number)k) return lj_tab_setint(L, t, k);
    if (tvisnan(key)) lj_err_msg(L, LJ_ERR_NANIDX);
    /* Else use the generic lookup. */
  } else if (tvisnil(key)) {
    lj_err_msg(L, LJ_ERR_NILIDX);
  }
  n = hashkey(t, key);
  do {
    if (lj_obj_equal(&n->key, key)) return &n->val;
  } while ((n = nextnode(n)));
  return lj_tab_newkey(L, t, key);
}

插入函数根据键的类型走不同的快路径。如字符串类型 lj_tab_setstr, 整数类型 lj_tab_setint 等。通用查找路径如键类型为 bool、table 等，首先会计算锚点n = hashkey(t, key)，遍历 hash 键，用 lj_obj_equal(&n->key, key) 判断完全相等即返回值槽。遍历完未命中即插入新键。

新键插入是由 lj_tab_netkey(L, t, key) 完成的。这个函数实现了 Brent’s variation 算法来优化哈希链长度：可能移动“非主槽”节点，重链表，尽量缩短查找路径。如果没有空闲节点，会触发重哈希（见扩容与缩容）。

键值的删除有两种方式：第一种是直接将值设置为 nil，删除时间复杂度为 O(1)，无需移动元素。hash 段只能使用但是会产生数组空洞。同时 #t 计算的长度与实际不符。

local t = {}

for i = 1, 10 do
    t[i] = i
end

t["key1"] = "value1"
t["key2"] = "value2"


t[3] = nil
t["key1"] = nil
-- table.remove(t, 5)

for index, value in pairs(t) do
    print(index, value)
end

print("#t: ", #t)

-- output 
1	1
2	2
4	4
5	5
6	6
7	7
8	8
9	9
10	10
key2	value2
#t: 	10

第二种方式是调用 table.remove()，table.remove 的语义是对“序列”操作：移除位置 pos，并将 pos+1..#t 依次前移，保持连续。但是 remove 只支持对数组进行操作。优点是能使数组保持连续性，不会出现上面的数组空洞。缺点是性能开销大，删除中间元素需要 O(n) 时间移动后续元素。 而且如果整数键很大，不在 #t 范围之内，使用 table.remove 是没有作用的。

最佳实践：

只按“序列段”来决定是否用 table.remove：
- 当且仅当整数键 k 满足 1 <= k <= #t，并且你把这张表当作“密集数组”使用时，用 table.remove(t, k)。
- 其他情况（例如 k > #t、表中存在空洞、你并非要维护一个顺序数组）都请用 t[k] = nil。
在“哈希段”的整数键上用 table.remove 不会报错，但也不会删除那个键：table.remove 只会对 1..#t 范围内的序列元素做移位；若 pos > #t 它直接什么也不做并返回 nil。
注意 #t 对“有空洞的表”是不可靠的（Lua 语义），因此若表稀疏，table.remove 的移位可能不是你期望的。要么保持数组密集，要么自己维护长度。

table 的扩容与缩容#

table 的扩容与缩容唯一的触发点是在新键插入的时候，并且需要满足没有空闲的哈希节点存放键值。删除是不会触发重哈希的。

TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
{
  Node *n = hashkey(t, key);
  if (!tvisnil(&n->val) || t->hmask == 0) {  // 位置已占用或无哈希部分
    Node *nodebase = noderef(t->node);
    Node *collide, *freenode = getfreetop(t, nodebase);
    do {
      if (freenode == nodebase) {  // 没有空闲节点了！
        rehashtab(L, t, key);  // 触发重哈希
        return lj_tab_set(L, t, key);  // 重试插入
      }
    } while (!tvisnil(&(--freenode)->key));
    // ... Brent算法优化链长度
  }
}

注意，如果 table 插入的是一个整数，而数组段没有空间容纳该整数（整数值大于数组上界），lua 并不会立即扩容数组段，而是会先尝试将该整数放入 hash 段，等到后面重哈希时再将 hash 段中的整数移动到数组段中。

重哈希流程：

static void rehashtab(lua_State *L, GCtab *t, cTValue *ek) {
  uint32_t bins[LJ_MAX_ABITS]; // 按 2 的幂次分组统计
  uint32_t total, asize, na, i;
  
  // 1. 统计现有键分布
  for (i = 0; i < LJ_MAX_ABITS; i++) bins[i] = 0;
  asize = countarray(t, bins); // 统计数组部分
  total = 1 + asize;
  total += counthash(t, bins, &asize); // 统计 hash 部分
  asize += countint(ek, bins); // 包含新键
  
  // 2. 计算最优数组大小
  na = bestasize(bins, &asize);
  total -= na;
  
  // 3. 执行 resize
  lj_tab_resize(L, t, asize, hsize2hbits(total));
}

数组段扩容按照 2 的幂次增长，大小维持 2^n+1 形式，1 表示空闲的 slot 0。数组段的核心原则是填充率需要大于 50%。对于导致低于 50% 的整数键会将其放到 hash 段中。

static uint32_t bestasize(uint32_t bins[], uint32_t *narray)
{
  // 核心原则：选择使数组利用率 > 50% 的最大2的幂边界
  for (b = 0, sum = 0; 2*nn > (1u<<b) && sum != nn; b++)
    if (bins[b] > 0 && 2*(sum += bins[b]) > (1u<<b)) {
      sz = (2u<<b)+1;  // 非包含式，+1为了slot 0
      na = sum;
    }
  *narray = sz;
  return na;  // 返回实际会放入数组的元素数
}

hash 段扩容按照实际占用的键个数分配。大小等于总键数 - 数组容纳数。实际大小为 2^hbits。

static uint32_t counthash(const GCtab *t, uint32_t *bins, uint32_t *narray)
{
  for (total = na = 0, i = 0; i <= hmask; i++) {
    Node *n = &node[i];
    if (!tvisnil(&n->val)) {
      na += countint(&n->key, bins);  // 整数键计入bins
      total++;  // 所有非nil键计数
    }
  }
  *narray += na;  // 整数键数量累加
  return total;   // 返回哈希部分总键数
}

// rehashtab：
total -= na;  // 减去要放入数组的键数
lj_tab_resize(L, t, asize, hsize2hbits(total));

// hsize2hbits: 计算容纳total个键需要的位数
#define hsize2hbits(s) ((s) ? ((s)==1 ? 1 : 1+lj_fls((uint32_t)((s)-1))) : 0)中

resize 执行流程：

void lj_tab_resize(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
{
  // 1. 数组增长
  if (asize > oldasize) {
    if (LJ_MAX_COLOSIZE != 0 && t->colo > 0) {
      // 共址数组必须分离
      array = lj_mem_newvec(L, asize, TValue);
      t->colo = (int8_t)(t->colo | 0x80);  // 标记已分离
      // 复制旧数据
      for (i = 0; i < oldasize; i++)
        copyTV(L, &array[i], &oarray[i]);
    } else {
      // 普通realloc
      array = lj_mem_realloc(L, tvref(t->array), 
                              oldasize*sizeof(TValue), 
                              asize*sizeof(TValue));
    }
    setmref(t->array, array);
    t->asize = asize;
    // 清零新槽位
    for (i = oldasize; i < asize; i++)
      setnilV(&array[i]);
  }
  
  // 2. 创建新哈希部分
  if (hbits) {
    newhpart(L, t, hbits);
    clearhpart(t);
  }
  
  // 3. 数组缩小：截断部分重新插入
  if (asize < oldasize) {
    t->asize = asize;
    for (i = asize; i < oldasize; i++)
      if (!tvisnil(&array[i]))
        copyTV(L, lj_tab_setinth(L, t, (int32_t)i), &array[i]);
  }
  
  // 4. 重新插入旧哈希部分的所有键值对
  if (oldhmask > 0) {
    for (i = 0; i <= oldhmask; i++) {
      Node *n = &oldnode[i];
      if (!tvisnil(&n->val))
        copyTV(L, lj_tab_set(L, t, &n->key), &n->val);
    }
    lj_mem_freevec(g, oldnode, oldhmask+1, Node);
  }
}

在 lj_tab_set 重插入时，如果整数键命中了数组段的 Index，则会直接插入数组段。另外，如果数组段是共址数组，会主动新分配数组并用循环手动拷贝旧值，否则会在内存分配器中拷贝原有数组中值。

总结一下，table 在新插入键值时，会进行重哈希，重新分配数组和哈希表的大小。数组必须保证填充率大于 50%（因此，可能扩容也可能缩容），整数键也因此会重新分配到数组上或者哈希表中。

table.new 的大表会被重哈希缩容吗#

很显然，不会。因为重哈希的触发需要是没有空闲的节点存放哈希键值，而初始化的大表会有充足的空间存放哈希键值（如果你非要 table.new(1000, 0)后插入一个 “hello”: “world” 当我没说）。