面试题答案
一键面试1. 数据结构选择
- 双向链表（Doubly Linked List）：用于存储缓存数据。双向链表可以方便地在O(1)时间内删除节点和在头部插入新节点。每个节点包含数据、前驱指针和后继指针。
- 哈希表（Hash Table）：用于快速定位双向链表中的节点。哈希表的键为缓存数据的键，值为对应双向链表节点的指针。这样可以在O(1)时间内根据键找到对应的节点，从而快速进行节点的移动和删除操作。
2. 操作逻辑
- 获取数据（get操作）：
- 首先在哈希表中查找键是否存在。如果不存在，返回 -1（表示未命中缓存）。
- 如果键存在，通过哈希表获取对应的双向链表节点。
- 将该节点从当前位置移动到双向链表头部（因为该数据最近被使用了）。
- 返回该节点对应的数据值。
- 插入数据（put操作）：
- 首先在哈希表中查找键是否存在。
- 如果存在，更新该节点对应的数据值，并将该节点移动到双向链表头部。
- 如果不存在，创建一个新的双向链表节点，并将其插入到双向链表头部。同时将键值对插入到哈希表中。
- 如果此时缓存已满（即双向链表节点数达到缓存容量上限），删除双向链表尾部的节点（最近最少使用的节点），并从哈希表中删除对应的键值对。
- 首先在哈希表中查找键是否存在。
3. 代码示例（Python）
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cache = {}
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.moveToHead(node)
return node.value
def put(self, key: int, value: int) -> None:
if key not in self.cache:
node = DLinkedNode(key, value)
self.cache[key] = node
self.addToHead(node)
self.size += 1
if self.size > self.capacity:
removed = self.removeTail()
self.cache.pop(removed.key)
self.size -= 1
else:
node = self.cache[key]
node.value = value
self.moveToHead(node)
def addToHead(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def moveToHead(self, node):
self.removeNode(node)
self.addToHead(node)
def removeTail(self):
node = self.tail.prev
self.removeNode(node)
return node
// 使用示例