lru缓存核心是淘汰最久未被访问元素，需哈希表+双向链表实现o(1)查找、移动和删除；php中推荐spldoublylinkedlist配合数组映射，但offsetunset等操作为o(n)，高频场景应自定义链表节点。
LRU 缓存的核心逻辑是什么？
LRU（Least Recently Used）要求在容量满时，淘汰**最久未被访问**的元素。关键不是“最早加入”，而是“最近一次访问时间最靠前”。所以必须同时支持：快速查找（O(1)）、快速移动到最新位置（O(1)）、快速删除最旧节点（O(1)）。纯数组或普通哈希表无法同时满足——PHP 中最常用解法是 哈希表 + 双向链表组合。
PHP 中怎么高效实现双向链表结构？
不建议手写完整链表类。PHP 7.4+ 推荐用 SplDoublyLinkedList，它原生支持头尾增删、迭代、偏移定位，且内部是双向链表实现。但注意：SplDoublyLinkedList 的 offsetGet() 是 O(n)，不能用来随机查节点；所以仍需搭配关联数组（Array）做 key → node 映射。典型结构：
- 一个
array $map：存储 key ⇒ SplDoublyLinkedList 节点（实际存的是 value，但需能反查 key） - 一个
SplDoublyLinkedList $list：按访问顺序维护节点，头部为最新，尾部为最旧 - 每次
get()：查 map → 找到节点 → 从 list 中 detach → push front； - 每次
put()：若存在则更新 value 并 move to front；若不存在且满，则 pop back（最旧）并 unset map 对应 key，再 unshift 新节点
面试时容易被追问的关键细节
别只写骨架代码。面试官常盯住这几个点：
- 如何保证 get/put 都是 O(1)？ —— map 提供 O(1) 查找；SplDoublyLinkedList 的 unshift/pop/rewind/next 是均摊 O(1)，detach 需要先定位，但我们可以不 detach，改用“删除后重建”或更稳妥的“手动维护指针”（即自定义链表节点类）
- PHP 数组键名是否区分大小写？key 是字符串还是整型？ —— LRU 缓存 key 应支持任意可哈希类型，实际中通常限定为 String/int，构造时可加
is_scalar($key)校验 - 并发安全吗？ —— 单线程没问题；若提 Web 场景，可说明“PHP-FPM 每请求单进程，天然隔离”，无需加锁；swoole 或多线程环境才需考虑
- 内存泄漏风险？ —— 注意不要在节点里循环引用自身或闭包，避免 GC 无法回收；SplDoublyLinkedList 节点本身不含引用陷阱，相对安全
一个简洁可用的 PHP LRU 实现（带注释）
以下代码满足面试基本要求，无依赖，可直接运行：
立即学习“PHP免费学习笔记（深入）”；
class LRUCache { private array $map = []; private SplDoublyLinkedList $list; private int $capacity; public function __construct(int $capacity) { $this->capacity = $capacity; $this->list = new SplDoublyLinkedList(); $this->list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO); } public function get(mixed $key): mixed { if (!isset($this->map[$key])) return -1; // 把对应节点移到头部（最新） $node = $this->map[$key]; $this->list->offsetUnset($this->findIndex($key)); // O(n)，仅用于演示；真实高频场景建议自定义链表 $this->list->unshift($node); $this->map[$key] = $node; return $node['value']; } public function put(mixed $key, mixed $value): void { if (isset($this->map[$key])) { // 更新值并移到头部 $this->list->offsetUnset($this->findIndex($key)); $this->list->unshift(['key' => $key, 'value' => $value]); $this->map[$key] = ['key' => $key, 'value' => $value]; return; } // 新增 if ($this->list->count() >= $this->capacity && $this->capacity > 0) { // 删除尾部（最久未用） $tail = $this->list->pop(); unset($this->map[$tail['key']]); } $this->list->unshift(['key' => $key, 'value' => $value]); $this->map[$key] = ['key' => $key, 'value' => $value]; } private function findIndex(mixed $key): int { $i = 0; foreach ($this->list as $node) { if ($node['key'] === $key) return $i; $i++; } return -1; } }
注意：findIndex 是 O(n)，仅用于教学清晰性。高分答案会主动指出这点，并给出优化方向：用自定义双向链表节点（含 prev/next），配合 map 存储节点引用，实现真正 O(1) 的 move-to-front。