1、业务场景：
由于业务场景是需要查询团单和门店的固定品类，而这些信息比较固定、不容易变化，为了减少对下游的压力，使用了一个本地缓存druid的LRUCache
private static LRUCache<Integer,Integer> dealCatCache = new LRUCache<Integer, Integer>(Integer.parseInt(size),16, 0.75f, true);
2、源码：
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private static final long serialVersionUID = 1L;
private final int maxSize;
public LRUCache(int maxSize){
this(maxSize, 16, 0.75f, false);
}
public LRUCache(int maxSize, int initialCapacity, float loadFactor, boolean accessOrder){
super(initialCapacity, loadFactor, accessOrder);
this.maxSize = maxSize;
}
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return this.size() > this.maxSize;
}
}
可以看出LRUCache是通过继承了LinkedHashMap这一个双向链表来实现LRU算法的。
来看下super(initialCapacity, loadFactor, accessOrder);
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
LinkedHashMap重写了init方法
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
可以看到LinkedHashMap始终维持了一个header不放在数组中，就是用来指示开始元素和标志结束元素的。
接下来看看put操作，首先进入hashmap的public V put(K key, V value) 方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
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;
}
hashmap的put操作是先看table数组里面是否有该key，有的话把old value替换为新的value同时执行LinkedHashMap中的recordAccess方法，没有该key，也是在LRU算法的情况下把该key移到链表尾部(header节点的前一个节点)。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
boolean accessOrder是表示该LinkedHashMap是FIFO（false）还是LRU（true）策略进出元素的。
remove(); addBefore(lm.header);代码如下
private void remove() {
before.after = after;
after.before = before;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
可以看到，先执行remove把该元素从链表抹去，然后把header元素和该元素before和after关联起来，这样就实现在put已有key的情况下，把对应key的元素移到链表尾部了。接下来再看如果没有改key的操作
LinkedHashMap中
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
HashMap中
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
addEntry代码和hashmap一致，重写了createEntry代码，多做了addBefore操作，把header和新加的元素建立首尾关联
接下来看看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;
}
同样执行了recordAccess，所以不再赘述。
总结一下LRU的本质：插入时会正常插入HashMap存储数据，同时LinkedHashMap会维护一个双向队列记录尾节点header，没插入一个entry，都把它插入到header的前一位，如果对应key存在，则替换value值，把该entry插入到header前一位；如果做get操作，也把该key-value插入到header前一位。在插入过程中会进入removeEldestEntry方法判断是否要移除最老的元素，确定移除，则把header后一位元素移除。
