手寫最近很少使用算法lru
這道題在很多公司面試的時候都可能被問到多糠，主要考察面試者對緩存算法的原理的了解。
先來了解一下什么是最近很少使用算法知纷？
最近很少使用算法：就是根據(jù)最近訪問的記錄壤圃，對緩存的數(shù)據(jù)進行淘汰。也就是說琅轧，如果一個數(shù)據(jù)最近被訪問伍绳，或經(jīng)常被訪問，則把數(shù)據(jù)放到列表的前面乍桂。而數(shù)據(jù)很久未訪問冲杀，或者訪問率較低效床，就會被放在對位，在隊列內(nèi)存不足的時候將其移除緩存隊列权谁，過程如圖：
Android中就帶有LruCache的類剩檀，這個類被廣泛使用，比如glide緩存圖片就用到這個算法旺芽。但是這個算法其實也沒有那么復雜谨朝，讀過LruCache源碼的同學都知道，這個算法的底層實際上就是用了一個LinkedHashMap甥绿。我們需要了解的其實LinkedHashMap的原理字币。
LinkedHashMap：
大家都知道HashMap的原理，HashMap內(nèi)部維護單鏈表共缕，存儲數(shù)據(jù)是無序的洗出，而我們Lru算法則有訪問順序的需求，所以不能使用HashMap图谷，這一點LinkedHashMap恰好能滿足翩活，LinkedHashMap內(nèi)部維護的是雙向鏈表，而且邏輯上實現(xiàn)了可以保證訪問的順序便贵，即：每次訪問或者插入數(shù)據(jù)的時候會被放到雙向鏈表的尾部菠镇，這個屬性被激活需要設置 accessOrder 為true即可。
我們已經(jīng)可以保證隊列里面存儲的值按照我們訪問的順序調(diào)整承璃，那我們實現(xiàn)Lru算法就可以很簡單了利耍。
但是還有一點，因為我們的隊列滿了以后盔粹，再存放數(shù)據(jù)的時候需要刪除最少使用的值隘梨，也就是鏈表首位的值（每次訪問或者插入數(shù)據(jù)的時候會被放到雙向鏈表的尾部）
好，總結一下如何實現(xiàn)lru算法：
accessOrder
上面兩點中舷嗡，第一點LinkedHashMap已經(jīng)實現(xiàn)我們只需要設置accessOrder`屬性為true即可轴猎。第二點需要我們?nèi)崿F(xiàn)。
開始寫代碼：
初始化一個LinkedHashMap进萄，設置accessOrder`屬性為true捻脖，讓它按照訪問順序排序，并設置隊列的最大容量maxSize中鼠。
public Lru(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap(0, 0.75f, true);
}
實現(xiàn)存儲數(shù)據(jù)的邏輯可婶。每次存儲一個數(shù)據(jù)，size應該加1兜蠕。這里面有個小技巧：HashMap的put方法在添加一個之前已經(jīng)存在的key的值的時候扰肌，會覆蓋以前的key對應value抛寝，并返回以前的value熊杨，如：V previous = map.put(key, value)之后previous不為null曙旭，則說明這個key之前就已經(jīng)有值，再次添加值只是覆蓋以前的值晶府，所以這時候size不應該加1桂躏。
public V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
//這是HashMap的屬性:如果key之前已經(jīng)存有值，則這里會返回之前的值川陆。
previous = map.put(key, value);
//如果之前已經(jīng)存在值剂习，則我們添加的值會把以前的值覆蓋，所以size就不會增加较沪，如果之前不存在值鳞绕，這里添加數(shù)據(jù)就會增加一個size
if (previous == null) {
size += 1;
}
}
//存放數(shù)據(jù)，刪除多余數(shù)據(jù)
trimToSize(maxSize);
return previous;
}
添加數(shù)據(jù)的時候應該注意數(shù)據(jù)是否超出容量了尸曼，如果超出了们何，就應該刪除最少使用的數(shù)據(jù)。這里使用循環(huán)刪除最少使用的數(shù)據(jù)控轿，直到size<=maxSize冤竹。
//如果size>maxSize，則刪除多余的數(shù)據(jù)
private void trimToSize(int maxSize) {
while (true) {
K key;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
return;
}
if (size <= maxSize || map.isEmpty()) {
break;
}
Map.Entry toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
map.remove(key);
size -= 1;
}
}
}
獲取一個數(shù)據(jù)茬射，也就是訪問數(shù)據(jù)鹦蠕，LinkedHashMap會自動把訪問的數(shù)據(jù)放到鏈表的尾部，所以這里我們不用太操心
//獲取一個數(shù)據(jù)
public V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
return mapValue;
}
}
return null;
}
清空數(shù)據(jù)就更簡單了在抛，我們既可以直接調(diào)用linkedhashmap的clear方法清空隊列钟病，也可以利用我們上面寫的循環(huán)刪除的方法，只要把maxSize參數(shù)設置為-1刚梭，就可以清空隊列里面的數(shù)據(jù)：
//清除空數(shù)據(jù)
public void evictAll() {
//map.clear();
trimToSize(-1);
}
以上 我們已經(jīng)實現(xiàn)了lru的基本操作档悠。只要同學知道LruCache的原理，這個代碼不難寫出來望浩。
一下是完整代碼：（總體思想來自LruCache）
public class Lru {
private final LinkedHashMap map;
private int size;
private int maxSize;
public Lru(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap(0, 0.75f, true);
}
public V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
return mapValue;
}
}
return null;
}
public V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
size += 1;
previous = map.put(key, value);
if (previous != null) {
size -= 1;
}
}
trimToSize(maxSize);
return previous;
}
private void trimToSize(int maxSize) {
while (true) {
K key;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
return;
}
if (size <= maxSize || map.isEmpty()) {
break;
}
Map.Entry toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
map.remove(key);
size -= 1;
}
}
}
public V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
previous = map.remove(key);
if (previous != null) {
size -= 1;
}
}
return previous;
}
public void evictAll() {
trimToSize(-1);
}
public synchronized int size() {
return size;
}
public synchronized int maxSize() {
return maxSize;
}
}
想學習更多Android知識辖所，或者獲取相關資料請加入Android技術開發(fā)交流2群：935654177。本群可免費獲取Gradle磨德，RxJava缘回，小程序，Hybrid典挑，移動架構酥宴，NDK，React Native您觉，性能優(yōu)化等技術教程拙寡！
