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();
}
}
}