和hashmap相比，linkedhashmap是有序的，順序方式兩種，插入順序和訪問(wèn)順序，而后面要說(shuō)的lru就是借助了訪問(wèn)順序的linkedhashmap實(shí)現(xiàn)。
使用：
Lru<Character, Integer> lru = new Lru<Character, Integer>(16, 0.75f, true);? ?
?String s = "1234567";? ?
?for (int i = 0; i < s.length(); i++) {? ? ? ?
? ? ? ? lru.put(s.charAt(i), i);? ?
}? ?
System.out.println("第三個(gè)是： " + lru.get('2'));? ?
System.out.println("大小 ：" + lru.size());? ?
System.out.println("LRU ：" + lru);
輸出：
第三個(gè)是： 3
大小 ：6
LRU ：{1，2，4，5，6，3}
accessorder構(gòu)造方法第三個(gè)參數(shù)，默認(rèn)為false。是否按照訪問(wèn)順序排序。
這里要注意的一點(diǎn)，linkedhashmap構(gòu)造方法的第三個(gè)參數(shù) accessorder = true。按照訪問(wèn)順序排序，從例子中可以看到，插入順序123456，而經(jīng)過(guò)一次訪問(wèn)get("2")之后，那么順序變?yōu)?24563。這就是accessorder的特性。
源碼分析：
linkedhashmap繼承hashmap，下面是關(guān)鍵的兩個(gè)成員變量，accessorder上面給出解釋。
private transient Entry<K,V> header;
private final boolean accessOrder;
private static class Entry<K,V> extends HashMap.Entry<K,V> {
?Entry<K,V> before, after;
}? ??
上面源碼看，重寫了hashmap的entry，結(jié)點(diǎn)多了前驅(qū)結(jié)點(diǎn)和后續(xù)結(jié)點(diǎn)，很明顯采用了雙向鏈表。
再來(lái)看一下put方法。
public V put(K key, V value) {
?//省略
?addEntry(hash, key, value, i);
?}
void addEntry(int hash, K key, V value, int bucketIndex) {
? ? ? createEntry(hash, key, value, bucketIndex);
? ? ? // 如果超過(guò)一定數(shù)量，刪除最近沒有使用的，也就是頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。
? ? ? Entry<K,V> eldest = header.after;
? ? ? if (removeEldestEntry(eldest)) {
? ?????????removeEntryForKey(eldest.key);
? ? }
? ? ? else {
?????????if (size >= threshold)
?????????????resize(2 * table.length);
? ? }
}
核心就在當(dāng)注釋，比如設(shè)置的是100個(gè)數(shù)量，那么當(dāng)達(dá)到100，就會(huì)刪除最近最少使用。
再來(lái)看一下get方法。
public V get(Object key) {
?????Entry<K,V> e = (Entry<K,V>)getEntry(key);
?????if (e == null)
?????return null;
?????e.recordAccess(this);
?????return e.value;
}
?????void recordAccess(HashMap<K,V> m) {
?????????LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
?????????if (lm.accessOrder) {//如果為true，則按照訪問(wèn)排序
?????????????lm.modCount++;
?????????????remove();//刪除當(dāng)前訪問(wèn)的結(jié)點(diǎn)
?????????????addBefore(lm.header);//再把當(dāng)前結(jié)點(diǎn)加入到尾部
? ? }
}
private void addBefore(Entry<K,V> existingEntry) {
?????after = existingEntry;//設(shè)置后續(xù)結(jié)點(diǎn)
?????before = existingEntry.before;//設(shè)置前驅(qū)結(jié)點(diǎn)
?????before.after = this; //設(shè)置前驅(qū)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)
?????after.before = this; }//設(shè)置后續(xù)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
在get中調(diào)用addbefore傳入header頭結(jié)點(diǎn)，四行代碼的意思?
設(shè)置當(dāng)前訪問(wèn)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)為頭結(jié)點(diǎn)，
設(shè)置當(dāng)前訪問(wèn)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)為之前頭結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)(也就是之前最后一個(gè)結(jié)點(diǎn))
設(shè)置前驅(qū)結(jié)點(diǎn)(頭結(jié)點(diǎn))的后續(xù)結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)。
設(shè)置后續(xù)結(jié)點(diǎn)的前驅(qū)為當(dāng)前結(jié)點(diǎn)。
這是雙向鏈表增加元素的一般步驟。
所以到這里，開頭的例子為什么get之后就改變了順序原因就明白了。
LRU算法
void addEntry(int hash, K key, V value, int bucketIndex) {
?????createEntry(hash, key, value, bucketIndex);
?????// Remove eldest entry if instructed, else grow capacity if appropriate
? ? ?Entry<K,V> eldest = header.after;
?????//如果removeEldestEntry方法返回為true，那么則刪除1個(gè)節(jié)點(diǎn)
?????//默認(rèn)就是刪除離header節(jié)點(diǎn)最近的節(jié)點(diǎn)，即header的after，即鏈表的頭部
?????if (removeEldestEntry(eldest)) {
?????removeEntryForKey(eldest.key);
?????}
????else {
?????????if (size >= threshold)
?????????????resize(2 * table.length);
?????}
?}
默認(rèn)removeeldestentry()返回的是false，想要使用lru，重寫，返回true。那么每次都是刪除header的下一個(gè)結(jié)點(diǎn)。
