缓存淘汰算法
LRU 算法
- Least Recently Used，即最近最少使用的意思。
- 设计原则：一个数据在最近一段时间未被访问，那在将来访问它的可能性也很小，当限定的空间已存满数据，把最久没有被访问到的数据淘汰
- https://www.jianshu.com/p/ed7e503fbb44
- 实现：
【LinkedHashMap，底层：HashMap 加双链表】
LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数，方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数。
LRU-k 算法
- 主要目的：解决LRU算法“缓存污染”的问题
- 核心思想：将“最近使用过1次”扩展为“最近使用过K次”
- 比LRU多维护一个队列，用于记录所有缓存数据被访问的历史。
只有当数据的访问次数达到K次的时候，才将数据放入缓存。
当需要淘汰数据时，LRU-K淘汰第K次访问时间距当前时间最大的数据。 - LRU-2 最佳
2Q 算法（Two queues）
- 类似 LUR-2，将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，
- 即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。
BKD 树
Lucene 6.0 开始使用
搜索多维数据的一种树
https://www.shenyanchao.cn/blog/2018/12/04/lucene-bkd/
