LinkedHashMap代码详解(一)

HashMap 在遍历map时，数据是无序的，在某些需要按照put顺序遍历时，就用到了 edHashMap， edHashMap是HashMap的子类，并且用一条双向链表来存储数据插入的顺序

transient  edHashMap.Entry<K,V> head; //链表的头节点transient  edHashMap.Entry<K,V> tail; //链表的尾节点final boolean accessOrder;               //是否开启lru算法(最活跃的点放在链表头部)

put():
由于 edHashMap没有put方法，put操作用的还是HashMap的方法，但是重写了newNode(int hash, K key, V value, Node e) ，afterNodeAccess(Node e),afterNodeInsertion(boolean evict)方法
1 table中不存在相同的key

if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);

edhashMap重写了newNode方法，将新增的节点加入链表尾部，上代码

   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {         edHashMap.Entry<K,V> p =            new  edHashMap.Entry<K,V>(hash, key, value, e);         NodeLast(p);        return p;    }    private void  NodeLast( edHashMap.Entry<K,V> p) {         edHashMap.Entry<K,V> last = tail;        tail = p;//尾节点指向新节点        if (last == null)//如果原尾节点为空，证明链表还没有数据，头节点指向新节点p            head = p;         else {        //链表不为空            p.before = last;             last.after = p;//原尾节点建立双向链接        }    }

2 table数组中存在相同的key

           if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }

发生了节点数据操作(value替换)，如果开启了LRU(accessOrder=true)，则将修改的节点放入链表尾部，HashMap.afterNodeAccess() 为空函数
edHashMap overwirte了该方法

      void afterNodeAccess(Node<K,V> e) { // move node to last         edHashMap.Entry<K,V> last;        if (accessOrder && (last = tail) != e) {             edHashMap.Entry<K,V> p =                ( edHashMap.Entry<K,V>)e, b = p.before, a = p.after;                          /**重写上面的赋值操作             edHashMap.Entry<K,V> p =( edHashMap.Entry<K,V>)e；             edHashMap.Entry<K,V> b(befor) = p.before；             edHashMap.Entry<K,V> a(after) = p.after;                       **/            p.after = null; //将修改的节点after置为null            if (b == null)  //如果b==null  证明e是头结点                head = a;  //将链表头结点指向 e.next            else            //e不是头结点                b.after = a;  // e.befor.after = e.after                             // e节点的上一个节点的next指向e的下一个节点,移除e            if (a != null)   //如果e的下一个节点不为空                a.before = b;//e.after.befor= e.after                             // e节点的下一个节点的befor指向e的上一个节点，双向链表的反向箭头            else             // a == null e是尾部节点                last = b;    //last指向e的上一个节点            if (last == null) //如果 last== null 证明 只有一个节点                head = p;      //头部尾部都指向该节点            else {              // p不是头节点                p.before = last; //将p放在链表尾部                 last.after = p;            }            tail = p;            ++modCount;        //map操作数+1，(重新赋值且开启LRU，modCount会两次+1)        }    }

3 在执行完put操作后，调用afterNodeInsertion方法

    void afterNodeInsertion(boolean evict) { // possibly remove eldest         edHashMap.Entry<K,V> first;        if (evict && (first = head) != null && removeEldestEntry(first)) {            K key = first.key;            removeNode(hash(key), key, null, false, true);        }    }   protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {        return false;    }

evict 在hashMap中默认为true， edHashMap.removeEldestEntry ()默认返回false，
该方法的yongfasj用法是 配合LRU算法，自定义Class继承 edHashMap方法并重写removeEldestEntry 方法，
在特定条件下返回true，移除链表中最左侧的节点
可以使用该特性进行缓存创建，保留最近活跃的数据，开启LRU需要将开头提到的accessOrder 置为true

该参数只能在 edHashMap new时指定，需要同时指定扩展因子loadFactor 默认为0.75f

    public  edHashMap(int initialCapacity,                         float loadFactor,                         boolean accessOrder) {        super(initialCapacity, loadFactor);        this.accessOrder = accessOrder;    }

get():
edHashMap get方法，可以看到 和hashMap是一致的，只是加了accessOrder 判断，开启LRU后，将获取的数据放在链表的最右侧，提高该节点的活跃程度

    public V get(  key) {        Node<K,V> e;        if ((e = getNode(hash(key), key)) == null)            return null;        if (accessOrder)            afterNodeAccess(e);        return e.value;    }