LRU 算法

缓存淘汰算法

LRU 算法

1. Least Recently Used，即最近最少使用的意思。
2. 设计原则：一个数据在最近一段时间未被访问，那在将来访问它的可能性也很小，当限定的空间已存满数据，把最久没有被访问到的数据淘汰
3. https://www.jianshu.com/p/ed7e503fbb44
4. 实现：
   【LinkedHashMap，底层：HashMap 加双链表】
   LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数，方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数。

LRU-k 算法

1. 主要目的：解决LRU算法“缓存污染”的问题
2. 核心思想：将“最近使用过1次”扩展为“最近使用过K次”
3. 比LRU多维护一个队列，用于记录所有缓存数据被访问的历史。
   只有当数据的访问次数达到K次的时候，才将数据放入缓存。
   当需要淘汰数据时，LRU-K淘汰第K次访问时间距当前时间最大的数据。
4. LRU-2 最佳

2Q 算法（Two queues）

1. 类似 LUR-2，将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，
2. 即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。

BKD 树

Lucene 6.0 开始使用

搜索多维数据的一种树
https://www.shenyanchao.cn/blog/2018/12/04/lucene-bkd/