linkedhashmap繼承自hashmap,他的底層維護的一個鏈表， private transient Entry<K,V> header 來記錄元素的插入順序和訪問順序;
hashmap的構造函數中調用init()方法，而linkedhashmap中重寫了init(),將head元素初始化
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
private final boolean accessOrder這個屬性表示是否要根據訪問順序改變線性結構
在linkedhashmap中改寫了hashmap的get()方法，增加了 e.recordAccess(this)，這個方法主要是根據accessOrder的值判斷是否需要實現LRU，
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
addBefore這個方法是把剛訪問的元素放到head的前面
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
put方法繼承自hashmap,hashmap預留了 e.recordAccess(this)這個方法：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
并通過重寫 addEntry(hash, key, value, i)這個方法，實現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;//找到最老的元素，這個在addBefore里確定，初次賦值是當只有一個head時候，你插入一個元素
if (removeEldestEntry(eldest)) {//這個是受保護的方法，需要自己制定刪除策略，比如size() > 最大容量,可自己實現，默認為false,也就是不開啟
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
自己重寫這個方法，指定刪除策略：
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
因此，可用linkedhashmap 構建一個基于LRU算法的緩存。
package com.google.study.cache;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.ReentrantLock;
public class SimpleCache<K, V> extends LinkedHashMap<K, V> {
private int maxCapacity;
private ReentrantLock lock = new ReentrantLock();
public SimpleCache(int maxCapacity, float load_factory) {
super(maxCapacity, load_factory, true);
this.maxCapacity = maxCapacity;
}
public int getMaxCapacity() {
return maxCapacity;
}
public void setMaxCapacity(int maxCapacity) {
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
// TODO Auto-generated method stub
return super.removeEldestEntry(eldest);
}
public V get(Object key) {
lock.lock();
try {
return super.get(key);
} finally {
lock.unlock();
}
}
public V put(K k, V v) {
lock.lock();
try {
return super.put(k, v);
} finally {
lock.unlock();
}
}
@Override
public void clear() {
lock.lock();
try {
super.clear();
} finally {
lock.unlock();
}
}
@Override
public int size() {
lock.lock();
try {
return super.size();
} finally {
lock.unlock();
}
}
}