【语法】
一、机制原理
抛坑提问：缓存设了上限一百条，满了之后该挤掉谁？答案是最近最少使用的先走，这就是 LRU。要让它三个操作都够快，得两张结构合体：哈希表负责键到节点的直达映射，查找一步到位；双向链表负责使用顺序，头部放最新、尾部放最旧。命中就把节点摘下来插到头部，满了就摘掉尾部节点并从哈希表里销户——查、增、挤三个操作全是常数级，单靠数组或单靠链表都做不到。
二、错误写法
-- 错误：数组缓存线性查找加头部插入搬移
local cache = {}
function put(key, value)
for _, it in ipairs(cache) do
if it.key == key then
it.value = value
return
end
end
table.insert(cache, 1, {key = key, value = value})
end
三、正确写法
local LRU = {}
LRU.__index = LRU
function LRU.new(cap)
local o = setmetatable({cap = cap, map = {},
size = 0, head = {}, tail = {}}, LRU)
o.head.next = o.tail
o.tail.prev = o.head
return o
end
local function detach(node)
node.prev.next = node.next
node.next.prev = node.prev
node.prev, node.next = nil, nil
end
local function toFront(self, node)
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
end
function LRU:get(key)
local node = self.map[key]
if node == nil then return nil end
detach(node)
toFront(self, node)
return node.value
end
function LRU:put(key, value)
local node = self.map[key]
if node ~= nil then
node.value = value
detach(node)
toFront(self, node)
return
end
if self.size >= self.cap then
local old = self.tail.prev
detach(old)
self.map[old.key] = nil
self.size = self.size - 1
end
node = {key = key, value = value}
self.map[key] = node
toFront(self, node)
self.size = self.size + 1
end
四、引擎验证
容量设三依次放入四条，最先放入的自动出户；命中过的条目在挤占时存活到尾，使用顺序与预期一致。
五、FAQ
问：为什么要双向链表？
答：摘除任意节点不用从头找前驱，摘与插都是常数操作。
问：哨兵头尾的作用？
答：省去头空尾空的分支判断，边界统一。
全站技术干货持续更新：996 引擎 / Lua 实战帖，语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【语法算法】 元方法 __len 的触发就这一行： 对带 __len 的表做 t 操作时，Lua 调用 __len 而不是返…
【语法算法】 load 的编译本质就这一行： load 把字符串编译成函数——字符串里的代码被编译成可调用的函数——调用返回…
【语法算法】 error 的传播本质就这一行： error 抛出一个错误——第二个参数指定错误信息的层级——层级 2 表示把…
【语法算法】 pcall 的保护调用本质就这两行： pcall 把函数包在保护壳里执行——函数内部报错不会传播到外层——ok…
【语法算法】 元方法 __tostring 的触发就这一行： 对带 __tostring 的表做 tostring(t) 或…
【语法算法】 元方法 __call 的触发就这一行： 对带 __call 元方法的表做函数调用 t(...) 时，Lua 不…