LinkedHashMap源码浅析（一）：集合的基本操作

LinkedHashMap继承了HashMap，所以HashMap的一些方法或者属性也会被继承；同时也实现了Map结构,
LinkedHashMap数据结构相比较于HashMap来,添加了双向指针,分别指向前一个节点——before和后一个节点——after
LinkedHashMap的迭代器为遍历节点提供了自己的实现——LinkedHashIterator，对于Key、Value、Entry的3个迭代器
具有访问顺序和插入顺序两种 

插入元素,调用的是HashMap的put(),添加成功之后,重写了newNode()方法,将插入成功的元素插入到双向链表当中
删除元素,同样调用的是HashMap的remove(),删除成功之后,重写了afterNodeRemoval(),将删除的元素从双向链表中剔除,

获取指定元素,获取成功之后,如果设置的linkedhashMap的顺序是访问顺序,则将获取成功的元素插入到双向链表的链尾

lru缓存 最近最少原则

LinkedHashMap继承于HashMap,在HashMap的基础上(主要是数组和链表的结构基础上)其内部还维护了一个双向链表,在每次插入数据或者访问数据、修改数据时,会跳转链表的节点顺序,以此来决定迭代时输入的顺序

// 因为是继承了HashMap,所以构造方法里面调用了HashMap的构造方法,入参同HashMap一样,初始容量和加载因子
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }
// 前面我们说过,LinkedHashMap相对于HashMap是有序的,或插入顺序或访问顺序,而选择那种顺序的标识就是accessOrder,默认为false(插入顺序)
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

put
LinkedHashMap并没有重写put(),所以添加数据的时候用的是HashMap的put(),不过重写的是创建节点的方法newNode(),在创建头结点或者添加尾节点时会用到这个方法，统一的说就是创建新节点的时候会用到:
LinkedHashMap#newNode()

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMapEntry<K,V> p =
            new LinkedHashMapEntry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

因为LinkedHashMap中使用的节点是LinkedHashMapEntry,所以这里重写也在情理之中,但是前面有说过LinkedHashMap是有顺序的,所以这里面肯定是有排序的逻辑的:
LinkedHashMap#linkNodeLast():

    private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

首先将新创建的节点指向尾节点,这个没有问题,LinkedHashMap本身就是双链表,新节点加入链表是要加入尾节点的,然后判断原先的尾节点是否为空,如果为空的话,则说明当前节点为头结点,所以,你懂得,将新建的节点再次指向头结点,如果插入的节点非头结点,就会走下面的else,然后完成两个节点的相互关联。
因为LinkedHashMapEntry代码比较简单,这里就一并说了,LinkedHashMapEntry继承于HashMap,并且拥有两个成员变量before和after用于维护双链表

    static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

在HashMap的putVal()中的倒是第二行代码：
HashMap#putVal():

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
       ...
       // 代码省略
       ...
        afterNodeInsertion(evict);
        return null;
    }

这里调用了afterNodeInsertion()，但是这个方法在HashMap中是个空方法,而在LinkedHashMap才重写实现这个方法
HashMap#afterNodeInsertion():

    void afterNodeInsertion():(boolean evict) { }

LinkedHashMap#afterNodeInsertion():

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

afterNodeInsertion方法的evict参数如果为false，表示哈希表处于创建模式。只有在使用Map集合作为构造器创建LinkedHashMap或HashMap时才会为false,这是第一个条件,第二个条件则是,集合不能为空，第三个条件是removeEldestEntry()的返回值。
LinkedHashMap#removeEldestEntry():

 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

此方法在LinkedHashMap中的实现默认返回false，所以这个判断体一般进不来,如果为true的话,我们可以看到通过removeNode()删除了头结点,头结点有两种意义,一种是插入顺序下的头结点,此时的头结点作为集合中最先插入的元素,同时也是集合中最老的元素,删除头结点代表删除集合中最老的元素,结合调用此方法的情景是在添加新元素之后,因为使用这个方法的场景就呼之欲出了,集合添加了新元素,但是由于某种原因,不得不删除集合中的最老的元素；另一种意义就是访问顺序下的头结点,此时的头结点代表刚刚被访问过的的元素,删除头结点代表删除刚刚访问过的元素,个人觉得这种情况下的删除头结点相对于上一种情况毫无道理可言。当然第一种的情况适合在构建缓存时使用,添加新元素,因为空间不够了，所以需要移除集合中最老的元素,但是这个方法是在添加完元素之后才被调用的,所以只能确定要被添加的元素的大小,并且保证一定能被添加进去,这个方法才能被调用到,所以现在的这个方法并不特别是实用.
在HashMap中的putVal中还有一个方法afterNodeAccess()，在HashMap中依旧是空实现,LinkedHashMap中实现这个方法，这个方法跟访问顺序有关系会在下一张中进行介绍,这里就不多说了

get
获取数据用的是自己的方法():
LinkedHashMap#get():

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

如果能够根据key值获取到节点,则直接返回,如果该节点为null,则返回null,如果需要对链表进行访问排序,则调用afterNodeAccess(),关于排序我会单独来说这里就不多说了。

remove
LinkedHashMap没有重写remove方法,也没有重写removeNode(),不过在HashMap中的removeNode()的最后,会调用afterNodeRemoval(),这个方法是够空方法
HashMap#afterNodeRemoval():

void afterNodeRemoval(Node<K,V> p) { }

不过这个方法在LinkedHashMap中进行了重写:
LinkedHashMap#afterNodeRemoval():

    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMapEntry<K,V> p =
            (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

afterNodeRemoval()在LinkedHashMap的作用是使要删除的节点脱离双链表,虽然在HashMap中进行了处理,但只是脱离了HashMap的单链表或者红黑树,LinkedHashMap中的双链表则需要单独的实现,
这个方法其实也很简单,主要是获取到要删除节点的前后节点,然后使这两个节点相互关联

迭代器

LinkedHashMap中的迭代器与HashMap一样有三种,但是确实跟HashMap中的迭代器没有关系

LinkedKeySet

size 当前集合的元素数量
iterator 得到一个迭代器
remove() 删除当前遍历到的节点

LinkedHashMap#LinkedKeySet#iterator()

       public final Iterator<K> iterator() {
            return new LinkedKeyIterator();
        }

LinkedKeyIterator继承于LinkedHashIterator

    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().getKey(); }
    }

LinkedHashIterator的属性:

next 当前节点的下一节点
current 当前节点
expectedModCount 修改次数

方法:

hasNext() 是否具有下一节点
nextNode() 获取下一节点
remove 删除当前节点

我们先看构造器:

        LinkedHashIterator() {
            next = head;
            expectedModCount = modCount;
            current = null;
        }

首先初始化next赋值为头结点,

        final LinkedHashMapEntry<K,V> nextNode() {
            LinkedHashMapEntry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            next = e.after;
            return e;
        }

每次调用此方法都会返回原先的next节点,然后更新next节点为after节点.

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }

直接通过removeNode进行删除,双链表的脱离在上面已经说过了,

    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().getKey(); }
    }

    final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

相等的还有另外两个迭代器,逻辑一样 ,代码如上