对比三家主流 AI 助手的代码生成能力

# LRU 缓存 Python 实现

设计说明

核心思路：用 哈希表 + 双向链表 组合实现 O(1) 的 get/put。

• 哈希表 (`dict`)：键 → 链表节点，实现 O(1) 查找。
• 双向链表：维护访问顺序，头部是最近使用，尾部是最久未使用。
• 使用带哨兵头尾节点的双向链表，避免边界判断（空链表、单节点等）。
• 每次访问/插入，把节点移到头部。
• 容量超限时，删除尾部前驱节点，并同步删除哈希表条目。

Python 标准库 `collections.OrderedDict` 也能直接实现，但下面手写双向链表版本更能体现 LRU 的核心机制。

完整代码

```python

class Node:

"""双向链表节点"""

__slots__ = ("key", "value", "prev", "next")

def __init__(self, key=0, value=0):

self.key = key

self.value = value

self.prev = None

self.next = None

class LRUCache:

"""

LRU 缓存：get/put 均为 O(1)

数据结构：

• self.cache: dict[key, Node] 用于 O(1) 定位节点
• 双向链表 head <-> ... <-> tail（哨兵节点）

head.next 是最近使用，tail.prev 是最久未使用

"""

def __init__(self, capacity: int):

if capacity <= 0:

raise ValueError("capacity must be positive")

self.capacity = capacity

self.cache = {}

# 哨兵头尾节点，简化边界处理

self.head = Node()

self.tail = Node()

self.head.next = self.tail

self.tail.prev = self.head

# ---------- 内部工具 ----------

def _add_to_head(self, node: Node) -> None:

"""把节点插入到 head 之后（即标记为最近使用）"""

node.prev = self.head

node.next = self.head.next

self.head.next.prev = node

self.head.next = node

def _remove(self, node: Node) -> None:

"""从链表中摘除节点"""

node.prev.next = node.next

node.next.prev = node.prev

def _move_to_head(self, node: Node) -> None:

"""节点移到头部（表示刚被访问过）"""

self._remove(node)

self._add_to_head(node)

def _pop_tail(self) -> Node:

"""弹出最久未使用的节点（tail 前驱）"""

node = self.tail.prev

self._remove(node)

return node

# ---------- 对外接口 ----------

def get(self, key: int):

"""读取：命中则移到头部并返回值，未命中返回 None"""

if key not in self.cache:

return None

node = self.cache[key]

self._move_to_head(node)

return node.value

def put(self, key: int, value: int) -> None:

"""写入：已存在则更新并移到头部；否则插入并可能淘汰尾部"""

if key in self.cache:

node = self.cache[key]

node.value = value

self._move_to_head(node)

return

if len(self.cache) >= self.capacity:

evicted = self._pop_tail()

del self.cache[evicted.key]

new_node = Node(key, value)

self.cache[key] = new_node

self._add_to_head(new_node)

# ---------- 调试用 ----------

def __repr__(self):

items, cur = [], self.head.next

while cur is not self.tail:

items.append(f"{cur.key}:{cur.value}")

cur = cur.next

return "LRUCache([" + ", ".join(items) + "])"

# ---------------- 测试 ----------------

if __name__ == "__main__":

cache = LRUCache(2) # 容量 2

cache.put(1, 1)

cache.put(2, 2)

print(cache.get(1)) # 1 -> 命中，1 变为最近使用

cache.put(3, 3) # 淘汰 key=2

print(cache.get(2)) # None

cache.put(4, 4) # 淘汰 key=1

print(cache.get(1)) # None

print(cache.get(3)) # 3

print(cache.get(4)) # 4

print(cache) # LRUCache([4:4, 3:3])

```

复杂度分析

| 操作 | 时间复杂度 | 说明 |

|------|-----------|------|

| `get` | O(1) | dict 查节点 + 双向链表移动（常数次指针操作） |

| `put` | O(1) | dict 插入/删除 + 链表插入/删除 |

| 空间 | O(capacity) | 哈希表 + 链表各存 capacity 个节点 |

关键点

1. 哨兵节点：`head` 和 `tail` 两个哑节点让插入/删除不需要判断空链表或头尾节点。

2. 存 key 于节点中：淘汰尾节点时需要用它的 key 从 `dict` 中删除，否则会有内存泄漏。

3. 命中时的顺序更新：`get` 命中后必须把节点移到头部，否则就不叫 LRU 了。

4. 替代方案：用 `collections.OrderedDict` + `move_to_end` + `popitem(last=False)` 可以更简洁地实现同样效果。

以下是符合要求的 LRU 缓存（Least Recently Used） 的 Python 实现，使用 `collections.OrderedDict`（底层基于哈希表 + 双向链表），保证 `get()` 和 `put()` 均为 O(1) 平均时间复杂度，支持容量限制与自动淘汰最久未使用的项。

✅ 代码可直接运行（含完整测试用例）

✅ 时间复杂度：`get` / `put` 均为 O(1)

✅ 空间复杂度：O(capacity)

✅ 自动淘汰：当 `put` 导致超容时，移除最久未使用（即 OrderedDict 最左侧） 的键值对

---

✅ 完整可运行代码

```python

from collections import OrderedDict

class LRUCache:

def __init__(self, capacity: int):

"""

初始化 LRU 缓存，设定最大容量。

使用 OrderedDict 维护访问顺序：新插入或访问的元素置于末尾（最近使用），

最老的元素始终在开头（最久未使用）。

"""

self.cache = OrderedDict()

self.capacity = capacity

def get(self, key: int) -> int:

"""

获取 key 对应的 value；若存在，则将其移到末尾（标记为最近使用），并返回 value；

若不存在，返回 -1。

时间复杂度：O(1) —— OrderedDict 的 move_to_end 和 get 均为平均 O(1)

"""

if key not in self.cache:

return -1

# 将访问的 key 移至末尾（最近使用）

self.cache.move_to_end(key)

return self.cache[key]

def put(self, key: int, value: int) -> None:

"""

插入或更新 key-value 对。

• 若 key 已存在：更新 value 并移至末尾；
• 若 key 不存在：

* 若未超容：直接插入（自动加至末尾）；

* 若已达 capacity：先弹出最久未使用的项（popitem(last=False) → 弹开头），再插入新项。

时间复杂度：O(1)

"""

if key in self.cache:

# 更新值并标记为最近使用

self.cache[key] = value

self.cache.move_to_end(key)

else:

# 新增 key；检查容量

if len(self.cache) >= self.capacity:

# 淘汰最久未使用的项（OrderedDict 最左侧）

self.cache.popitem(last=False)

self.cache[key] = value

# —————— 测试用例（可直接运行）——————

if __name__ == "__main__":

# 示例：capacity = 2

lru = LRUCache(2)

lru.put(1, 1) # cache: {1=1}

lru.put(2, 2) # cache: {1=1, 2=2}

print(lru.get(1)) # 返回 1；cache 变为 {2=2, 1=1}（1 被访问，移到末尾）

lru.put(3, 3) # 淘汰 2 → cache: {1=1, 3=3}

print(lru.get(2)) # 返回 -1（2 已淘汰）

lru.put(4, 4) # 淘汰 1 → cache: {3=3, 4=4}

print(lru.get(1)) # 返回 -1

print(lru.get(3)) # 返回 3

print(lru.get(4)) # 返回 4

# 输出应为：1, -1, -1, 3, 4

```

---

🔍 设计说明（关键点）

| 组件 | 作用 | 时间复杂度 |

|------|------|------------|

| `OrderedDict` | ✅ 核心数据结构：<br>• 底层：哈希表（O(1) 查找） + 双向链表（O(1) 移动/删除任意节点）<br>• `move_to_end(key)`：将指定 key 对应节点移到链表末尾（标记为最近使用）<br>• `popitem(last=False)`：O(1) 弹出链表头（最久未使用） | 均为 O(1) |

| `get(key)` | 先查是否存在 → 存在则 `move_to_end` + 返回值；否则返回 -1 | O(1) |

| `put(key, value)` | 分情况：<br>• key 存在 → 更新 + `move_to_end`<br>• key 不存在 → 检查容量，必要时 `popitem(last=False)` 淘汰，再插入新项 | O(1) |

| 容量控制 | 仅在 `put` 且新增 key 时检查 `len(cache) >= capacity`，严格保证缓存大小 ≤ capacity | O(1) |

> 💡 为什么不用手写双向链表？

> 虽然手写链表+哈希表也是经典解法（面试常考），但 `OrderedDict` 是 Python 标准库中经过高度优化的实现，语义清晰、代码简洁、性能可靠，且满足题目「O(1)」和「可直接运行」要求。实际工程推荐此方案。

---

如需手写双向链表版本（用于深入理解或面试准备），我也可以立即提供 👍

是否需要？

下面给出一个 哈希表 + 双向链表 手写的 LRU 缓存实现，并附带可直接运行的测试代码。

设计说明

| 组件 | 作用 | 为什么能保证 O(1) |

|------|------|-------------------|

| 哈希表 (`dict`) | 存储 `key → 链表节点` 的映射 | 查找、插入、删除均为平均 O(1) |

| 双向链表 | 按“使用时间”维护节点顺序，头部为最近使用，尾部为最久未使用 | 给定节点指针后，删除/插入仅需修改前后指针，O(1) |

| 伪头/伪尾节点 | 哨兵节点（Sentinel），避免对空链表或边界节点做特殊判断 | 简化代码，减少分支 |

核心操作：

1. `get(key)`：通过哈希表找到节点，将其移到链表头部，返回 `value`。

2. `put(key, value)`：

• 若 `key` 已存在：更新 `value` 并移到头部。
• 若 `key` 不存在：新建节点插入头部；若容量超限，删除尾部节点（最久未使用），同时从哈希表中移除对应的 `key`。

---

完整代码（可直接运行）

```python

class DLinkedNode:

"""双向链表节点"""

def __init__(self, key: int = 0, value: int = 0):

self.key = key

self.value = value

self.prev = None

self.next = None

class LRUCache:

"""

LRU 缓存：哈希表 + 双向链表实现

• get / put 时间复杂度均为 O(1)
• 容量满时自动淘汰最久未使用的元素

"""

def __init__(self, capacity: int):

self.cache = {} # key -> DLinkedNode

self.capacity = capacity

self.size = 0

# 伪头部和伪尾部（哨兵节点），避免处理空指针

self.head = DLinkedNode()

self.tail = DLinkedNode()

self.head.next = self.tail

self.tail.prev = self.head

# ---------- 内部辅助方法：纯链表操作 ----------

def _add_to_head(self, node: DLinkedNode):

"""将节点插入到头部（表示最近使用）"""

node.prev = self.head

node.next = self.head.next

self.head.next.prev = node

self.head.next = node

def _remove_node(self, node: DLinkedNode):

"""将节点从链表中移除"""

node.prev.next = node.next

node.next.prev = node.prev

def _move_to_head(self, node: DLinkedNode):

"""将已有节点移到头部"""

self._remove_node(node)

self._add_to_head(node)

def _pop_tail(self) -> DLinkedNode:

"""移除链表尾部节点（最久未使用），并返回该节点"""

node = self.tail.prev

self._remove_node(node)

return node

# ---------- 对外接口 ----------

def get(self, key: int) -> int:

"""若 key 存在，返回值并将其设为最近使用；否则返回 -1"""

if key not in self.cache:

return -1

node = self.cache[key]

self._move_to_head(node)

return node.value

def put(self, key: int, value: int) -> None:

"""插入或更新 key；若容量超限，淘汰最久未使用的 key"""

if self.capacity <= 0:

return

if key in self.cache:

# 更新已有节点，并移到头部

node = self.cache[key]

node.value = value

self._move_to_head(node)

else:

# 新建节点，插入头部

node = DLinkedNode(key, value)

self.cache[key] = node

self._add_to_head(node)

self.size += 1

# 超出容量，淘汰尾部

if self.size > self.capacity:

removed = self._pop_tail()

del self.cache[removed.key]

self.size -= 1

# ==================== 测试 ====================

if __name__ == "__main__":

print("=== LRU Cache 测试 ===")

cache = LRUCache(2) # 容量为 2

cache.put(1, 1)

cache.put(2, 2)

print(f"get(1) = {cache.get(1)}") # 返回 1，key 1 变为最近使用

cache.put(3, 3) # 容量满，淘汰最久未使用的 key 2

print(f"get(2) = {cache.get(2)}") # 返回 -1（已被淘汰）

cache.put(4, 4) # 淘汰 key 1

print(f"get(1) = {cache.get(1)}") # 返回 -1（已被淘汰）

print(f"get(3) = {cache.get(3)}") # 返回 3

print(f"get(4) = {cache.get(4)}") # 返回 4

# 测试更新操作：更新 key 3，它应变为最近使用

cache.put(3, 30)

cache.put(5, 5) # 应淘汰 key 4，而不是 key 3

print(f"get(3) = {cache.get(3)}") # 返回 30

print(f"get(4) = {cache.get(4)}") # 返回 -1（已被淘汰）

print(f"get(5) = {cache.get(5)}") # 返回 5

```

复杂度总结

• 时间复杂度：`get` 和 `put` 均为 O(1)。哈希表定位节点 O(1)，双向链表移动节点也是 O(1)。
• 空间复杂度：O(capacity)，哈希表与链表最多存储 `capacity + 2`（含哨兵）个节点。