17 | 如何通过链表做LRU/LFU缓存？-JavaScript进阶实战

当前位置:　首页>> 技术小册>> JavaScript进阶实战

章节 17 | 如何通过链表做LRU/LFU缓存？

在软件开发中，缓存机制是提高应用性能的重要手段之一。特别是在处理大量数据访问时，合理的缓存策略能显著减少数据访问延迟和系统负载。其中，最近最少使用（Least Recently Used, LRU）和最近最不常用（Least Frequently Used, LFU）是两种常见的缓存淘汰策略。本章节将深入探讨如何通过链表（特别是双向链表）结合哈希表来实现这两种缓存机制，并详细分析各自的优势与应用场景。

一、引言

LRU 缓存：LRU 缓存策略基于访问时间的局部性原理，即最近被访问的数据项在未来被再次访问的可能性更高。因此，当缓存空间不足时，会优先淘汰最长时间未被访问的数据项。
LFU 缓存：LFU 缓存策略则基于访问频率的局部性原理，即被访问次数越多的数据项在未来被再次访问的可能性越高。在缓存空间有限时，会优先淘汰访问次数最少的数据项。

二、LRU 缓存实现

2.1 LRU 缓存的基本原理

LRU 缓存的核心在于能够快速识别并移除最久未使用的数据项。这通常通过维护一个双向链表来实现，链表中的节点按照访问顺序排列，最近访问的节点被移动到链表头部，而最久未访问的节点则位于链表尾部。同时，为了快速访问任意节点，还需结合哈希表来存储键到节点指针的映射。

2.2 数据结构设计

双向链表节点：包含数据（或数据的引用）、前驱节点指针、后继节点指针。
哈希表：键为缓存项的键，值为对应链表节点的指针。

2.3 操作实现

访问数据：
1. 如果数据已存在于哈希表中，则更新该数据在链表中的位置，将其移动到链表头部。
2. 如果数据不存在，则首先检查缓存是否已满：
  - 若已满，移除链表尾部的节点（最久未使用），并从哈希表中删除该节点的键。
  - 否则，在链表头部添加新节点，并在哈希表中添加键到节点的映射。
删除数据：
1. 如果数据存在于哈希表中，找到对应的链表节点。
2. 从链表中移除该节点，并更新前驱和后继节点的指针。
3. 从哈希表中删除该键的映射。

2.4 示例代码（伪代码）

class ListNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = ListNode(0, 0)
        self.tail = ListNode(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    def get(self, key):
        # 省略访问逻辑...
    def put(self, key, value):
        # 省略添加或更新逻辑...
    def _move_to_head(self, node):
        # 省略将节点移动到链表头部的逻辑...
    def _remove_node(self, node):
        # 省略从链表中移除节点的逻辑...
    def _add_node(self, node):
        # 省略在链表头部添加新节点的逻辑...

三、LFU 缓存实现

3.1 LFU 缓存的基本原理

LFU 缓存相较于 LRU 缓存更为复杂，因为它需要记录每个数据项的访问频率。这通常通过为每个节点附加一个频率计数器来实现，并可能需要一个额外的数据结构（如最小堆或有序链表）来维护频率的排序，以便快速找到访问频率最低的数据项进行淘汰。

3.2 数据结构设计

双向链表节点：除了基本的数据和指针外，还需包含访问频率计数器。
哈希表：键为缓存项的键，值为对应链表节点的指针。
频率表：可以是基于频率的哈希表（每个频率映射到一个链表），或者是有序的数据结构（如最小堆），用于快速找到最低频率的节点。

3.3 操作实现

访问数据：
1. 如果数据已存在，增加其访问频率，并更新频率表和链表中的位置（可能需要重新排序或调整）。
2. 如果数据不存在，则检查缓存是否已满：
  - 若已满，从频率表中找到访问频率最低的节点并移除，然后添加新节点。
  - 否则，直接添加新节点，并初始化其频率。
删除数据：
1. 从哈希表中找到对应节点。
2. 从频率表和链表中移除该节点。

3.4 示例代码（伪代码）

由于 LFU 缓存的复杂性，这里仅提供概念性的伪代码框架。

class LFUCache:
    def __init__(self, capacity):
        # 省略初始化哈希表、链表和频率表的逻辑...
    def get(self, key):
        # 省略访问逻辑，包括增加频率、更新链表和频率表...
    def put(self, key, value):
        # 省略添加或更新逻辑，包括检查容量、增加频率、维护频率表等...
    # 辅助函数：如增加频率、从链表和频率表中移除节点等...

四、性能分析与适用场景

LRU 缓存：
- 优点：实现简单，能够快速识别并移除最久未使用的数据项。
- 缺点：在某些场景下，如数据项被周期性访问但访问频率不高时，可能会频繁淘汰有用数据。
- 适用场景：适用于需要频繁访问最近数据的场景，如网页缓存、数据库查询缓存等。
LFU 缓存：
- 优点：能够更准确地反映数据项的使用情况，避免频繁淘汰频繁访问但间隔较长的数据项。
- 缺点：实现复杂，需要维护额外的频率统计和排序结构，可能导致较高的维护成本和性能开销。
- 适用场景：适用于需要长期保留高频访问数据项的场景，如热门文章推荐、高频查询缓存等。