缓存淘汰 LRU 和 LFU

LRU（Least Recently Used）和 LFU（Least Frequently Used）缓存淘汰策略

一、LRU（Least Recently Used）缓存淘汰策略

LRU缓存淘汰策略的核心思想是：删除最近不使用的键值。为了实现这一策略，通常使用哈希表和双向链表相结合的数据结构。

数据结构定义：

• Node<K, V>：表示缓存中的一个节点，包含键（K）、值（V）、以及指向前一个节点和后一个节点的指针（prev和next）。
• NodeList：表示双向链表，包含头节点（head）和尾节点（tail）。
• KeyMap<K, Node<K, V>>：表示哈希表，用于通过键快速查找对应的节点。
• LRU：表示LRU缓存类，包含哈希表（map）、双向链表（list）、缓存容量大小（capacity）和当前键数（size）。

主要方法：

• set(K key, V value)：若键存在，则替换值并将对应的节点移动到链表的尾部（表示最近使用过）；若不存在，先检查当前键数是否等于容量，若是，则移除链表的头节点（表示最久未使用）并从哈希表中删除对应键值，再将新的节点添加到链表尾部。
• get(K key)：通过哈希表查找键对应的节点，若存在，则将该节点移动到链表的尾部（表示最近使用过），并返回节点的值。

二、LFU（Least Frequently Used）缓存淘汰策略

LFU缓存淘汰策略的核心思想是：先淘汰频次最少的键值。为了实现这一策略，通常使用哈希表和二重双向链表相结合的数据结构。

数据结构定义：

• KeyNode<K, V>：表示缓存中的一个节点，包含键（K）、值（V）、频次（count）、以及指向前一个节点和后一个节点的指针（prev和next）。
• CountList：表示根据频次双向链接的链表，包含指向更高频次链表和更低频次链表的指针（higher和lower），以及头节点（head）和尾节点（tail）。
• KeyMap<K, V>：这里的V实际上是KeyNode<K, V>类型，表示通过键快速查找对应的节点。
• KeyCountMap<K, V>：这里的V实际上是CountList类型，表示通过键节点快速查找对应的频次链表。
• LFU：表示LFU缓存类，包含头节点（head，表示最高频次的链表）、哈希表（KeyMap）、频次链表哈希表（KeyCountMap）、缓存容量大小（capacity）和当前键数（size）。

主要方法：

• set(K key, V value)：

  先从KeyMap中查找键对应的节点，若存在，则更新节点的值并将节点的频次加1。然后，将该节点从当前的频次链表中删除，并插入到更高频次的链表中（若不存在该频次链表，则新建）。

  若键不存在，则新建节点，频次设为1。若不存在频次为1的链表，则新建该链表并插入到头节点之前。否则，将新节点插入到频次为1的链表的头部。

  若此时缓存大小超过容量，则需要从最低频次的链表的尾部删除节点（表示频次最少且最久未使用的节点），并从哈希表和频次链表中删除对应键值。

• get(K key)：通过KeyMap查找键对应的节点，若存在，则将节点的频次加1，并更新节点在频次链表中的位置（与set方法中的更新逻辑相同）。

图片展示：

上图展示了LFU缓存中不同频次链表的结构，其中频次为1的链表包含多个节点，这些节点的使用频次都是1。

上图展示了频次为1的链表中节点的具体连接方式，这些节点通过双向链表连接在一起。

总结：

LRU和LFU都是常见的缓存淘汰策略，它们通过不同的方式来确定哪些键值应该被删除以腾出空间给新的键值。LRU基于最近使用的时间来淘汰键值，而LFU则基于使用的频次来淘汰键值。在实现这两种策略时，都需要使用哈希表和链表相结合的数据结构来高效地查找、更新和删除键值。