4.表与数据结构取舍
4.1 知识点
表和数据结构
Lua 里表可以当数组、字典、集合、队列，但用法不同，成本差很多。
使用表当数据结构前，先想清楚几个问题：
- 按下标顺序访问还是按 id 查？
- 顺序会不会影响结果？
- 只判存在还是要完整数据？
- FIFO 会不会在热路径里频繁出入队？
数组语义
从 1 开始连续增长，中间不留洞，就按数组来写。
local skills = { 1001, 1002, 1003 }
print(skills[1]) -- 输出：1001
print(#skills) -- 输出：3
数组语义的前提是“连续”。只要中间可能有 nil，或者混了其他的业务 key，就不能把 # 当稳定获取长度的API。
数组常见操作：
list[i]按下标读写。#list只用于连续列表。ipairs(list)只用于连续列表。table.insert(list, value)用于尾插。
热路径里，尾插通常没问题。
但是如果频繁中间插入、头部删除，就得用别的方式处理了。
字典语义
按 id 查配置行、按名字查对象、按实例 id 找运行时对象，走字典语义。
local skillMap = {
[1001] = { name = "FireBall" },
[1005] = { name = "IceBolt" },
["passive_1"] = { name = "Shield" }
}
print(skillMap[1001].name) -- 输出：FireBall
print(skillMap[1002]) -- 输出：nil
字典的重点是通过key得到value。遍历顺序是不可靠的。
不能拿 # 当数量。
业务需要数量，需要自己维护 count；如果业务需要顺序，单独维护顺序表。
顺序表
字典负责查，顺序表负责“按什么顺序处理”。
有时候一些场景下，必须得按一定顺序遍历处理。比如，在帧同步 Tick 里这个边界很重要，因为要保证一致性。
实体按 id 查用 entityMap，Tick 顺序用 entityOrder。不要把 pairs(entityMap) 的遍历结果当业务顺序。
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(entityId, entity.hp)
-- 输出：101 99 / 102 79 / 103 119，各端按同一份顺序 Tick
end
新实体入战时，entityMap[id] = entity，再把 id 尾插进 entityOrder。
删除时看项目需求：可以从顺序表移除，也可以标记失效后帧末批量整理。
写槽和插入
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
这两个操作不能混为一谈：
t[2] = 15 -- 覆盖 2 号位
table.insert(t, 2, 15) -- 在 2 号位插入，后面元素整体后移
中间插入和头删
尾插通常干净，基本不会有什么影响：
local pending = { "A", "B" }
table.insert(pending, "C")
print(#pending) -- 输出：3
print(pending[3]) -- 输出：C
中间插入会让后面的元素“搬家”：
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
头删也会“搬家”，往前搬：
local tasks = { "move", "attack", "idle" }
local removedTask = table.remove(tasks, 1)
print(removedTask) -- 输出：move
print(tasks[1], tasks[2]) -- 输出：attack idle
demo 里数据不多的话，看起来没什么问题。
但是如果一个很多元素的表频繁这么干，很吃性能。尤其是每一帧频繁调用时。
但是中间插入和头删也不是完全禁用。
冷路径、短列表、编辑器工具里一般无所谓。
怎么避免搬家
队列：维护头尾双指针
FIFO 队列别用 table.remove(q, 1) 做出队。前面也提过，这样会搬家。
通用的写法是维护 head / tail。可以理解为 Leetcode 学的双指针（手动狗头）。
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 -- 断掉旧引用，方便 GC
head = head + 1
return v
end
Enqueue("cmd_move")
Enqueue("cmd_attack")
print(Dequeue()) -- 输出：cmd_move
print(Dequeue()) -- 输出：cmd_attack
print(Dequeue()) -- 输出：nil
q[head] = nil 一般不能省略。
尤其 value 里可能挂着对象、回调、资源句柄时，旧引用断掉才不影响 GC。
长期来看，这样实现的队列还有一个小问题是 head 会越走越远。
可以加个实现，如果队列变空，可以直接重置：
if head > tail then
q, head, tail = {}, 1, 0
end
也可以在适当时机考虑压缩。
大多数项目代码里，把热路径的 remove(1) 改掉是合理优化。
中间删除：不要求顺序，就用末尾元素补位
有些列表只是为了快速遍历，不要求顺序稳定。
比如子弹列表、临时命中列表、对象池里的空闲对象，这种就没必要每次删除都让后面的元素往前搬。
可以用最后一个元素补到被删除的位置：
local function RemoveFast(list, index)
local lastIndex = #list
if index < 1 or index > lastIndex then
return
end
list[index] = list[lastIndex] -- 用最后一个元素补当前位置
list[lastIndex] = nil -- 清掉最后一个槽位，断掉旧引用
end
local list = { "A", "B", "C", "D" }
RemoveFast(list, 2)
print(list[1], list[2], list[3], list[4])
-- 输出：A D C nil
这样删除很快，但是顺序会变。
所以它适合不关心顺序的运行时列表，不适合 UI 列表、排行榜、任务展示顺序这种业务。
按 id 删除：字典 + 数组 + indexMap
如果既想用数组遍历，又想按 id 快速删除，可以多维护一张 indexMap。
数组负责遍历，字典负责按 id 找位置。
用空间换时间。数组段方便遍历，哈希段方便 O(1) 查位置。
local entityList = {}
local entityIndexMap = {} -- key 是实体 id，value 是实体在 entityList 里的下标
local function AddEntity(entity)
table.insert(entityList, entity)
-- 新实体一定插在末尾，所以它的下标就是当前长度
entityIndexMap[entity.id] = #entityList
end
local function RemoveEntity(id)
-- 先通过 id 找到实体在数组里的位置，避免遍历 entityList
local index = entityIndexMap[id]
if index == nil then
return
end
local lastIndex = #entityList
local removedEntity = entityList[index]
local lastEntity = entityList[lastIndex]
-- 用最后一个实体补到被删除的位置，避免 table.remove 造成整体前移
entityList[index] = lastEntity
entityList[lastIndex] = nil -- 清掉最后一个槽位，断掉旧引用
-- 被删除的实体已经不在列表里了，下标表也要同步清掉
entityIndexMap[removedEntity.id] = nil
-- 如果删除的不是最后一个实体，补位实体的下标也要更新
if lastEntity ~= removedEntity then
entityIndexMap[lastEntity.id] = index
end
end
AddEntity({ id = 101, name = "RoleA" })
AddEntity({ id = 102, name = "RoleB" })
AddEntity({ id = 103, name = "RoleC" })
RemoveEntity(102)
print(entityList[1].id, entityList[2].id, entityList[3])
-- 输出：101 103 nil
print(entityIndexMap[101], entityIndexMap[102], entityIndexMap[103])
-- 输出：1 nil 2
这种写法项目里挺常见。有些项目组会封装常用 Lua 数据结构，底层都是多个表模拟对应数据结构。
注意点是只要移动了数组里的元素，就要同步维护 indexMap。
否则下次按 id 删除，拿到的下标就是旧的。
必须保顺序：先标记，帧末统一整理
如果顺序必须保留，那就不能用末尾补位。
UI 列表、任务顺序、帧同步 Tick 里，顺序乱了会直接变成业务 bug。
这种场景可以先标记删除，等这一轮逻辑结束后统一整理。
本质思想也是我们刷Leetcode题的时候，一个字段标记有效位置，一个字段遍历。
然后不停的把遍历到的覆盖进有效位置，然后有效位置+1。
这样遍历完后，数组前面都是有效的，有效位置后的有效的元素都丢到前面来了，有效位置后的就可以干掉了。
相当于压缩。
local entities = {
{ id = 101, dead = false },
{ id = 102, dead = true },
{ id = 103, dead = false },
{ id = 104, dead = true },
}
local function Compact(list)
-- writeIndex 表示下一个“存活对象”应该写入的位置
-- readIndex 负责从前往后扫描原数组
local writeIndex = 1
for readIndex = 1, #list do
local entity = list[readIndex]
-- 只保留没有死亡的对象
-- 在原数组上往前覆盖，不另建新表
if not entity.dead then
list[writeIndex] = entity
writeIndex = writeIndex + 1
end
end
-- writeIndex 后面的元素，已经不属于压缩后的有效数组
-- 这些位置可能还引用着旧对象，如果不清掉，会让旧对象继续被 table 持有
for i = writeIndex, #list do
list[i] = nil
end
end
Compact(entities)
for i = 1, #entities do
print(entities[i].id) -- 依次输出：101 / 103
end
这种做法是把很多次零散删除，变成一次统一整理。
这一帧先标记，安全时机再清理。比如帧末。
中间插入：能延后就延后
中间插入也一样：热路径里频繁插才麻烦，偶尔插一次无所谓。
能延后就先丢临时表，安全时机再合并。
local entityOrder = { 101, 102, 103 }
local pendingAddList = {}
local function AddEntityLater(id)
-- 不直接修改 entityOrder
-- 避免在遍历主顺序表时，边遍历边插入导致顺序和循环范围变复杂
table.insert(pendingAddList, id)
end
local function FlushPendingAdd()
-- 当前一轮逻辑结束后，再把待添加的实体统一追加到主顺序表末尾
for i = 1, #pendingAddList do
table.insert(entityOrder, pendingAddList[i])
end
-- 这一批待添加数据已经处理完，清空临时列表
-- 这里直接换一张新表，适合没有其他地方持有 pendingAddList 引用的情况
pendingAddList = {}
end
AddEntityLater(104)
AddEntityLater(105)
FlushPendingAdd()
print(entityOrder[1], entityOrder[2], entityOrder[3], entityOrder[4], entityOrder[5])
-- 输出：101 102 103 104 105
如果业务必须插到指定位置，就要看频率。
低频逻辑直接 table.insert 没问题；高频逻辑最好重新设计结构。
集合
只做判重、判存在，一般用 key 做占位。
local aliveSet = {}
aliveSet[1001] = true
aliveSet[1002] = true
print(aliveSet[1001] ~= nil) -- 输出：true
print(aliveSet[2001] ~= nil) -- 输出：false
aliveSet[1001] = nil
print(aliveSet[1001] ~= nil) -- 输出：false
值一般写 true 就可以，写1也无所谓。
如果还要记录访问时间、来源节点、权重，再把 value 换成小表。没有特殊需求一般没啥必要。
local visited = {}
visited[1001] = {
visitTime = 12345,
fromNode = "A"
}
print(visited[1001].visitTime) -- 输出：12345
不要为了判一个元素存在，每次都遍历数组，以下是bad case：
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
逻辑虽然没有问题跑，但元素一多，每帧查很多次，就会变成无意义的扫描，很吃性能的。
总结
连续下标访问，用数组。
按 id 查数据，用字典。
只判断存在，用集合。
既要查得快，又要顺序稳定，就字典配顺序表。
t[k] = v 是写槽。table.insert(t, pos, v) 会搬后面的元素。table.remove(t, pos) 会把后面的元素往前补。
热路径里别频繁让大数组搬家。
FIFO 用 head / tail；不要求顺序就末尾补位；要求顺序就先标记，帧末统一整理。
4.2 知识点代码
Lesson4_表与数据结构取舍.lua
print("**********表与数据结构取舍************")
print("**********知识点一 表先定用途************")
local arrayList = { 1001, 1002, 1003 }
local skillMap = {
[1001] = "FireBall",
[1002] = "IceBolt"
}
print(arrayList[1]) -- 输出：1001，数组按下标取
print(skillMap[1001]) -- 输出：FireBall，字典按 key 查
print("**********知识点二 数组语义************")
local skills = { 1001, 1002, 1003 }
print(skills[2]) -- 输出：1002
print(#skills) -- 输出：3
table.insert(skills, 1004)
print(skills[4]) -- 输出：1004，连续列表尾插
print(#skills) -- 输出：4
print("**********知识点三 字典语义************")
local configMap = {
[1001] = { name = "FireBall" },
[1005] = { name = "IceBolt" },
["passive_1"] = { name = "Shield" }
}
print(configMap[1001].name) -- 输出：FireBall
print(configMap[1002]) -- 输出：nil
local playerMap = {}
local playerCount = 0
local function AddPlayer(id, data)
if playerMap[id] == nil then
playerCount = playerCount + 1
end
playerMap[id] = data
end
AddPlayer(1001, { name = "PlayerA" })
AddPlayer(2008, { name = "PlayerB" })
print(playerCount) -- 输出：2，字典数量自己维护
print(playerMap[2008].name) -- 输出：PlayerB
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(entityId .. ":" .. entity.hp)
-- 依次输出：101:99 / 102:79 / 103:119
end
print("**********知识点五 写槽和插入************")
local direct = { 10, 20, 30 }
direct[2] = 99
print(direct[1], direct[2], direct[3]) -- 输出：10 99 30
print(#direct) -- 输出：3
local insertDemo = { 10, 20, 30, 40 }
table.insert(insertDemo, 2, 15)
print(insertDemo[1], insertDemo[2], insertDemo[3], insertDemo[4], insertDemo[5])
-- 输出：10 15 20 30 40
print(#insertDemo) -- 输出：5
print("**********知识点六 中间插入和头删************")
local pending = { "A", "B" }
table.insert(pending, "C")
print(#pending) -- 输出：3
print(pending[3]) -- 输出：C
local nums = { 10, 20, 30, 40 }
table.insert(nums, 2, 15)
print(nums[2], nums[3]) -- 输出：15 20
print(#nums) -- 输出：5
local tasks = { "move", "attack", "idle" }
local removedTask = table.remove(tasks, 1)
print(removedTask) -- 输出：move
print(tasks[1], tasks[2]) -- 输出：attack idle
print("**********知识点七 怎么避免搬家************")
print("----------队列：维护 head / tail----------")
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 -- 出队后断掉旧引用，避免旧对象继续被 table 持有
head = head + 1
return v
end
Enqueue("cmd_move")
Enqueue("cmd_attack")
print(Dequeue()) -- 输出：cmd_move
print(Dequeue()) -- 输出：cmd_attack
print(Dequeue()) -- 输出：nil
if head > tail then
q, head, tail = {}, 1, 0 -- 队列空了以后重置，避免 head 一直变大
end
print(head, tail) -- 输出：1 0
print("----------中间删除：末尾元素补位----------")
local function RemoveFast(list, index)
local lastIndex = #list
if index < 1 or index > lastIndex then
return
end
list[index] = list[lastIndex] -- 用最后一个元素补当前位置，避免后面元素整体前移
list[lastIndex] = nil -- 清掉最后一个槽位，断掉旧引用
end
local bulletList = { "BulletA", "BulletB", "BulletC", "BulletD" }
RemoveFast(bulletList, 2)
print(bulletList[1], bulletList[2], bulletList[3], bulletList[4])
-- 输出：BulletA BulletD BulletC nil，删除很快，但顺序会变
print("----------按 id 删除：数组 + indexMap----------")
local entityList = {}
local entityIndexMap = {} -- key 是实体 id，value 是实体在 entityList 里的下标
local function AddEntity(entity)
table.insert(entityList, entity)
-- 新实体插在末尾，所以它的下标就是当前长度
entityIndexMap[entity.id] = #entityList
end
local function RemoveEntity(id)
-- 先通过 id 找到数组下标，避免每次遍历 entityList
local index = entityIndexMap[id]
if index == nil then
return
end
local lastIndex = #entityList
local removedEntity = entityList[index]
local lastEntity = entityList[lastIndex]
-- 用最后一个实体补到被删除的位置，避免 table.remove 造成整体前移
entityList[index] = lastEntity
entityList[lastIndex] = nil -- 清掉最后一个槽位，断掉旧引用
-- 被删除的实体已经不在列表里了，下标表也要同步清掉
entityIndexMap[removedEntity.id] = nil
-- 如果删除的不是最后一个实体，补位实体的下标也要更新
if lastEntity ~= removedEntity then
entityIndexMap[lastEntity.id] = index
end
end
AddEntity({ id = 101, name = "RoleA" })
AddEntity({ id = 102, name = "RoleB" })
AddEntity({ id = 103, name = "RoleC" })
RemoveEntity(102)
print(entityList[1].id, entityList[2].id, entityList[3])
-- 输出：101 103 nil
print(entityIndexMap[101], entityIndexMap[102], entityIndexMap[103])
-- 输出：1 nil 2
print("----------必须保顺序：标记后统一整理----------")
local roleList = {
{ id = 101, dead = false },
{ id = 102, dead = true },
{ id = 103, dead = false },
{ id = 104, dead = true },
}
local function Compact(list)
local writeIndex = 1 -- 下一个有效对象应该写入的位置
for readIndex = 1, #list do
local role = list[readIndex]
-- 不新建数组，直接把有效对象往前覆盖
if not role.dead then
list[writeIndex] = role
writeIndex = writeIndex + 1
end
end
-- writeIndex 后面的槽位已经不是有效数据了，需要清掉旧引用
for i = writeIndex, #list do
list[i] = nil
end
end
Compact(roleList)
for i = 1, #roleList do
print(roleList[i].id)
-- 依次输出：101 / 103
end
print("----------中间插入：能延后就延后----------")
local entityOrder = { 101, 102, 103 }
local pendingAddList = {}
local function AddEntityLater(id)
-- 不在遍历主顺序表时直接插入，先丢进待添加列表
table.insert(pendingAddList, id)
end
local function FlushPendingAdd()
-- 当前一轮逻辑结束后，再统一合并到主顺序表
for i = 1, #pendingAddList do
table.insert(entityOrder, pendingAddList[i])
end
pendingAddList = {} -- 这一批已经处理完，直接换一张空表
end
AddEntityLater(104)
AddEntityLater(105)
FlushPendingAdd()
print(entityOrder[1], entityOrder[2], entityOrder[3], entityOrder[4], entityOrder[5])
-- 输出：101 102 103 104 105
print("**********知识点八 集合************")
local aliveSet = {}
aliveSet[1001] = true
aliveSet[1002] = true
print(aliveSet[1001] ~= nil) -- 输出：true，1001 存在
print(aliveSet[2001] ~= nil) -- 输出：false，2001 不存在
aliveSet[1001] = nil
print(aliveSet[1001] ~= nil) -- 输出：false，1001 已经移除
local visited = {}
visited[1001] = {
visitTime = 12345,
fromNode = "A"
}
print(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(1001)) -- 输出：true，但这是遍历数组查存在
print(IsAlive(2001)) -- 输出：false，数据多了以后这种写法不适合热路径
print("**********知识点九 总结************")
print("table 先看用途，再选写法")
print("连续下标访问，用数组")
print("按 id 查数据，用字典")
print("只判断存在，用集合")
print("既要查得快，又要顺序稳定，就字典配顺序表")
print("FIFO 队列用 head/tail，不要在热路径 remove(1)")
print("不要求顺序的删除，可以用末尾元素补位")
print("要求顺序的删除，可以先标记，帧末统一整理")
print("中间插入能延后就延后，能批量就批量")
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
