Redis 是一个内存数据库，当 Redis 应用的内存超过物理内存的限度后，内存数据会和磁盘产生频繁的替换，替换会导致 Redis 性能急剧下降。所以在生产环境中咱们通过配置参数 maxmemoey 来限度应用的内存大小。
当理论应用的内存超过 maxmemoey 后，Redis 提供了如下几种可选策略。
noeviction：写申请返回谬误
volatile-lru：应用 lru 算法删除设置了过期工夫的键值对
volatile-lfu：应用 lfu 算法删除设置了过期工夫的键值对
volatile-random：在设置了过期工夫的键值对中随机进行删除
volatile-ttl：依据过期工夫的先后进行删除，越早过期的越先被删除
allkeys-lru：在所有键值对中，应用 lru 算法进行删除
allkeys-lfu：在所有键值对中，应用 lfu 算法进行删除
allkeys-random：所有键值对中随机删除
咱们来具体理解一下 lru 和 lfu 算法，这是 2 个常见的缓存淘汰算法。因为计算机缓存的容量是无限的，所以咱们要删除那些没用的数据，而这两种算法的区别就是断定没用的纬度不一样。
LRU算法
lru（Least recently used，最近起码应用）算法，即最近拜访的数据，后续很大概率还会被拜访到，即是有用的。而长时间未被拜访的数据，应该被淘汰
lru 算法中数据会被放到一个链表中，链表的头节点为最近被拜访的数据，链表的尾节点为长时间没有被拜访的数据
lru算法的外围实现就是哈希表加双向链表 。链表能够用来保护拜访元素的程序，而 hash 表能够帮咱们在 O(1) 工夫复杂度下拜访到元素。
至于为什么是双向链表呢？次要是要删除元素，所以要获取前继节点。数据结构图示如下
应用双向链表 +HashMap
双向链表节点定义如下
public class ListNode<K, V> {
K key;
V value;
ListNode pre;
ListNode next;
public ListNode() {}
public ListNode(K key, V value) {
this.key = key;
this.value = value;
}
}
封装双向链表的罕用操作
public class DoubleList {
private ListNode head;
private ListNode tail;
public DoubleList() {
head = new ListNode();
tail = new ListNode();
head.next = tail;
tail.pre = head;
}
public void remove(ListNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
public void addLast(ListNode node) {
node.pre = tail.pre;
tail.pre = node;
node.pre.next = node;
node.next = tail;
}
public ListNode removeFirst() {
if (head.next == tail) {
return null;
}
ListNode first = head.next;
remove(first);
return first;
}
}
封装一个缓存类，提供最根本的 get 和 put 办法。须要留神，这两种根本的办法都波及到对两种数据结构的批改。
public class MyLruCache<K, V> {
private int capacity;
private DoubleList doubleList;
private Map<K, ListNode> map;
public MyLruCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
doubleList = new DoubleList();
}
public V get(Object key) {
ListNode<K, V> node = map.get(key);
if (node == null) {
return null;
}
// 先删除该节点，再接到尾部
doubleList.remove(node);
doubleList.addLast(node);
return node.value;
}
public void put(K key, V value) {
// 间接调用这边的 get 办法，如果存在，它会在 get 外部被挪动到尾巴，不必再挪动一遍, 间接批改值即可
if ((get(key)) != null) {
map.get(key).value = value;
return;
}
// 如果超出容量，把头去掉
if (map.size() == capacity) {
ListNode listNode = doubleList.removeFirst();
map.remove(listNode.key);
}
// 若不存在，new 一个进去
ListNode node = new ListNode(key, value);
map.put(key, node);
doubleList.addLast(node);
}
}
这里咱们的实现为最近拜访的放在链表的尾节点，不常常拜访的放在链表的头节点
测试一波，输入为链表的正序输入（代码为了简洁没有贴 toString 办法）
MyLruCache<String, String> myLruCache = new MyLruCache<>(3);
// {5 : 5}
myLruCache.put(“5”, “5”);
// {5 : 5}{3 : 3}
myLruCache.put(“3”, “3”);
// {5 : 5}{3 : 3}{4 : 4}
myLruCache.put(“4”, “4”);
// {3 : 3}{4 : 4}{2 : 2}
myLruCache.put(“2”, “2”);
// {4 : 4}{2 : 2}{3 : 3}
myLruCache.get(“3”);
因为 LinkedHashMap 的底层实现就是哈希表加双向链表，所以你能够用 LinkedHashMap 替换 HashMap 和 DoubleList 来改写一下下面的类。
我来演示一下更骚的操作，只须要重写一个流量交易构造函数和 removeEldestEntry 办法即可。
应用 LinkedHashMap 实现 LRU
public class LruCache<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LruCache(int cacheSize) {
/**
- initialCapacity: 初始容量大小
- loadFactor: 负载因子
- accessOrder: false 基于插入排序（默认），true 基于拜访排序
*/
super(cacheSize, 0.75f, true);
this.cacheSize = cacheSize;
}
/**
- 当调用 put 或者 putAll 办法时会调用如下办法，是否删除最老的数据，默认为 false
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cacheSize;
}
}
留神这个缓存并不是线程平安的，能够调用 Collections.synchronizedMap 办法返回线程平安的 map
LruCache<String, String> lruCache = new LruCache(3);
Map<String, String> safeMap = Collections.synchronizedMap(lruCache);
Collections.synchronizedMap 实现线程平安的形式很简略，只是返回一个代理类。代理类对 Map 接口的所有办法加锁
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
LFU算法
LRU 算法有一个问题，当一个长时间不被拜访的 key，偶然被拜访一下后，可能会造成一个比这个 key 拜访更频繁的 key 被淘汰。
即 LRU 算法对 key 的冷热水平的判断可能不精确。而 LFU 算法（Least Frequently Used，最不常常应用）则是依照拜访频率来判断 key 的冷热水平的，每次删除的是一段时间内拜访频率较低的数据，比 LRU 算法更精确。
应用 3 个 hash 表实现 lfu 算法
那么咱们应该如何组织数据呢？
为了实现键值的对快速访问，用一个 map 来保留键值对
private HashMap<K, Integer> keyToVal;
还须要用一个 map 来保留键的拜访频率
private HashMap<K, Integer> keyToFreq;
当然你也能够把值和拜访频率封装到一个类中，用一个 map 来代替上述的 2 个map
接下来就是最外围的局部，删除拜访频率最低的数据。
- 为了能在 O(1)工夫复杂度内找到拜访频率最低的数据，咱们须要一个变量 minFreq 记录拜访最低的频率
- 每个拜访频率有可能对应多个键。当空间不够用时，咱们要删除最早被拜访的数据，所以须要如下数据结构，Map< 频率, 有序汇合 >。每次内存不够用时，删除有序汇合的第一个元素即可。并且这个有序汇合要能疾速删除某个 key，因为某个 key 被拜访后，须要从这个汇合中删除，退出 freq+ 1 对应的汇合中
- 有序汇合很多，然而能满足疾速删除某个 key 的只有 set，然而 set 插入数据是无序的。幸好 Java 有LinkedHashSet这个类，链表和汇合的结合体，链表不能疾速删除元素，然而能保障插入程序。汇合外部元素无序，然而能疾速删除元素，完满
上面就是具体的实现。
public class LfuCache<K, V> {
private HashMap<K, V> keyToVal;
private HashMap<K, Integer> keyToFreq;
private HashMap<Integer, LinkedHashSet<K>> freqTokeys;
private int minFreq;
private int capacity;
public LfuCache(int capacity) {
keyToVal = new HashMap<>();
keyToFreq = new HashMap<>();
freqTokeys = new HashMap<>();
this.capacity = capacity;
this.minFreq = 0;
}
public V get(K key) {
V v = keyToVal.get(key);
if (v == null) {
return null;
}
increaseFrey(key);
return v;
}
public void put(K key, V value) {
// get 办法外面会减少频次
if (get(key) != null) {
// 从新设置值
keyToVal.put(key, value);
return;
}
// 超出容量，删除频率最低的 key
if (keyToVal.size() >= capacity) {
removeMinFreqKey();
}
keyToVal.put(key, value);
keyToFreq.put(key, 1);
// key 对应的 value 存在，返回存在的 key
// key 对应的 value 不存在，增加 key 和 value
freqTokeys.putIfAbsent(1, new LinkedHashSet<>());
freqTokeys.get(1).add(key);
this.minFreq = 1;
}
// 删除呈现频率最低的 key
private void removeMinFreqKey() {
LinkedHashSet<K> keyList = freqTokeys.get(minFreq);
K deleteKey = keyList.iterator().next();
keyList.remove(deleteKey);
if (keyList.isEmpty()) {
// 这里删除元素后不须要从新设置 minFreq
// 因为 put 办法执行完会将 minFreq 设置为 1
freqTokeys.remove(keyList);
}
keyToVal.remove(deleteKey);
keyToFreq.remove(deleteKey);
}
// 减少频率
private void increaseFrey(K key) {
int freq = keyToFreq.get(key);
keyToFreq.put(key, freq + 1);
freqTokeys.get(freq).remove(key);
freqTokeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
freqTokeys.get(freq + 1).add(key);
if (freqTokeys.get(freq).isEmpty()) {
freqTokeys.remove(freq);
// 最小频率的 set 为空，key 被挪动到 minFreq+ 1 对应的 set 了
// 所以 minFreq 也要加 1
if (freq == this.minFreq) {
this.minFreq++;
}
}
}
测试一下
LfuCache<String, String> lfuCache = new LfuCache(2);
lfuCache.put(“1”, “1”);
lfuCache.put(“2”, “2”);
// 1
System.out.println(lfuCache.get(“1”));
lfuCache.put(“3”, “3”);
// 1 的频率为 2，2 和 3 的频率为 1，但 2 更早之前被拜访，所以被革除
// 后果为 null
System.out.println(lfuCache.get(“2”));