实现固定容量LRU图片缓存为何不能只用数组？

## 作用 固定容量的 LRU 图片缓存需要同时完成两件事： - **限制缓存数量**：缓存满时淘汰最近最少使用的图片。 - **维护访问顺序**：某张图片被访问后，要把它标记为最近使用。 只用数组也可以实现，但效率不理想。 ## 原理与复杂度差别 ### 只用数组 可以按照访问顺序在数组中存放图片，例如队首放最近使用的图片，队尾放最久未使用的图片。 问题在于： - **查找图片是否已缓存**：通常要遍历数组，时间复杂度为 **O(n)**。 - **访问已有图片后移动到队首**：需要先找到元素，再移动数组中的其他元素，整体为 **O(n)**。 - **插入新图片**： - 缓存未满时插到队首，需要移动元素，为 **O(n)**； - 缓存已满时还要删除队尾元素并移动数据，通常也是 **O(n)**。 - 数组需要连续内存，插入、删除时会产生数据搬移。 因此，数组实现虽然简单，但随着缓存容量增大，查找和维护访问顺序的成本较高。 ### 只用链表 链表的零散内存块通过指针连接： - 已经知道目标结点位置时，插入和删除只需修改相邻结点的指针，时间复杂度为 **O(1)**。 - 但查找某个图片结点需要从头遍历链表，时间复杂度为 **O(n)**。 所以只用单链表仍不能高效判断图片是否在缓存中，也不能快速定位对应结点。 ### 哈希表 + 双向链表 更典型的 LRU 实现是将两种结构结合： - **哈希表**：根据图片 key 快速找到对应链表结点，期望时间复杂度 **O(1)**。 - **双向链表**：按访问时间顺序组织结点；找到结点后，可利用前驱和后继指针在 **O(1)** 时间内删除、移动或插入。 因此，缓存的查找、访问更新、插入新图片和淘汰最久未使用图片，通常都可以达到 **O(1)** 的平均时间复杂度。

## 作用 固定容量的 LRU 图片缓存需要同时完成三件事： - 根据图片 key 快速找到缓存图片。 - 每次访问或更新图片后，把它标记为“最近使用”。 - 缓存满时，快速淘汰“最近最少使用”的图片。 因此，LRU 不只是存储图片，还必须维护图片的访问先后顺序。 ## 原理 ### 为什么不能只用数组 如果只用数组保存缓存项： - 查找某张图片通常需要遍历数组，平均时间复杂度为 `O(n)`。 - 访问一张图片后，要把它移动到表示“最近使用”的位置；在数组中间删除或插入元素需要移动大量元素，时间复杂度为 `O(n)`。 - 缓存满时，如果最老元素不在数组尾部，删除它也可能需要移动元素，复杂度为 `O(n)`。 所以，只用数组虽然能实现固定容量和顺序维护，但在容量变大、图片访问频繁时性能较差。 ### Object 配合额外顺序结构的问题 使用普通 `Object` 可以按键取值，但它本身不适合直接完成 LRU 的“移动到最新位置”操作： - `Object` 的键会被转换为字符串，键类型不如 `Map` 灵活。 - 属性顺序规则不完全等价于简单的“最近使用顺序”。 - 通常还要额外维护数组或链表来记录顺序。 - 如果通过遍历对象键找到最老元素，淘汰操作可能是 `O(n)`，代码也更复杂。 ### 使用 Map 的方案 `Map` 会保留键值对的插入顺序，因此可以约定： - `Map` 第一个元素：最近最少使用。 - `Map` 最后一个元素：最近使用。 每次 `get` 或 `put` 已存在的 key 时： 1. 先删除旧键值对。 2. 再重新 `set` 到 `Map` 中。 3. 该元素就被移动到末尾，表示最近使用。 缓存满时： - 通过 `this.cache.keys().next().value` 取得第一个 key。 - 删除它，即淘汰最近最少使用的图片。 在 JavaScript 中，`Map` 的 `has`、`get`、`set`、`delete` 平均可视为接近 `O(1)`，因此 `get` 和 `put` 都可以达到平均 `O(1)` 的时间复杂度；空间复杂度为 `O(capacity)`。 ### 复杂度对比 | 实现方式 | 查找 | 更新访问顺序 | 淘汰最旧元素 | |---|---:|---:|---:| | 只用数组 | `O(n)` | `O(n)` | 通常 `O(n)` | | Object + 数组/链表 | 查找可接近 `O(1)`，但顺序维护可能为 `O(n)` | 可能 `O(n)` | 可能 `O(n)` | | Map | 平均接近 `O(1)` | 平均接近 `O(1)` | 平均接近 `O(1)` | 因此，固定容量的图片 LRU 缓存不能“只”靠数组高效实现；更合适的方式是使用能快速按键查找并维护使用顺序的结构。在 JavaScript 中可直接利用 `Map` 的插入顺序实现平均 `O(1)` 的读取、更新和淘汰。