LRU

力扣链接：LRU缓存

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

分析

LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

要让 LRU 的 put 和 get 方法的时间复杂度为 O(1)，可以总结出 LRU 这个数据结构必要的条件：

1、显然 LRU 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。

2、要在 LRU 中快速找某个 key 是否已存在并得到对应的 val；

3、每次访问 LRU 中的某个 key，需要将这个元素变为最近使用的，也就是说 LRU 要支持在任意位置快速插入和删除元素。

那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样： 借助这个结构，逐一分析上面的 3 个条件：

1、如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。

2、对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。

3、链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。

put方法流程图：

代码实现

LFU

力扣链接：LFU缓存

LRU 算法的淘汰策略是 Least Recently Used，也就是每次淘汰那些最久没被使用的数据；而 LFU 算法的淘汰策略是 Least Frequently Used，也就是每次淘汰那些使用次数最少的数据。

分析

根据 LFU 算法的逻辑，先列举出算法执行过程中的几个显而易见的事实：

  1. 调用 get(key) 方法时，要返回该 key 对应的 val。

  2. 只要用 get 或者 put 方法访问一次某个 key，该 key 的 freq 就要加一。

  3. 如果在容量满了的时候进行插入，则需要将 freq 最小的 key 删除，如果最小的 freq 对应多个 key，则删除其中最旧的那一个。

希望能够在 O(1) 的时间内解决这些需求，可以使用基本数据结构来逐个解决：

  1. 使用一个HashMap存储key到val的映射，就可以快速计算get(key)。

  2. 使用一个HashMap存储key到freq的映射，就可以快速操作key对应的freq。

  3. 这个需求是 LFU 算法的核心

  4. 首先，肯定是需要freq到key的映射，用来找到freq最小的key。

  5. 将freq最小的key删除，那你就得快速得到当前所有key最小的freq是多少。想要时间复杂度 O(1) 的话，肯定不能遍历一遍去找，那就用一个变量minFreq来记录当前最小的freq。

  6. 可能有多个key拥有相同的freq，所以 freq对key是一对多的关系，即一个freq对应一个key的列表。

  7. 希望freq对应的key的列表是存在时序的，便于快速查找并删除最旧的key。

  8. 希望能够快速删除key列表中的任何一个key，因为如果频次为freq的某个key被访问，那么它的频次就会变成freq+1，就应该从freq对应的key列表中删除，加到freq+1对应的key的列表中。

LinkedHashSet，能满足我们 3.3，3.4，3.5 这几个要求。你会发现普通的链表LinkedList能够满足 3.3，3.4 这两个要求，但是由于普通链表不能快速访问链表中的某一个节点，所以无法满足 3.5 的要求。

LinkedHashSet顾名思义，是链表和哈希集合的结合体。链表不能快速访问链表节点，但是插入元素具有时序；哈希集合中的元素无序，但是可以对元素进行快速的访问和删除。那么，它俩结合起来就兼具了哈希集合和链表的特性，既可以在 O(1) 时间内访问或删除其中的元素，又可以保持插入的时序，高效实现 3.5 这个需求。

put方法流程：

代码实现

在removeMinFreqKey()方法中，如果keyList中只有一个元素，那么删除之后minFreq对应的key列表就为空了，也就是minFreq变量需要被更新。如何计算当前的minFreq是多少呢？

实际上没办法快速计算minFreq，只能线性遍历FK表或者KF表来计算，这样肯定不能保证 O(1) 的时间复杂度。但是，其实这里没必要更新minFreq变量，因为removeMinFreqKey这个函数是在put方法中插入新key时可能调用。而回头看put的代码，插入新key时一定会把minFreq更新成 1，所以说即便这里minFreq变了，也不需要管它。