★ FEATURED ARTICLE 本文专栏Lua作者主页努力努力再努力wz 今日博客励志语录允许自己暂时平凡但不要因此怀疑未来的无限可能。思维导图Lua 动态类型变量没有固定类型值有类型 ↓ TValue解释器如何表示一个运行时值 ↓ Table把多个 key-value 组织成一个整体 ↓ Table 语法{}、字段名、[]、匿名创建、增删改 ↓ Table 的引用语义赋值与函数传参共享对象 ↓ 尝试自己设计Entry(key, value) 动态数组 ↓ 问题随机访问很快但根据 key 查找要遍历 ↓ 引入哈希由 key 计算存储位置 ↓ 问题哈希冲突、空间利用率 ↓ Lua 的实际设计Table 管理两块不同的数组 ├── TValue[]适合数组索引的整数键 └── Node[]其他键 不适合数组存储的整数键 ↓ 主位置、next 冲突链 ↓ 必要时节点搬迁维护链的归属 ↓ 找不到空闲节点时 Rehash引入不要一上来就背 Table 的 API此前我们已经学习了 Lua 的nil、number、string、boolean、function等类型也逐渐建立了一个认识Lua 的变量没有固定的数据类型但值始终具有类型。继续学习table时很容易只记住以下几个写法localplayer{namewangzhe,level20}print(player.name)player.level30这些语法并不难。但是如果我们把问题再往下一层推进就会发现一些值得思考的地方name为什么不需要写出字段的类型它究竟是结构体字段还是哈希表的 keyplayer.name和player[name]是什么关系player[key]使用的到底是变量名还是变量当前关联的值Table 既能够动态增加字段又能够根据任意 key 查找它的底层还能像 C 结构体一样存储吗如果自己来设计是不是一个动态数组就够了为什么还要引入哈希既然哈希表已经能存储 key-valueLua 为什么还要单独设计数组部分本文就沿着这些问题逐步推导而不是机械地背诵 Lua 的语法和源码。一、先回到动态类型变量、值与 TValue1. 静态类型和动态类型的区别先看 Cinta10;a20;// 合法// a hello; // 类型不匹配a的类型在编译阶段就确定为int后续可以改变它存储的数值却不能直接把这个变量变成字符串类型。而 Lualocala10ahelloatrue同一个变量a先后关联了数值、字符串和布尔值。这说明变量本身没有固定类型变化的是它当前关联的值。但“变量没有固定类型”不等于解释器可以忽略类型。我们想对一个值做加法、比较或者访问它所引用的对象就必须知道这个值究竟是什么类型。2. TValue 帮我们建立运行时模型Lua 解释器内部使用带类型标记的表示来管理运行时值。可以先把TValue抽象成// 仅是方便理解的模型并非 Lua 的真实源码定义structTValue{TypeTag type;// 值的类型标记Value data;// 具体数据或某个对象的引用};例如数字100可以通过类型标记与数值内容表示如果是table类型运行时表示中保存的则是对 Table 对象的引用。需要强调一个严谨的区别并不是 Lua 源码中每个变量本身就是一个单独分配的 TValue 结构体。局部变量可以对应虚拟机栈槽等运行时位置全局变量又涉及环境表。我们这里借助 TValue 建立的是“值具有类型标记和数据内容”的心智模型。所以目前只需要记住变量是访问值的入口值具有类型解释器使用 TValue 这样的运行时表示来记录并处理值。有了这个基础再来看 Table 就自然了。二、为什么需要 Table从结构体过渡到动态复合数据1. 一组数据需要被组织成一个整体假设我们要在游戏服务器中描述一个玩家。这个玩家不仅有 ID还可能具有昵称、等级、在线状态等信息。在 C 中我们很自然地定义structPlayer{intid;std::string name;intlevel;boolonline;};这里的结构体能够把不同类型的数据组织成一个整体。Lua 使用table也能完成类似工作localplayer{id1001,namewangzhe,level20,onlinetrue}从使用场景来看这里的 Table 很像 C 结构体因为它也把一组相关属性组织成了一个整体。2. 但 Table 不能直接等同于结构体二者一个明显区别在于C 普通结构体的成员及其类型在编译期已确定而 Lua Table 的键值映射可以在运行时变化。player.gold1000-- 新增字段player.level30-- 修改原有字段的 valueplayer.id1001-- 同一个 key 可以关联不同类型的 value对于 C 的结构体编译器知道每个成员的大小与布局可以根据结构体起始地址 字段偏移量来访问成员必要时还会考虑内存对齐。结构体对象的成员通常位于一段连续的虚拟地址空间中字段名本身不需要作为 key 保存在每个对象内部。Lua Table 则不同。字段可以动态增加或删除因而不能简单依赖这种固定的字段偏移布局。3. Table 的本质更接近关联容器实际上Lua Table 是一个key-value 映射容器关联数组。刚才的玩家localplayer{id1001,namewangzhe,level20}在逻辑上可以理解为KeyKey 类型ValueValue 类型idstring1001numbernamestringwangzhestringlevelstring20number这里最重要的认识是所谓字段名本质上就是 Table 的 keyTable 通过 key 找到对应的 value。因此Table 不只有“结构体”的用途。我们还可以用它表示数组、字典、集合或其他业务数据结构。与常见的 Cstd::unordered_mapstd::string, int不同Lua Table 不要求所有 key 都是同一种类型也不要求所有 value 都是同一种类型。要注意这是 Lua 动态类型和关联容器接口的特点“哈希表”这种抽象数据结构本身并不天然要求同质类型C 的类型约束来自具体模板实例。三、Table 的创建和访问真正用作 key 的是什么1.{}是一个 Table 构造表达式Lua 最常见的创建方式如下localplayer{namewangzhe,level20}这里的{ ... }用于创建一个新的 Table 对象player是我们声明的局部变量它获得对新对象的引用。也可以先创建空 Table再动态增加映射localplayer{}player.namewangzheplayer.level20并不是每个 Table 都必须先有名字。例如直接作为返回值或参数functioncreatePlayer()return{namewangzhe,level20}endlocalplayercreatePlayer()functionprintPlayer(p)print(p.name)endprintPlayer({namezhangsan,level10})这类写法可以借用“匿名对象”来理解创建对象时不需要先绑定到某个变量名。但“匿名创建”不代表对象必然很快销毁只要还有有效引用能访问它对象就仍然可达。2.player.name是player[name]的简写例如localplayer{namewangzhe}print(player.name)print(player[name])两条语句都访问字符串键name对应的值。实际上定义时的namewangzhe也相当于[name]wangzhe所以name只是特定语法位置上字符串键的简写并不是一个静态类型的成员声明。3.[]中放的是表达式求出的值才是 key这是一个特别容易混淆的问题。localplayer{namewangzhe}localkeynameprint(player[key])-- wangzheprint(player[name])-- wangzhe执行player[key]时Lua 并不是把变量的名字key当作字符串键而是先求出变量key当前关联的值name再使用这个带有类型信息的值去查找 Table。因此player[key]-- 当前 key 变量的值比如 nameplayer[key]-- 字面量字符串 keyplayer.key-- 同样是字面量字符串 key它们并不天然相等。4. key 本身也是值因此它也有类型例如localt{}t[name]wangzhet[1001]truet[false]3.14这就创建了三种不同类型的键表达式用作 key 的值类型t[name]namestringt[1001]1001numbert[false]falseboolean类型属于键的实际值而不是某个变量名。当用于索引的变量重新关联其他值时下次索引可以使用另一种 key 类型但之前插入的映射并不会跟着变。localt{}localkeynamet[key]wangzhekey1001t[key]helloprint(t[name])-- wangzheprint(t[1001])-- hello这里还有两条规则nil和 NaN 都不能作为 Table 的 key而整数1与浮点数1.0在 Lua 5.4 中表示同一个 Table 键整数值的浮点 key 会规范化为整数键。字符串1则与数字1是不同的 key。四、Table 如何增加、修改与删除键值对现在我们已经明确Table 存储的是键值映射而不是把变量名作为字段实体存储起来。那么增删改就很好理解了。localt{namewangzhe}t[level]20-- 原来没有这个 key新增映射t[name]zhangsan-- 已经有这个 key修改 valuet[level]nil-- 删除 level 对应的映射1. 能不能直接把一个已有 key 改成另一个 key例如最初name → wangzhe我们想直接修改这条映射的 key让它变为123 → wangzheLua 没有一个操作是“原地修改已有条目的 key 身份”。通常只能使用新 key 建立映射再移除旧映射localt{namewangzhe}t[123]t[name]t[name]nil但这两个操作的意义是新建或更新映射再删除旧映射不是对旧 key 直接改名。2. 给 value 赋值nil究竟是不是删除localt{namewangzhe}t[name]nil从语言语义来看name已经不再属于这张 Table 的有效键值映射。t[name]得到nilpairs(t)也不会将它作为有效条目返回。如果原本没有这个 keylocalt{}t[unknown]nil仍然不会产生一条“value 是 nil 的有效映射”。因此nil表示键缺失而不是一个可正常保留在 Table 中的字段值。与之不同false是一个合法 value。不过要区分逻辑层面和内存层面逻辑删除立即生效并不等于底层 Node 槽位或 TValue 数组空间在这条语句执行时立刻被物理释放。例如对数组部分中的元素赋nil底层数组不必因此缩短对于哈希部分旧节点的存储信息也可能暂时保留之后再由内部调整流程处理。以上描述的是普通 Table 的直接存储语义。元表的__index、__newindex可能改变部分访问和赋值行为初学 Table 时可以先不引入。五、为什么变量赋值和函数传参会共享 Table 对象现在回到第一部分的 TValue 心智模型。对于number等简单值运行时值表示可以直接保存数值内容对于 Table运行时值表示保存的是一个对象引用。localt1{level20}localt2t1 t2.level30print(t1.level)-- 30这不是t2拷贝了一份完整的 Table。实际上两个变量的运行时值保存了同一个 Table 对象的引用。所以通过t2.level 30修改对象内部字段时t1再访问同一个对象自然能够观察到结果变化。1. 函数传参也一样复制引用这个值localplayer{level20}functionupdatePlayer(p)p.level30endupdatePlayer(player)print(player.level)-- 30这里的形参p是一个新的局部变量位置调用时得到的实参值是对原 Table 的引用。Lua 的参数传递仍然是值传递传递的值恰好是对象引用。所以我们可以观察到共享对象的效果但不应该把它和 C 的T引用形参直接画等号。2. 修改对象与重新给形参赋值是两回事再看localplayer{level20}functionupdatePlayer(p)p{level100}endupdatePlayer(player)print(player.level)-- 20为什么这次player.level没有变化因为p { level 100 }的行为是新建一个 Table 对象让局部变量 p 改为引用新对象。函数外面的player仍然引用原来的对象。调用刚开始 player ──────┐ ├── Table A { level 20 } p ───────────┘ 执行 p { level 100 } 后 player ───────── Table A { level 20 } p ────────────── Table B { level 100 }所以要区分p.level 30通过引用修改共享对象。p { level 100 }仅改变局部形参自己保存的引用。这样我们就把 Table 的创建、变量赋值、函数传参以及引用共享这几件事联系起来了。六、如果自己设计 Table能不能只使用动态数组到这里我们已经会使用 Table也认识了它的引用语义。接下来换个角度如果让我们自己实现一个支持任意 key-value 的容器该怎么设计1. 一个非常自然的方案Entry 动态数组我们可以先设计一个数组每个元素保存一组 key-value。// 伪代码忽略 TValue 的真实源码定义structEntry{TValue key;TValue value;};std::vectorEntryentries;例如数组下标 key value [0] id 1001 [1] name wangzhe [2] level 20这种方案显然能工作新增键值对时往后追加容量不足时扩容还可以提前预留容量避免频繁扩容。而且数组连续存储具有较好的局部性对 CPU Cache 相对友好。但是它解决的是“如何存储”并没有解决“如何根据任意 key 快速定位”。2. 数组随机访问快不代表按 key 查找快例如我们访问print(player[level])我们知道的是 key level但并不知道它刚好位于数组下标 2。如果数组没有额外的索引结构只能依次比较[0] key id → 不匹配 [1] key name → 不匹配 [2] key level → 找到对于具有n个元素的普通无序动态数组按任意 key 查找通常需要 O(n) 时间。数组能 O(1) 地访问entries[2]前提是已经知道下标 2但是level本身并不是下标。这是我们推导到哈希表的关键。3. 哈希尝试把 key 映射成数组下标我们可以继续保留 Node 或 Entry 数组只是改变定位方式。给定 key先通过哈希函数计算哈希值再根据数组容量获得主位置。示意公式key → hash(key) → 映射到数组主位置 → 检查 key → value假设用一个简化的整数哈希模型哈希位置 hash(key) % capacity这里有一个重要区分哈希值与哈希主位置不是同一回事。哈希值是计算结果主位置则还依赖当前哈希数组的大小或位置映射规则。不同 key 可能算出相同主位置这就引出了哈希冲突。4. 我们自己的方案线性探测例如数组容量为 7假设三个整数 key 的初始位置都是 3key 10 → 位置 3 key 17 → 位置 3 key 24 → 位置 3插入10后位置 3 已经被占用。再插入17时就从位置 3 开始查找后续空位插入24时继续探测可能最终得到位置 310 位置 417 位置 524查找24时先到位置 3发现不匹配再探测 4、5。这就是哈希表的一种经典实现开放寻址中的线性探测。它并不是错误的设计。即使会发生探测好的哈希分布、适当的容量与装载因子控制仍然能使常见操作的期望成本接近 O(1)。只是极端情况下仍可能退化到 O(n)。但Lua 的哈希部分并没有直接采用这种逐个探测相邻位置的方案。它使用的是 Node 数组与冲突链相结合的设计。七、Lua 的实际内存组织为什么是 TValue[] Node[]1. 首先明确Table 不是一个大数组Lua 5.4 内部的 Table 对象可以简化理解为// 简化模型省略元表、GC、容量等其他字段structTable{TValue*array;// 数组部分Node*node;// 哈希部分};这里容易产生一个误解既然两部分都是数组是否本质上还是同一个数组不是。array和node分别指向两块不同的数组存储区域元素类型也不同。例如localt{10,20,30,namewangzhe,level5}在语义上相当于localt{[1]10,[2]20,[3]30,[name]wangzhe,[level]5}下图给出一种符合这种输入特点的概念性布局并不承诺真实运行时的精确容量和 Node 槽位顺序。注意这里涉及三个不同的存储对象Table 结构体、TValue 数组、Node 数组。其中两块数组各自连续但不必彼此相邻Table 对象本身不需要与数组存放在同一块内存里。2. Node[] 既然能够存储 key-valueTValue[] 又是干什么的这是理解 Lua 混合设计最关键的问题。假设 Table 只有哈希部分那么localt{10,20,30,40}实际上存在四个整数键1、2、3、4。如果把它们全部放进 Node 数组就需要在每个 Node 中保存 key、value 和冲突链信息。但这些 key 恰好能直接对应数组索引。既然如此为什么还要显式存储1、2、3、4这些 key 呢我们完全可以用一个TValue[]Lua key C 数组下标 TValue 保存的 value 1 0 10 2 1 20 3 2 30 4 3 40访问t[3]时可以直接根据整数索引定位到对应数组槽位既不需要额外保存 key也不需要哈希定位和冲突链遍历。这里的 TValue 仍然能够保存不同类型的值所以并不要求数组每个元素都是同一种 Lua 数据类型。由此就自然产生了 Lua 的设计数组部分专门优化适合用数组下标表示的整数键哈希部分负责其他键值映射。3. 不是所有整数 key 都进入数组部分例如localt{}t[1]10t[2]20t[1000000]30如果为了保存1000000直接分配一个长度达到一百万的 TValue 数组中间就会空出大量槽位造成明显浪费。因此Lua 并不是“只要是整数 key就一定放进 TValue[]”。它会根据整数键的分布密度和容量情况决定数组部分适合覆盖的索引范围。超出这个范围的整数键也可以放进 Node[]。反过来假设原来数组部分仅覆盖14后来又不断插入5、6、7、8在后续空间调整时Lua 也可能扩大数组部分并把部分整数键从哈希区域迁移过来。所以我们可以把两部分理解为对同一个 Table 中键值对的分流存储而不是分别对应两种对外公开的 Table。八、Node 哈希部分冲突链和节点搬迁到底怎么工作现在我们已经知道了Lua 使用连续的 Node 数组来存储哈希部分。接下来再认识 Node 内部的链接结构。1. Node 不只是 key value我们可以抽象为// 概念模型不等于 5.4 中 Node 的精确 C 布局structNode{TValue key;TValue value;intnext;};这里的next不是普通的指针而是相对于当前 Node 位置的整数偏移量。实际 5.4 源码为了控制 Node 大小对 key 的类型标记与值字段做了紧凑布局。例如Node[2] 的 next 5意味着沿 Node 数组移动到Node[2 5]即Node[7]。next 0表示这条链没有后继节点。偏移量也可以是负数。这样做的目的就是当不同 key 映射到同一个哈希主位置时能够把相关节点组织起来。2. 第一种冲突旧节点就在自己的主位置假设A 的主位置 2 B 的主位置 2先插入 A直接放入Node[2]。随后插入 B 时位置 2 已被 A 占据。Lua 检查后发现A 本来就属于主位置 2所以 A 不需要搬迁。Lua 寻找一个空闲 Node假设找到Node[7]将 B 放进去再通过next建立链接Node[2]A主位置 2 │ │ next 5 ▼ Node[7]B主位置 2现在查找 B就先根据 B 的 key 定位主位置 2发现 A 不匹配后沿next直接跳到Node[7]而不是逐个检查 3、4、5、6。但要注意Lua 在寻找空闲 Node时仍然可能扫描数组槽位它只是不会在正常的冲突链查找中采用上述线性探测规则。3. 第二种冲突旧节点只是借用了别人的主位置我们现在再插入 C假设C 的主位置 7问题出现了Node[7]已经存着 B。但 B 的主位置明明是 2B 只是因为与 A 冲突才被暂时安排在 7。所以 Lua 在插入 C 时会先判断占据位置 7 的旧节点 B其自己的哈希主位置是不是 7发现不是。那么 Lua 会把 B 移到其他空闲槽位假设Node[6]修正 A 原来的冲突链再把真正以 7 为主位置的 C 放进去。于是存储关系变为主位置 2 Node[2] A ──next4── Node[6] B 主位置 7 Node[7] C查询 A 直接命中 2查询 B 从 2 沿链到 6查询 C 直接命中 7。4. 为什么不直接把 C 接在 B 的 next 后面我们此前其实提出过另一种方案既然 C 的主位置 7 被 B 占据那就再找个空位 6让 B 的next指向 CNode[2] A → Node[7] B → Node[6] C对于这个简单例子如果相应的链接正确维护那么从位置 7 出发确实也能通过 B 找到 C。这个想法并不是绝对不可行。但问题在于A、B 的主位置是 2而 C 的主位置是 7。如果把 C 直接接在 B 后面就把不同主位置的查找路径混在一起了。后续插入、查找、维护链时不仅要处理真正共享主位置的冲突还可能经过其他主位置的节点若 B 已经有后继节点还需要小心维护原链不能随意覆盖next。Lua 选择的是另一种约束一个节点如果不在自己的主位置那么占据它主位置的节点必须属于这个主位置。在这个约束下每条有效冲突链可以围绕同一个哈希主位置组织不用把不同主位置的节点随意混在一起。这不是彻底消除哈希冲突也不一定是减少冲突链的数量真正的目的是减少无关节点混入查找路径保持链的组织规则清晰。九、Node 空间不足后Rehash 不只是简单扩容我们现在还差最后一块拼图假设新 key 的主位置被占用Lua 想找一个空闲 Node却已经找不到可用的空闲节点该怎么办一个自然的思路就是扩容。然而对于 Lua Table 而言情况比普通动态数组扩容复杂一些。1. 不是只考虑 Node 数组长度因为 Table 本身有两部分Array PartTValue[] Hash Part Node[]因此 Lua 触发 Rehash 时会重新统计相关键的分布并决定两部分的合适容量。例如某些整数键原来在哈希部分重新调整时发现它们足够密集就可能迁移到数组部分。这种情况下Node 数组的容量并不一定要变大甚至可能比原来更小。2. Node 容量变化为什么还要重新安置键值对因为哈希位置不仅与 key 的哈希结果有关也与哈希数组容量有关。假设一个 key 的哈希值始终是13我们用取模方式演示容量 4 13 % 4 1 容量 8 13 % 8 5那么key 的哈希值没有发生变化但是映射到数组中的哈希主位置发生了变化。之前以旧容量建立的 Node 位置与next链可能已经不适用于新容量。因此需要重新安置键值对并按新位置重建冲突链。十、把 Table 的语言模型与底层结构串起来我们最后回到最初那个玩家对象localplayer{id1001,namewangzhe,level20,onlinetrue}player.gold1000functionupgrade(p)p.levelp.level1endupgrade(player)print(player.level)-- 21现在我们可以从三个层面理解这段代码。第一层语言层面。{}创建 Table 对象Table 管理 key-value 映射player.level等价于用level这个字符串 key 访问值新增字段只是在运行时增加映射。第二层运行时值层面。player当前关联的是一个 table 类型的值其内部保存对实际 Table 对象的引用。调用upgrade(player)时把这个引用值传给形参p所以p.level修改的仍是原对象。第三层存储实现层面。Table 对象内部管理数组部分和哈希部分。像name、level这样的字符串 key 需要经过哈希部分适合数组存储的整数 key 则可以直接索引 TValue 数组。哈希冲突靠 Node 之间的next链组织空间不足时可能触发 Rehash。将三个层次放在一起Lua 代码 local player { ... } │ ▼ 变量关联 table 类型的运行时值 │ ▼ TValue 表示类型标记 Table 对象引用 │ ▼ Table 对象管理两块数组 ├── TValue[] 数组部分 │ └── 适合数组索引的整数键 │ └── Node[] 哈希部分 ├── key ├── value └── next冲突链偏移量 │ ▼ 主位置、冲突链、节点搬迁 │ ▼ 必要时 Rehash最后总结回顾我们这一整条推导链实际上并没有什么需要死记硬背的地方。最开始我们从 Lua 的动态类型出发认识到变量没有固定类型但值具有类型并通过 TValue 了解解释器如何表示运行时的值。接着我们希望像 C 结构体一样把游戏玩家的多个字段组织成一个整体于是引出了table。但是 Table 比普通结构体更加灵活它能够动态增加、修改、删除映射并允许不同 key 和 value 具有不同的类型。再往下一层我们尝试用动态数组来实现一个 Entry 保存 key 和 value插入时追加容量不足时扩容。这个思路完全可行但根据任意 key 查找时必须逐个比较于是自然需要哈希映射来提高查找效率。而 Lua 又发现对于密集的整数键单独保存 key 并进行哈希计算没有必要。因此它将适合数组存储的键值对放入 TValue 数组把其他键值对交给 Node 哈希数组形成了混合存储结构。最后为了解决哈希冲突Lua 使用 Node 内部的next偏移量连接冲突节点并通过必要的节点搬迁维护不同哈希主位置的链结构当存储空间无法继续满足插入要求时再进行 Rehash。所以如果要用一句话概括本文Lua Table 对外是一个统一、动态的 key-value 容器对内则把不同特征的键分配到适合的存储结构中并通过哈希冲突处理和 Rehash 维持运行时效率。至此我们已经能够在“不必自己造 Lua 解释器”的深度上完整解释 Table 的语法、引用共享以及主要内存组织方式。后面阅读 Lua 游戏服务器业务代码时就可以把注意力更多放在Table 中到底保存了哪些游戏状态、这些状态由谁持有、传给了哪些函数、是否会发生共享修改上。
阅读完成 · 觉得有帮助？
