JDK 1.8 LinkedHashMap 源码分析

由于其源码并不是很长，直接贴出来:

• 可以看到LinkedHashMap继承自HashMap，同时实现map接口最新JDK 1.8 HashMap的数据结构为数组+链表+红黑树。

• LinkedHashMap基于HashMap的数据结构，新增了一条双向链表

• HashMap是无序的，而LinkedHashMap就弥补了该缺点，默认为插入顺序，即最后插入的key-value会加到双向链表的尾部，若定义accessOrder为true的话，则为访问顺序，即put key-value后，调用get，replace等方法，都会将节点放到链表尾部，即符合LRU算法，经常使用的数据放在链表尾部。

• 这里可以通过实现removeEldestEntry接口来自定义自己的LRU算法，即put一个key-value后，根据自己业务的LRU需求，将最旧的数据节点(即双向链表节点的头节点)删除。

package java.util;

import java.util.function.Consumer;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.io.IOException;


public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

    //LinkedHashMap新增双向链表维护的链表条目，这里称其为链表节点
    static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        //比HashMap.Node多了两个节点before，after
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    private static final long serialVersionUID = 3801124242820219131L;

    //双向链表的头节点
    transient LinkedHashMapEntry<K,V> head;

    //双向链表的尾节点
    transient LinkedHashMapEntry<K,V> tail;

    
    //迭代顺序(例如调用entrySet)：
    //accessOrder=true时为访问顺序
    //access-order=false为插入顺序
    final boolean accessOrder;

    //将p放到链表的末尾
    private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;  //旧的链表尾节点
        tail = p; //新的链表尾节点
        
        //若旧的链表尾节点为null
        //证明链表为null
        //将链表头节点赋值为p
        if (last == null)
            head = p;
        
        //若旧的链表尾节点不为null
        else {
            //将新的链表尾节点连接到旧的链表尾节点
            p.before = last;
            last.after = p;
        }
    }

    //将dst节点的前后节点替换为src节点的前后节点
    private void transferLinks(LinkedHashMapEntry<K,V> src,
                               LinkedHashMapEntry<K,V> dst) {
        LinkedHashMapEntry<K,V> b = dst.before = src.before;
        LinkedHashMapEntry<K,V> a = dst.after = src.after;
        
        //若dst的后节点为null
        if (b == null)
            //将链表头节点赋值为dst节点
            head = dst;
            
        //若dst的后节点不为null
        else
            //将dst前节点的后节点赋值为dst节点
            b.after = dst;
        
        //若dst的前节点为null
        if (a == null)
            //将链表尾节点赋值为dst节点
            tail = dst;
            
        //若dst的前节点不为null    
        else
            //将dst后节点的前节点赋值为dst节点
            a.before = dst;
    }

    //重置为初始默认状态。 由clone和readObject调用
    void reinitialize() {
        super.reinitialize();
        head = tail = null;
    }
    
    //覆盖HashMap的创建普通节点方法
    //创建一个新的链表节点
    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;
    }
    
    //覆盖HashMap的红黑树节点转换为普通单链表节点方法
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p;
        //将红黑树节点转换为双链表节点
        LinkedHashMapEntry<K,V> t =
            new LinkedHashMapEntry<K,V>(q.hash, q.key, q.value, next);
        
        //节点转换完成后，将新的节点的前后节点指向原本节点的前后节点
        transferLinks(q, t);
        return t;
    }
    
    //覆盖HashMap的创建红黑树节点方法
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        //创建红黑树节点
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        
        //创建节点完成后将其插入到双向链表尾部
        //这里可以直接将TreeNode强转为LinkedHashMapEntry
        //是因为在HashMap中:
        //TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> 
        linkNodeLast(p);
        return p;
    }

    //覆盖HashMap的普通单链表节点转换为红黑树节点方法
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        //由上面newNode接口我们可以知道，创建的节点都为LinkedHashMapEntry
        LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p;
        TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
        
        //节点转换完成后，将新的节点的前后节点指向原本节点的前后节点
        //这里可以直接将TreeNode强转为LinkedHashMapEntry
        //是因为在HashMap中:
        //TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> 
        transferLinks(q, t);
        return t;
    }

    //下面三个接口为HashMap预留个LinkedHashMap的接口
    
    //HashMap移除节点的时候会回调该接口
    void afterNodeRemoval(Node<K,V> e) { 
        //声明当前要移除的节点p = e
        //声明b = p的前一个节点
        //声明a = p的后一个节点
        LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, 
        b = p.before, a = p.after;
        
        //因为p节点要移除，这里将其前后节点都置为null
        p.before = p.after = null;
        
        //如果b为null，证明要删除的节点为链表头节点
        if (b == null)
            //这里要将链表头节点赋值为p的后一个节点
            head = a;
        
        //如果b不为null，证明要删除的节点不是链表头节点
        else
            //将b的后一个节点赋值为a
            b.after = a;
        
        //如果a为null，证明要删除的节点为链表尾节点
        if (a == null)
            //这里要将链表尾节点赋值为p的前一个节点
            tail = b;
            
        //如果a不为null，证明要删除的节点不是链表尾节点    
        else
            //将a的前一个节点赋值为b
            a.before = b;
    }
    
    //HashMap插入一个节点后会回调此接口
    //evict = false的话，处于创建模式
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        //声明双向链表头节点
        LinkedHashMapEntry<K,V> first;
        
        
        //只有处于创建模式且头节点不为null且removeEldestEntry接口返回true的时候
        //会删除最旧的数据
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    //HashMap调用put、replace等接口后会回调此接口
    //在LinkedHashMap中意义为将put，replace，get视为访问，每次访问结束都会将对应的
    //节点放到链表后面
    void afterNodeAccess(Node<K,V> e) { 
        //声明上一个尾节点为last
        LinkedHashMapEntry<K,V> last;
        
        //如果accessOrder为true且e不是双向链表的最后一个节点
        if (accessOrder && (last = tail) != e) {
            
            //声明当前节点p = e
            //声明当前节点b = p的前节点
            //声明当前节点a = p的后节点
            LinkedHashMapEntry<K,V> p =(LinkedHashMapEntry<K,V>)e, 
            b = p.before, a = p.after;
            
            //因为要将p加到链表最后，因此这里要将p的后一个节点置为null
            p.after = null;
            
            //如果b为null的话，证明p就是头节点
            if (b == null)
                //因此这里需要将头节点赋值为p的后节点
                head = a;
            else
                //否则将b的后节点赋值为a
                b.after = a;
            
            //如果a不为null，
            if (a != null)
                //将a的前节点赋值为b
                a.before = b;
            else
                //如果a为null，证明p就是尾节点
                //这里将last赋值为b
                last = b;
            
            //上一个尾节点为null的话，证明链表为null
            if (last == null)
                //这里将头节点赋值为p
                head = p;
            else {
                //否则将p的前节点赋值为last
                p.before = last;
                //last的后节点赋值为p
                last.after = p;
            }
            
            //将双向链表尾节点赋值为p，即将e加到了双向链表尾部
            tail = p;
            
            ++modCount; //修改次数加1
        }
    }
    //------------------------------------------------------------

    
    //内部序列化写入
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
            s.writeObject(e.key);
            s.writeObject(e.value);
        }
    }

    //构造函数
    //initialCapacity：初始容量
    //loadFactor：加载因子
    //且默认accessOrder为false
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    //构造函数
    //initialCapacity：初始容量
    //且默认accessOrder为false
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    
    //构造函
    //且默认accessOrder为false
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    
    //构造函数
    //m：要拷贝的map
    //且默认accessOrder为false
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    
    //构造函数
    //initialCapacity：初始容量
    //loadFactor：加载因子
    //accessOrder：链表顺序
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }


    //是否包含某个value
    //这里会遍历查找双向链表，因此查找的时间复杂度为O(n)
    public boolean containsValue(Object value) {
        for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
            V v = e.value;
            if (v == value || (value != null && value.equals(v)))
                return true;
        }
        return false;
    }

    //重写的get方法
    //会调用HashMap的getNode方法
    //getNode不为null且accessOrder为true的话，则将对应节点放到链表尾部
    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;
    }

    
    //重写的getOrDefault方法
    //会调用HashMap的getNode方法
    //getNode不为null且accessOrder为true的话，则将对应节点放到链表尾部
    public V getOrDefault(Object key, V defaultValue) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
   }

    //清空数据，包括头尾节点
    public void clear() {
        super.clear();
        head = tail = null;
    }

   
    //获取最旧的数据，即头节点
    public Map.Entry<K, V> eldest() {
        return head;
    }

    //LinkedHashMap默认总是返回false
    //即不删除最旧的节点，如果需要删除最旧节点，继承LinkedHashMap，
    //然后重写removeEldestEntry方法
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

    
    //获取key集合
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new LinkedKeySet();
            keySet = ks;
        }
        return ks;
    }

    //自定义KeySet
    final class LinkedKeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        
         //这里的迭代器也是LinkedHashMap自定义的迭代器
        public final Iterator<K> iterator() {
            return new LinkedKeyIterator();
        }
        public final boolean contains(Object o) { return containsKey(o); }
        
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        
        public final Spliterator<K> spliterator()  {
            return Spliterators.spliterator(this, Spliterator.SIZED |
                                            Spliterator.ORDERED |
                                            Spliterator.DISTINCT);
        }
        
        //遍历顺序：双向链表的头->尾 
        public final void forEach(Consumer<? super K> action) {
            if (action == null)
                throw new NullPointerException();
            int mc = modCount;
            
            //遍历
            for (LinkedHashMapEntry<K,V> e = head; (e != null && modCount == mc); e = e.after)
                action.accept(e.key);
             
            //证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常 
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    
    //value集合
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new LinkedValues();
            values = vs;
        }
        return vs;
    }

    //自定义value集合
    final class LinkedValues extends AbstractCollection<V> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        
        //这里的迭代器也是LinkedHashMap自定义的迭代器
        public final Iterator<V> iterator() {
            return new LinkedValueIterator();
        }
        
        public final boolean contains(Object o) { return containsValue(o); }
        public final Spliterator<V> spliterator() {
            return Spliterators.spliterator(this, Spliterator.SIZED |
                                            Spliterator.ORDERED);
        }
        
        public final void forEach(Consumer<? super V> action) {
            if (action == null)
                throw new NullPointerException();
                
            int mc = modCount;
            
            // 遍历
            for (LinkedHashMapEntry<K,V> e = head; (e != null && modCount == mc); e = e.after)
                action.accept(e.value);
            
            //证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常 
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    //所有条目集合
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }

    //自定义条目结合
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        
        //这里的迭代器也是LinkedHashMap自定义的迭代器
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }
        
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return Spliterators.spliterator(this, Spliterator.SIZED |
                                            Spliterator.ORDERED |
                                            Spliterator.DISTINCT);
        }
        
        //遍历
        public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
            if (action == null)
                throw new NullPointerException();
            int mc = modCount;
           
            for (LinkedHashMapEntry<K,V> e = head; (e != null && mc == modCount); e = e.after)
                action.accept(e);
                
            //证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常     
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    // Map overrides

    public void forEach(BiConsumer<? super K, ? super V> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        
        for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)
            action.accept(e.key, e.value);
            
        //证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常     
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }

    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        if (function == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)
            e.value = function.apply(e.key, e.value);
            
        //证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常     
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }

    
    //自定义迭代器
    abstract class LinkedHashIterator {
        //声明next节点
        LinkedHashMapEntry<K,V> next;
        //声明当前节点
        LinkedHashMapEntry<K,V> current;
        
        //预期修改次数
        //该变量用于判断当前迭代器在迭代的时候是否被修改过(例如put, remove方法)
        //若迭代时被改过，那么expectedModCount != modCount，抛出异常
        int expectedModCount;

        
        LinkedHashIterator() {
            next = head; //从双向链表头节点开始
            expectedModCount = modCount; //expectedModCount为当前总的修改次数
            current = null; //还没开始，当前节点为null
        }

        //是否还有下一个节点
        public final boolean hasNext() {
            return next != null;
        }

        //寻找下一个节点
        final LinkedHashMapEntry<K,V> nextNode() {
            //声明当前节点
            LinkedHashMapEntry<K,V> e = next;
            
            //证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
                
            //当前节点为null，抛出异常    
            if (e == null)
                throw new NoSuchElementException();
            
            //当前节点赋值
            current = e;
            //next赋值
            next = e.after;
            return e;
        }
        
        //移除当前节点
        public final void remove() {
            //声明当前节点
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            
            //证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            
            //当前节点赋值为null
            current = null;
            //删除节点
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            //删除节点后重新赋值修改次数
            expectedModCount = modCount;
        }
    }

    //key的迭代器
    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().getKey(); }
    }

    //value的迭代器
    final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }
    
    //Entry的迭代器
    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
}