【数据结构进阶版】从数组到哈希表：用五大基础数据结构拼出一台 LRU 缓存引擎

目录

一、综述

二、主要内容

1. 五大基础数据结构快速复习

1.1 数组（Array）

1.2 链表（LinkedList）

1.3 队列（Queue）

1.4 栈（Stack）

1.5 哈希表（HashMap）

2. 什么是 LRU 缓存？

3. 如何设计一个 LRU 缓存？

3.1 数据结构选择

4. Java 实现 LRU 缓存

4.1 定义双向链表节点

4.2 实现 LRUCache 类

4.3 辅助方法：添加节点到头部、移除节点、移动节点到头部、移除尾部节点

4.4 get 方法

4.5 put 方法

5. 测试代码

6. 总结与思考

7.拓展思考：为什么不用堆？

7.1 堆方案的缺点

7.2 双向链表 + 哈希表的优势

两种方案对比总结

一、综述

在软件开发中，数据结构是程序的骨架。数组、链表、队列、栈、哈希表是五种最基础的数据结构，理解它们的特点和适用场景，是写出高效代码的前提。而实际工程中，我们往往需要组合多种数据结构来解决问题。本文将通过实现一个经典算法——LRU 缓存（使用哈希表+链表），带你彻底掌握这些数据结构，并展示它们如何协同工作。

二、主要内容

1. 五大基础数据结构快速复习

1.1 数组（Array）

• 存储方式：连续的内存空间，存储相同类型的元素。

• 特点：通过下标访问，时间复杂度 O(1)；插入和删除需要移动元素，平均 O(n)。

• 适用场景：频繁读取、很少插入删除的场景，如查找表。

1.2 链表（LinkedList）

• 存储方式：节点通过指针链接，内存不连续。

• 特点：插入和删除只需修改指针，时间复杂度 O(1)（已知位置）；查找需要遍历，O(n)。

• 变种：单向链表、双向链表（每个节点有 prev 和 next 指针）、循环链表。

• 适用场景：频繁插入删除、无需随机访问的场景，如队列、栈的底层实现。

1.3 队列（Queue）

• 逻辑结构：先进先出（FIFO），一端入队（offer），一端出队（poll）。

• 实现方式：可用数组（循环队列）或链表。

• 适用场景：任务排队、广度优先搜索等。

1.4 栈（Stack）

• 逻辑结构：后进先出（LIFO），压栈（push），弹栈（pop）。

• 实现方式：数组或链表。

• 适用场景：函数调用、括号匹配、深度优先搜索等。

1.5 哈希表（HashMap）

• 核心思想：通过哈希函数将键映射到数组下标，实现快速存取。

• 冲突解决：拉链法（数组+链表）、开放寻址法等。

• 时间复杂度：理想情况 O(1)，最坏 O(n)。

• 适用场景：需要快速查找、插入、删除的键值对存储。

这些数据结构各有长短，聪明的做法是组合使用，取长补短。

2. 什么是 LRU 缓存？

LRU 是 Least Recently Used 的缩写，即最近最少使用。它是一种缓存淘汰策略：当缓存空间满时，优先淘汰最长时间没有被访问的数据。

现实类比：手机后台 App 管理。当你打开多个应用，系统内存不足时，会关闭你最长时间没用的那个应用。

应用场景：Redis 缓存、操作系统页面置换、浏览器历史记录等。

3. 如何设计一个 LRU 缓存？

我们需要支持两个操作：

• get(key)：如果 key 存在，返回对应的 value，并将该 key 标记为最近使用；否则返回 -1。

• put(key, value)：插入或更新键值对。如果 key 已存在，更新 value 并标记为最近使用；如果不存在，检查容量是否已满，若满则淘汰最久未使用的 key，再插入新键值对。

要求：get 和 put 的时间复杂度都是 O(1)。

3.1 数据结构选择

• 哈希表：实现 O(1) 的查找。

• 双向链表：维护键值对的访问顺序。最近使用的放在头部，最久未使用的在尾部。删除和移动到头部操作都是 O(1)（因为节点有 prev 和 next 指针）。

组合方式：哈希表的 value 存储链表节点的引用。这样我们能在 O(1) 时间内定位到节点，然后进行删除或移动。

4. Java 实现 LRU 缓存

4.1 定义双向链表节点

每个节点存储 key、value 以及前后指针。存储 key 是为了在淘汰时能从哈希表中删除对应的条目。

class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}

4.2 实现 LRUCache 类

主要成员：

• capacity：缓存容量。

• size：当前节点数量。

• cache：哈希表，键为 Integer，值为节点引用。

• head, tail：双向链表的虚拟头尾节点，方便操作。

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 初始化双向链表，使用虚拟头尾节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
}

4.3 辅助方法：添加节点到头部、移除节点、移动节点到头部、移除尾部节点

这些方法操作链表，由于是双向链表，复杂度均为 O(1)。

// 将节点添加到头节点之后（头部）
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}

// 移除一个节点
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}

// 将节点移动到头部：先移除，再添加
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}

// 移除尾部节点（最久未使用）并返回该节点
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}

4.4 get 方法

public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 移动到头部
moveToHead(node);
return node.value;
}

4.5 put 方法

public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 不存在，创建新节点
DLinkedNode newNode = new DLinkedNode(key, value);
cache.put(key, newNode);
addToHead(newNode);
size++;
if (size > capacity) {
// 超出容量，移除尾部节点
DLinkedNode tailNode = removeTail();
cache.remove(tailNode.key); // 从哈希表删除
size–;
}
} else {
// 存在，更新值并移到头部
node.value = value;
moveToHead(node);
}
}

5. 测试代码

我们来验证一下：

public class Main {
public static void main(String[] args) {
LRUCache lru = new LRUCache(2);
lru.put(1, 1); // 缓存: {1=1}
lru.put(2, 2); // 缓存: {1=1, 2=2}
System.out.println(lru.get(1)); // 返回 1，并将 1 移到头部，缓存: {2=2, 1=1}
lru.put(3, 3); // 容量满，淘汰尾部 2，缓存: {1=1, 3=3}
System.out.println(lru.get(2)); // 返回 -1 (未找到)
lru.put(4, 4); // 淘汰尾部 1，缓存: {3=3, 4=4}
System.out.println(lru.get(1)); // 返回 -1
System.out.println(lru.get(3)); // 返回 3
System.out.println(lru.get(4)); // 返回 4
}
}

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

6. 总结与思考

通过实现 LRU 缓存，我们深刻体会了组合数据结构的威力：

• 哈希表提供了 O(1) 的键值查找。

• 双向链表保证了节点顺序的快速维护（移动、删除）。

• 两者结合，完美满足了 LRU 缓存的所有要求。

这种设计思想在许多底层系统中都有体现，比如 Redis 的 LRU 实现、MySQL 的 Buffer Pool 等。掌握它，不仅能应对面试，更能提升你对系统设计的理解。

7.拓展思考：为什么不用堆？

7.1 堆方案的缺点

如果尝试用最小堆来实现 LRU，通常会遇到以下问题：

7.2 双向链表 + 哈希表的优势

LRU 的标准实现采用双向链表 + 哈希表的组合，完美解决了上述问题：

• 哈希表：提供 O(1) 的键到链表节点的定位。

• 双向链表：维护访问顺序（头部为最近使用，尾部为最久未使用）。

• 操作流程：

  • get(key)：通过哈希表找到节点，O(1)；然后将节点移动到链表头部（双向链表已知节点，移动也是 O(1)）。

  • put(key, value)：如果 key 存在，更新值并移动到头部；如果不存在，创建新节点插入头部，并检查容量。若超容，删除尾部节点（O(1)），同时从哈希表中移除对应的键。

• 优点：所有操作均为严格的 O(1)，实现简单，是工业界最常用的 LRU 实现方式（如 Java 的 LinkedHashMap）。

两种方案对比总结

因此，LRU 缓存的最佳选择是双向链表 + 哈希表，堆并非合适的数据结构。