4.表与数据结构取舍
4.1 知识点
表充当多种数据结构
前几篇一直在聊表的引用、拷贝。
这篇回到 table 本身。
Lua 里常用容器基本都绕不开 table。
它可以当数组、字典、集合、队列来写。虽然可以充当成各种数据结构，但如果用错场景，成本会差很多。
比如战斗里一帧插删几百次，和配置表里按 id 查一行数据，肯定不是一套写法。
所以真正要先想清楚的是：这张表到底打算当什么用。
连续列表当数组，id 映射当字典，判重当集合，队列的话维护 head/tail 出队，别 table.remove(t, 1) 删头，这样移动太多元素。
数组语义
key 从 1 开始连续往上长，中间没洞，就按数组来用。
local skills = { 1001, 1002, 1003 }
print(skills[1]) -- 输出：1001
print(#skills) -- 输出：3
待释放技能 id、Buff 列表、本帧要 tick 的表现 id，项目里最常见的就是这种。
这种表适合用：
list[i]#listipairs- 两参数
table.insert(list, value)尾插
但前提是它真的是连续数组。
一旦中间有洞，或者业务上已经混了字符串 key，就别再把它当“纯数组”看。
字典语义
按 id 查配置行、按名字查对象、运行时做映射表，走的是字典语义。
key 不要求连续，甚至可以根本不是数字。
local skillMap = {
[1001] = { name = "FireBall" },
[1005] = { name = "IceBolt" },
["passive_1"] = { name = "Shield" }
}
print(skillMap[1001].name) -- 输出：FireBall
print(skillMap[1002]) -- 输出：nil
skillMap[1001] 查一次就能拿到配置行。
配置表、对象缓存、id 到实例的映射，一般都是查一次就行。
字典别拿 # 当长度，也别指望 ipairs 扫全表——空洞、pairs 顺序那套，语法篇 10.表 已经讲过，这里不赘述。pairs 能遍历，但顺序不能当 UI 排序、帧同步 Tick 顺序。这种时候单独挂一张顺序表。
顺序表
字典负责查，顺序表负责「按什么先后走」。
两张表分工：map 存数据，order 存 id 列表；遍历 order，再去 map 里取。
帧同步 Tick Entity 就是典型场景。实体按 id 查，entityMap 存运行时数据；每帧谁先谁后，各端必须一致，不能直接使用 pairs(entityMap) 不可靠顺序进行遍历：
local entityMap = {
[101] = { hp = 100 },
[102] = { hp = 80 },
[103] = { hp = 120 }
}
-- 每帧 Tick 顺序，各端共用同一份
local entityOrder = { 101, 102, 103 }
for _, entityId in ipairs(entityOrder) do
local entity = entityMap[entityId]
entity.hp = entity.hp - 1
print(entityId, entity.hp)
-- 输出：101 99 / 102 79 / 103 119，各端按同一顺序扣血
end
entityMap 只管 lookup，Tick 先后交给 entityOrder。
新 Entity 入战，map 里塞数据，order 尾插 id 就行。
直接赋值和插入对比
t[k] = v 是往某个 key 写值，不会把后面的元素往后挪。
local t = { 10, 20, 30 }
t[2] = 99
print(t[1], t[2], t[3]) -- 输出：10 99 30
print(#t) -- 输出：3
table.insert(t, pos, value) 是在数组段里挤位置。
从 pos 开始，后面的元素会整体后移一位。
local t = { 10, 20, 30, 40 }
table.insert(t, 2, 15)
print(t[1], t[2], t[3], t[4], t[5]) -- 输出：10 15 20 30 40
print(#t) -- 输出：5，2 号位插入 15，原 20 被挤到后面
所以这两句实际效果不一样——承接上面 { 10, 20, 30, 40 } 那张表：
t[2] = 15 -- 只覆盖 2 号槽，表长还是 4
table.insert(t, 2, 15) -- 2 号位挤进新元素，后面整体后移，表长变 5
前者只改一个槽。
后者是在 2 号位插入，原来的 2 号位和后面元素一起往后搬。
table.insert 尾插
两个参数的 table.insert 是尾插。
local pending = { "A", "B" }
table.insert(pending, "C")
print(#pending) -- 输出：3
print(pending[3]) -- 输出：C
待处理事件、日志行、临时列表，一般是字节往后加的话，那使用尾插就够了。
没有明确需求，最好不要往中间插。因为会涉及一些搬家开销。
table.insert 中间插入
三个参数的 table.insert 会在 pos 处插入，并把 pos 及之后的元素往后搬。
local nums = { 10, 20, 30, 40 }
table.insert(nums, 2, 15)
print(nums[1], nums[2], nums[3], nums[4], nums[5])
-- 输出：10 15 20 30 40
插得越靠前，要搬的元素越多。
插到 1 号位，基本就是整段平移。
中间插入不能说完全禁止，但是最好别在热路径里频繁调用。
例如在战斗 Tick、红点刷新、表现队列这类地方，如果大表频繁中间插入，Profiler 里很容易看到这块开销，影响性能。
table.remove 头删的问题
table.remove(t, 1) 会删掉第一个元素，然后把后面的元素整体前移。
local tasks = { "move", "attack", "idle" }
table.remove(tasks, 1)
print(tasks[1], tasks[2]) -- 输出：attack idle
print(#tasks) -- 输出：2
demo 里三行代码看不出问题。
但战斗帧里如果每帧对几百上千条指令 remove(1)，这块开销会叠起来。
热路径 FIFO 队列别这么写。而是最好用 head / tail 更，见后文。
table 作为集合
判重、判存活、判已访问，用 key 占位就够了。
local visited = {}
visited[1001] = true
visited[1002] = true
print(visited[1001] ~= nil) -- 输出：true
print(visited[2001] ~= nil) -- 输出：false
visited[1001] = nil
print(visited[1001] ~= nil) -- 输出：false
值写 true 就行。当然用 1 也行，一般只是个占位。
真要附带访问时间、来源节点、权重，再把 value 写成一张小表：
visited[1001] = {
visitTime = 12345,
fromNode = "A"
}
普通判重集合别一上来就套这种结构。
同时得注意，别为了一个集合，又维护一份数组来回扫，比如下面这种写法就别用，判 alive 得把整个数组从 1 扫到尾，性能很差：
local aliveList = { 1001, 1002, 1003 }
local function IsAlive(id)
for i = 1, #aliveList do
if aliveList[i] == id then
return true
end
end
return false
end
print(IsAlive(1001)) -- 输出：true
print(IsAlive(2001)) -- 输出：false，2001 不在列表里，但得先扫完整张表才知道
逻辑上看起来能跑，但 Entity 一多、每帧判很多次，就是 O(n)。上面 visited[1001] ~= nil 查一次 key 就搞定了，是 O(1)。
table 作为队列
入队往 tail 写，出队只动 head，避开 table.remove(t, 1)。
local q = {}
local head, tail = 1, 0 -- head 队头，tail 队尾；head > tail 表示空队列
local function Enqueue(v)
tail = tail + 1
q[tail] = v -- 入队：往 tail 写，不碰 head
end
local function Dequeue()
if head > tail then
return nil -- 队列为空
end
local v = q[head]
q[head] = nil -- 出队后断掉旧引用，方便 GC
head = head + 1 -- 只挪队头，不像 remove(1) 那样搬后面一截
return v
end
Enqueue("A")
Enqueue("B")
print(Dequeue()) -- 输出：A，先进先出
print(Dequeue()) -- 输出：B
print(Dequeue()) -- 输出：nil，队列已空
项目很多地方使用队列，比如待执行指令、网络消息、异步回调排队。
注意q[head] = nil 也不能省略，出队后要旧引用断掉，方便 GC 回收，避免内存泄漏。
head 走太远以后，表会变得稀疏——前面大量 key 已经是 nil，但 slot 还占着：
for i = 1, 5 do
Enqueue("cmd")
end
for i = 1, 4 do
Dequeue()
end
print(head) -- 输出：5，队头已经挪到 5
print(q[1]) -- 输出：nil，1~4 号位是空槽，但表还在占坑
print(q[tail]) -- 输出：cmd，有效数据只剩 tail 这一格
队列是长期对象的话，空闲时可以压缩成新表，把有效段挪回 1 号位；或者队列已空，直接 q, head, tail = {}, 1, 0 换一张干净的：
-- 把 [head, tail] 里的有效元素，紧凑拷到新表
local function CompactQueue(q, head, tail)
local newQ = {}
local newTail = 0
for i = head, tail do
newTail = newTail + 1
newQ[newTail] = q[i] -- 从 1 号位重新排，丢掉前面的空槽
end
return newQ, 1, newTail -- head 回到 1，tail 变成有效长度
end
q, head, tail = CompactQueue(q, head, tail)
print(head) -- 输出：1，队头重新贴到数组段开头
print(q[1]) -- 输出：cmd，前面 1~4 的空槽不再占坑
但我觉得最重要的还是先把热路径里的 remove(1) 干掉。
数组段和哈希段
前面聊的尾插顺手、中间 insert/remove 要搬元素、混 key 时 #/ipairs ，粗略讲都可以归结成：table 里有一块数组段放连续 1..n，另有一块哈希段放其余 key。
混用两种 key 的表要格外注意：
local mixed = {
"A",
"B",
role = "cache"
}
print(mixed[1]) -- 输出：A，1、2 在数组段
print(mixed.role) -- 输出：cache，role 在哈希段
for i, v in ipairs(mixed) do
print(i, v) -- 输出：1 A / 2 B，ipairs 只走数组段，扫不到 role
end
数组段怎么切、什么时候 rehash，跟 Lua 5.x、LuaJIT、项目魔改运行时都有关。真想抠实现，再去翻 ltable.c 也不迟。
总结
同一张 table，当数组、字典、集合、队列写，写法不一样，成本也不一样。
连续 1..n 当数组。
id 映射当字典，顺序走 order 表。
判重用集合。
FIFO 用 head / tail。
t[k] = v 是写槽，而不是插入。table.insert(t, pos, v) 和 table.remove(t, 1) 都会涉及搬家，热路径里要谨慎。
4.2 知识点代码
Lesson4_表与数据结构取舍.lua
print("**********表与数据结构取舍************")
print("**********知识点一 表充当多种数据结构************")
local arrayList = { 1001, 1002, 1003 }
local mapList = {
[1001] = "FireBall",
[1002] = "IceBolt"
}
print("arrayList[1]：", arrayList[1]) -- 输出：1001，按数组下标取
print("mapList[1001]：", mapList[1001]) -- 输出：FireBall，按 key 查
print("**********知识点二 数组语义************")
local skills = { 1001, 1002, 1003 }
print("skills[2]：", skills[2]) -- 输出：1002，数组按下标取值
print("#skills：", #skills) -- 输出：3，连续 1..n 时 # 才靠谱
for i, skillId in ipairs(skills) do
print("技能下标和技能 id：", i, skillId) -- 输出：1 1001 / 2 1002 / 3 1003
end
print("**********知识点三 字典语义************")
local skillMap = {
[1001] = { name = "FireBall" },
[1005] = { name = "IceBolt" },
["passive_1"] = { name = "Shield" }
}
print("skillMap[1001].name：", skillMap[1001].name) -- 输出：FireBall
print("skillMap[1002]：", skillMap[1002]) -- 输出：nil，查不到就是 nil
print("**********知识点四 顺序表************")
local entityMap = {
[101] = { hp = 100 },
[102] = { hp = 80 },
[103] = { hp = 120 }
}
local entityOrder = { 101, 102, 103 }
for _, entityId in ipairs(entityOrder) do
local entity = entityMap[entityId]
entity.hp = entity.hp - 1
print("Tick：", entityId, entity.hp) -- 输出：101 99 / 102 79 / 103 119，各端顺序一致
end
print("**********知识点五 直接赋值和插入对比************")
local direct = { 10, 20, 30 }
direct[2] = 99
print("direct[2]：", direct[2]) -- 输出：99，只覆盖 2 号位
print("direct[3]：", direct[3]) -- 输出：30，后面的元素不会被搬动
print("#direct：", #direct) -- 输出：3
local insertDemo = { 10, 20, 30, 40 }
table.insert(insertDemo, 2, 15)
print("insertDemo[2]：", insertDemo[2]) -- 输出：15，2 号位插入新元素
print("insertDemo[3]：", insertDemo[3]) -- 输出：20，原 20 被挤到后面
print("#insertDemo：", #insertDemo) -- 输出：5，和 t[2]=15 完全不是一回事
print("**********知识点六 table.insert 尾插************")
local tailList = { "A", "B" }
table.insert(tailList, "C")
print("#tailList：", #tailList) -- 输出：3
print("tailList[3]：", tailList[3]) -- 输出：C，两参数 insert 是尾插
print("**********知识点七 table.insert 中间插入************")
local midList = { 10, 20, 30, 40 }
table.insert(midList, 2, 15)
print("midList[1]：", midList[1]) -- 输出：10
print("midList[2]：", midList[2]) -- 输出：15，新元素插进 2 号位
print("midList[3]：", midList[3]) -- 输出：20，原 20 被往后挤
print("#midList：", #midList) -- 输出：5
print("**********知识点八 table.remove 头删的问题************")
local headRemove = { "move", "attack", "idle" }
local removedTask = table.remove(headRemove, 1)
print("removedTask：", removedTask) -- 输出：move，被删掉的元素会返回
print("headRemove[1]：", headRemove[1]) -- 输出：attack，头删后后面整体前移
print("headRemove[2]：", headRemove[2]) -- 输出：idle
print("#headRemove：", #headRemove) -- 输出：2
print("**********知识点九 table 作为集合************")
local aliveSet = {}
aliveSet[1001] = true
aliveSet[1002] = true
print("1001 在集合里：", aliveSet[1001] ~= nil) -- 输出：true
print("2001 在集合里：", aliveSet[2001] ~= nil) -- 输出：false
aliveSet[1001] = nil
print("移除后 1001：", aliveSet[1001] ~= nil) -- 输出：false，赋 nil 等于从集合里删掉
local visited = {}
visited[1001] = {
visitTime = 12345,
fromNode = "A"
}
print("visited 附带信息：", visited[1001].visitTime) -- 输出：12345，判重之外还要附带字段时，value 再用小表
local aliveList = { 1001, 1002, 1003 }
local function IsAlive(id)
for i = 1, #aliveList do
if aliveList[i] == id then
return true
end
end
return false
end
print("IsAlive 2001：", IsAlive(2001)) -- 输出：false，能跑但每次 O(n) 扫整张表，别这么写
print("**********知识点十 table 作为队列************")
local q = {}
local head, tail = 1, 0 -- head 队头，tail 队尾；head > tail 表示空队列
local function Enqueue(v)
tail = tail + 1
q[tail] = v -- 入队：往 tail 写
end
local function Dequeue()
if head > tail then
return nil
end
local v = q[head]
q[head] = nil -- 出队后断掉旧引用
head = head + 1 -- 只挪队头，不像 remove(1) 那样搬元素
return v
end
Enqueue("cmd_move")
Enqueue("cmd_attack")
print("Dequeue：", Dequeue()) -- 输出：cmd_move，先进先出
print("Dequeue：", Dequeue()) -- 输出：cmd_attack
print("Dequeue：", Dequeue()) -- 输出：nil，队列已空
for i = 1, 5 do
Enqueue("cmd")
end
for i = 1, 4 do
Dequeue()
end
print("head：", head) -- 输出：5，队头走远，前面 1~4 号是空槽
print("q[1]：", q[1]) -- 输出：nil
local function CompactQueue(q, head, tail)
local newQ = {}
local newTail = 0
for i = head, tail do
newTail = newTail + 1
newQ[newTail] = q[i]
end
return newQ, 1, newTail
end
q, head, tail = CompactQueue(q, head, tail)
print("压缩后 head：", head) -- 输出：1
print("压缩后 q[1]：", q[1]) -- 输出：cmd，有效数据贴回数组段开头
print("**********知识点十一 数组段和哈希段************")
local mixed = {
"A",
"B",
role = "cache"
}
print("mixed[1]：", mixed[1]) -- 输出：A，1、2 在数组段
print("mixed.role：", mixed.role) -- 输出：cache，role 在哈希段
for i, v in ipairs(mixed) do
print("ipairs mixed：", i, v) -- 输出：1 A / 2 B，ipairs 只走数组段
end
print("**********知识点十二 总结************")
print("连续 1..n 当数组，id 映射当字典") -- 输出：连续 1..n 当数组，id 映射当字典
print("业务顺序用 order 表，别赌 pairs 顺序") -- 输出：业务顺序用 order 表，别赌 pairs 顺序
print("集合查 key，别数组 for 扫") -- 输出：集合查 key，别数组 for 扫
print("队列用 head/tail，别 remove(1) 删头") -- 输出：队列用 head/tail，别 remove(1) 删头
print("t[k]=v 是写槽，insert/remove 会搬元素") -- 输出：t[k]=v 是写槽，insert/remove 会搬元素
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
