一、为什么考设计题？
Mermaid · 渲染中（下方为源码）
graph LR A[设计题] --> B[选基础结构] B --> C[多结构组合] C --> D[权衡复杂度]
面试中的"设计数据结构"题考查：
- 组合多种基础结构实现复杂功能
- 权衡时间复杂度（空间换时间）
- API 设计能力（接口清晰、边界处理）
核心思路：没有万能结构，只有组合。哈希表 + 链表、哈希表 + 堆、数组 + 哈希...
二、经典设计题
2.1 LRU 缓存（哈希表 + 双向链表）
已在 LRU 缓存 中详解。核心：
class LRUCache {
private int capacity;
private Map<Integer, Node> map;
private Node head, tail; // 虚拟头尾
public int get(int key) { /* 查找 + 移到头部 */ }
public void put(int key, int value) { /* 插入/更新 + 淘汰尾部 */ }
}- get/put 均 O(1)
2.2 LFU 缓存（双哈希 + 双向链表）
问题：淘汰使用频率最低的，频率相同淘汰最久未使用的。
class LFUCache {
private int capacity, minFreq;
private Map<Integer, Node> keyMap; // key → 节点
private Map<Integer, LinkedHashSet<Node>> freqMap; // freq → 节点集合
public int get(int key) {
if (!keyMap.containsKey(key)) return -1;
Node node = keyMap.get(key);
increaseFreq(node);
return node.val;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (keyMap.containsKey(key)) {
Node node = keyMap.get(key);
node.val = value;
increaseFreq(node);
return;
}
if (keyMap.size() >= capacity) {
// 淘汰 minFreq 中最旧的
LinkedHashSet<Node> set = freqMap.get(minFreq);
Node evict = set.iterator().next();
set.remove(evict);
keyMap.remove(evict.key);
}
Node newNode = new Node(key, value, 1);
keyMap.put(key, newNode);
freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(newNode);
minFreq = 1;
}
private void increaseFreq(Node node) {
int oldFreq = node.freq;
freqMap.get(oldFreq).remove(node);
if (freqMap.get(oldFreq).isEmpty() && oldFreq == minFreq) minFreq++;
node.freq++;
freqMap.computeIfAbsent(node.freq, k -> new LinkedHashSet<>()).add(node);
}
}