一、什么是LRU
LRU是什么？按照英文的直接原義就是Least Recently Used,最近最久未使用法，它是按照一個非常著名的計算機作業系統基礎理論得來的：最近使用的頁面資料會在未來一段時期內仍然被使用,已經很久沒有使用的頁面很有可能在未來較長的一段時間內仍然不會被使用，基于這個思想,會存在一種快取淘汰機制，每次從記憶體中找到最久未使用的資料然后置換出來，從而存入新的資料！它的主要衡量指標是使用的時間，附加指標是使用的次數，在計算機中大量使用了這個機制，它的合理性在于優先篩選熱點資料，所謂熱點資料，就是最近最多使用的資料！因為，利用LRU我們可以解決很多實際開發中的問題，并且很符合業務場景，
二、LRU的實作原理
根據LRU的原理我們可以知道資料在淘汰時總會先淘汰最久未被使用的，如果我們可以按照資料的更新時間排序不就可以很好的處理這樣的場景了嗎？所以我們采用雙端鏈表，頭部一定是最近更新的資料，尾部就是最久未被更新的資料，
public class LRU<K, V> { private int currentSize;//當前的大小 private int capcity;//總容量 private HashMap<K, Node> caches;//所有的node節點，這里加map的原因是為了提高查詢效率，時間復雜度O(1) private Node first;//頭節點 private Node last;//尾節點 public LRU(int size) { currentSize = 0; this.capcity = size; caches = new HashMap<K, Node>(size); }
插入：添加元素的時候首先判斷是不是新的元素，如果是新元素，判斷當前的大小是不是大于總容量了，防止超過總鏈表大小，如果大于的話直接拋棄最后一個節點，然后再以傳入的key\value值創建新的節點，對于已經存在的元素，直接覆寫舊值，再將該元素移動到頭部，然后保存在map中，
這種方式雖然簡單，在頻繁訪問熱點資料的時候效率高，但是它的缺點在于如果是偶爾的批量訪問不同的資料時其命中率就會很低，比如我頻繁的訪問A，接著訪問不同的資料直到A被淘汰，此時我再訪問A，則不得不又再次把A加入到Cache中，顯然這種方式是不合時宜的，因為A已經訪問了很多次了，不應該將其淘汰而把一堆只訪問一次的資料加入到Cache中，
LRU-K
LRU-K中的K代表最近使用的次數，因此LRU可以認為是LRU-1，LRU-K的主要目的是為了解決LRU演算法“快取污染”的問題，其核心思想是將“最近使用過1次”的判斷標準擴展為“最近使用過K次”，
相比LRU，LRU-K需要多維護一個佇列，用于記錄所有快取資料被訪問的歷史，只有當資料的訪問次數達到K次的時候，才將資料放入快取，當需要淘汰資料時，LRU-K會淘汰第K次訪問時間距當前時間最大的資料，
資料第一次被訪問時，加入到歷史訪問串列，如果資料在訪問歷史串列中沒有達到K次訪問，則按照一定的規則（FIFO,LRU）淘汰；當訪問歷史佇列中的資料訪問次數達到K次后，將資料索引從歷史佇列中洗掉，將資料移到快取佇列中，并快取資料，快取佇列重新按照時間排序；快取資料佇列中被再次訪問后，重新排序，需要淘汰資料時，淘汰快取佇列中排在末尾的資料，即“淘汰倒數K次訪問離現在最久的資料”，
LRU-K具有LRU的優點，同時還能避免LRU的缺點，實際應用中LRU-2是綜合最優的選擇，由于LRU-K還需要記錄那些被訪問過、但還沒有放入快取的物件，因此記憶體消耗會比LRU要多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285716.html
標籤：其他
上一篇：如何讓Android 支持HEIF 圖片解碼和加載（免費的方法）
下一篇：T 語言語法設計(預審稿)