緩存淘汰算法
LRU 算法
- Least Recently Used吕世，即最近最少使用的意思翻翩。
- 設(shè)計原則：一個數(shù)據(jù)在最近一段時間未被訪問，那在將來訪問它的可能性也很小褂萧，當(dāng)限定的空間已存滿數(shù)據(jù)押桃，把最久沒有被訪問到的數(shù)據(jù)淘汰
- http://www.reibang.com/p/ed7e503fbb44
- 實現(xiàn)：
【LinkedHashMap，底層：HashMap 加雙鏈表】
LinkedHashMap中本身就實現(xiàn)了一個方法removeEldestEntry用于判斷是否需要移除最不常讀取的數(shù)箱玷，方法默認是直接返回false怨规，不會移除元素陌宿，所以需要重寫該方法锡足。即當(dāng)緩存滿后就移除最不常用的數(shù)波丰。
LRU-k 算法
- 主要目的：解決LRU算法“緩存污染”的問題
- 核心思想：將“最近使用過1次”擴展為“最近使用過K次”
- 比LRU多維護一個隊列，用于記錄所有緩存數(shù)據(jù)被訪問的歷史舶得。
只有當(dāng)數(shù)據(jù)的訪問次數(shù)達到K次的時候掰烟，才將數(shù)據(jù)放入緩存。
當(dāng)需要淘汰數(shù)據(jù)時沐批，LRU-K淘汰第K次訪問時間距當(dāng)前時間最大的數(shù)據(jù)纫骑。 - LRU-2 最佳
2Q 算法（Two queues）
- 類似 LUR-2，將LRU-2算法中的訪問歷史隊列（注意這不是緩存數(shù)據(jù)的）改為一個FIFO緩存隊列九孩，
- 即：2Q算法有兩個緩存隊列先馆，一個是FIFO隊列，一個是LRU隊列躺彬。
BKD 樹
Lucene 6.0 開始使用
搜索多維數(shù)據(jù)的一種樹
https://www.shenyanchao.cn/blog/2018/12/04/lucene-bkd/
