阿裡巴巴筆試考到了LRU,一激動忘了怎麼回事了。。準備不充分啊。。
緩存這個東西就是為了提高運作速度的,由于緩存是在寸土寸金的記憶體裡面,不是在硬碟裡面,是以容量是很有限的。LRU這個算法就是把最近一次使用時間離現在時間最遠的資料删除掉。先說說List:每次通路一個元素後把這個元素放在 List一端,這樣一來最遠使用的元素自然就被放到List的另一端。緩存滿了t的時候就把那最遠使用的元素remove掉。但更實用的是HashMap。因為List太慢,要删掉的資料總是位于List底層數組的第一個位置,删掉之後,後面的資料要向前補位。。是以複雜度是O(n),那就用連結清單結構的LinkedHashMap呗~,LinkedHashMap預設的元素順序是put的順序,但是如果使用帶參數的構造函數,那麼LinkedHashMap會根據通路順序來調整内部 順序。 LinkedHashMap的get()方法除了傳回元素之外還可以把被通路的元素放到連結清單的底端,這樣一來每次頂端的元素就是remove的元素。
構造函數如下:
public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder);
initialCapacity 初始容量
來個例子吧:
import java.util.*;
class Test
{
public static void main(String[] args) throws Exception{
Map<Integer,Integer> map=new LinkedHashMap<>(10,0.75f,true);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
//現在周遊的話順序肯定是9,7,5,3
//下面通路了一下9,3這個鍵值對,輸出順序就變喽~
map.get(9);
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
輸出
7
5
3
9
好玩吧~
下面開始實作LRU緩存喽~
import java.util.*;
//擴充一下LinkedHashMap這個類,讓他實作LRU算法
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{
//定義緩存的容量
private int capacity;
private static final long serialVersionUID = 1L;
//帶參數的構造器
LRULinkedHashMap(int capacity){
//調用LinkedHashMap的構造器,傳入以下參數
super(16,0.75f,true);
//傳入指定的緩存最大容量
this.capacity=capacity;
}
//實作LRU的關鍵方法,如果map裡面的元素個數大于了緩存最大容量,則删除連結清單的頂端元素
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
}
//測試類
class Test{
public static void main(String[] args) throws Exception{
//指定緩存最大容量為4
Map<Integer,Integer> map=new LRULinkedHashMap<>(4);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
map.put(6,6);
//總共put了5個元素,超過了指定的緩存最大容量
//周遊結果
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
輸出結果如下
9=3
6
分析一下:使用帶參數構造器,且啟用LRU模式的LinkedHashMap會在每次有新元素加入的時候,判斷目前儲存元素是否超過了緩存上限,也就是執行
一次removeEldestEntry方法,看最後的周遊結果,發現果然把9删除了,LRU發揮作用了~