LInkHashMap源码分析

说LinkHashMap之前，我们先来谈谈什么是LRU算法？

按照英文的直接原义就是Least Recently Used,最近最久未使用法，它是按照一个非常注明的计算机操作系统基础理论得来的：最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。基于这个思想,会存在一种缓存淘汰机制，每次从内存中找到最久未使用的数据然后置换出来，从而存入新的数据！它的主要衡量指标是使用的时间，附加指标是使用的次数。在计算机中大量使用了这个机制，它的合理性在于优先筛选热点数据，所谓热点数据，就是最近最多使用的数据！因为，利用LRU我们可以解决很多实际开发中的问题，并且很符合业务场景。

双向循环链表

public class LinkedHashMap<K,V>extends HashMap<K,V>{
transient LinkedEntry<k,V> header; //头结点
private final boolean accessOrder;   //true：访问排序         false：插入排序

public LinkedHashMap(){
　　init(); 
　　accessOrder=false; //默认情况为false，基于插入排序的
}

static class LinkedEntrykK,V> extends HashMapEntry<K, V>     //linkedEntry继承了HashMapEntry，也就拥有了父类的所有属性和方法

{
    LinkedEntry<K, V> nxt;
    LinkedEntry<K, V> prv;

static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;
    V value;
    final int hash;
    HashMapEntry<K, V> next;

    HashMapEntry(K key, V value, int hash, HashMapEntry<k, V> next) {
        this.key = key;
        this.value = value;
        this.hash = hash;
        this.next = next;
    }

linkedHashMap只是重写了hashMap put方法里的addNewEntry增加新元素方法

@Override
void addNewEntry(K key, V value, int hash, int index) {
    LinkedEntry<K, V> header = this.header;

    LinkedEntry<K, V> eldest = header.nxt;

    if (eldest != header && removeEldestEntry(eldest)) {如果头结点不是自己抱自己
        remove(eldest.key);
    }
    LinkedEntry<K, V> oldTail = header.prv;
    LinkedEntry<K, V> newTail = new LinkedEntry<K, V>(
            key, value, hash, table[index], header, oldTail);
    table[index] = oldTail.nxt = header.prv = newTail;
}

//默认构造方法，头结点自己指向自己，也就是自己抱自己
@Override void init(){
header]=new uinkedEntry<K,V>();


LinkedEntry(){
super(nu11,nul1,0,null); nxt = prv = this;

隐藏了一列一维数组，将来还是有用的

默认return false;不会移除     方法的作用：是在内存过高时，移除最老的元素，所以需要重写这个方法，return true；
protected boolean removeEldestEntry(Map. Entry<k,V>eldest){
　　return false;
}

新进来的要放在队头

最后进来的是最新的

顺序存储，谁先存进来的，谁先被移出去。

访问排序，谁最近被访问就是最活跃的，最后才被移出去