LinkedHashMap源码解析

相信即便是Java初学者都应该用过Java中的HashMap和TreeMap，但貌似大多数人都没怎么用过LinkedHashMap，对其知之甚少。因为基本上大多数情况下TreeMap和HashMap都能满足需求，只有在需要map中K-V保持一定顺序时才会用到LinkedHashMap。所以保序是LinkedHashMap较HashMap和TreeMap最大的特点，至于保什么序后面会详细讲解。

　　从类图其实可以看出来，LinkedHashMap其实是完全继承于HashMap的，甚至好多地方干脆复用了HashMap的源码。其实可以认为HashMap的功能是LinkedHashMap的子集，HashMap可以做的LinkedHashMap都可以做。

如何使用

其使用方式和HashMap一致，但默认是能保持插入顺序的，所以使用Iterator比例keySet或者entrySet时可以得到和插入顺序一致的结果。

    public static void main(String[] args) {
        Map<Integer, Integer> map = new LinkedHashMap<>();
        map.put(4,2);
        map.put(2,4);
        map.put(3,5);
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

它不仅仅能保持插入顺序，也可以看元素是否访问调整顺序，下面代码和上面代码的区别是多了构造函数和一个元素的get。但迭代的结果完全不同。LinkedHashMap对访问调序的支持为简单实现LRUCache奠定了基础。

    public static void main(String[] args) {
        Map<Integer, Integer> map = new LinkedHashMap<>(8, (float)0.75, true);
        map.put(4,2);
        map.put(2,4);
        map.put(3,5);
        map.get(4);
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

实现

　　从类图其实可以看出来，LinkedHashMap其实是完全继承于HashMap的，甚至好多地方干脆复用了HashMap的源码。其实可以认为HashMap的功能是LinkedHashMap的子集，HashMap可以做的LinkedHashMap都可以做。
　　其实说白了，LinkedHashMap其实就是在HashMap+链表，就是用双链表把HashMap中的每个Node串起来，可以看如下示意图，黄色线条代表链表中的关系，主体结构还是HashMap中的结构，关于HashMap可以看我另一篇博客Java HashMap源码浅析 。所以较HashMap的源码，LinkedHashMap就是多加了一些双链表的操作（插入、删除、节点挪动到尾部……）。

源码

初始化

　　LinkedHashMap的构造函数和HashMap的差不多类似，但多出来上图中的最后一个，其中参数多了一个boolean 类型的accessOrder，这个其实是否在节点被访问和变更后将其移动到双向链表的末尾，这也是文章最后实现LRUCache的关键参数。

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

Entry

Entry继承自HashMap.Node<K,V>，就是在HashMap.Node<K,V>的基础上只添加了双向链表的前后指针，代码很简单如下。

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

put & get & resize & removeNode

其实LinkedHashMap中没有自己的put & get & resize & removeNode方法，完全是继承了HashMap中的方法。那肯定你也会好奇，LinkedHashMap中肯定每次增删改查总是会涉及到对双链表的操作，这是如何实现的？这个时候我们需要回到HashMap的源码中去。

    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

  

 

  
1
  
2
  
3
  
4
 

如果你之前看HashMap的代码，你可能注意到了这三个没有实现的方法，你可能会很好奇他们有什么用。这三个方法在HashMap的各种操作中被用到了，看名字和注释也能看出来是在节点操作后做一些工作。可惜在HashMap中没用，你不看LinkedHashMap的源码肯定会感到莫名其妙的。

    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<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;
    }

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

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

afterNodeRemoval()就是在Map中元素被移除后也移除双链表中相应的元素。 afterNodeInsertion()就是额外在双链表尾部插入新元素。但afterNodeAccess()就比较奇怪了，它是把某个元素挪动到队列的尾部，这有啥用？
　　afterNodeAccess分别在putVal、merge、replace……总之所有有变动的地方调用，这以为着map中最新变动的值肯定是会在链表尾部，相反最旧的就在头部了（需要在构造函数中开启accessOrder）。
　　在afterNodeInsertion()中我们还看到了removeEldestEntry(first)，就是在插入新元素后移除最老的元素。 LinkedHashMap中默认是false，也就是不移除。如果我们继承了LinkedHashMap并对其重载，然后结合afterNodeAccess，就可以对最近最久未访问的元素做清理，不就是有个LRUCache了吗。

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

### LinkedHashMap如何实现遍历时的保序 
 
　　开头说过，LinkedHashMap和HashMap最大的一个区别就是前者能实现遍历的保序。可以按插入顺序或者最久访问顺序遍历，如何实现的？其实看下keySet() values() entrySet()这几个key value k-v遍历方法就知道了。HashMap中无法保存顺序信息，但双链表可以啊，所以为了获取顺序信息，它们不是HashMap中从map中获取数据，而是从双向链表中获取。  
```java
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new LinkedKeySet();
            keySet = ks;
        }
        return ks;
    }

    final class LinkedKeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        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 (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
                action.accept(e.key);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
 

values() entrySet()方法实现类似，就不全贴了。

LRUCache

上文提到多次LRUCache，其中LRU是Least Recently Used的缩写，其实就是想在有限的存储空间里保留更多有价值数据的一种方式。其实现的依旧就是最佳被使用的数据将来还被使用的概率更高，这个现象在计算机领域非常明显，很多优化就是基于此的。LRUCache就是这样一种存储的实现，它的难点就在于如何高效地剔除掉最旧的数据，以及如何维护数据的新旧度。
　　有了LinkedHashMap后，我们就可以很简单的实现一个LRUCache。依赖Linked和HashMap的结合，查询时可以从HashMap中以O(1)的时间复杂度查询，数据过期也可以用O(1)的时间复杂度从Linked中删除。LRUCache就是HashMap和Linked二者完美结合的体现。
　　一个LRUCache的完整代码如下，没错 是完整的代码，就是这么简单，主要的逻辑LinkedHashMap里都已经帮你实现了，你只需要稍微封装下就可以了。其实只需要重载下HashMap中的removeEldestEntry()方法就行，这个方法会在新节点插入或者旧节点访问后被调用。

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K,V> extends LinkedHashMap<K,V> {
    private int maxCap;
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > this.maxCap;
    }
    public LRUCache(int capacity) {
        super(capacity, (float)0.75, true);
        this.maxCap = capacity;
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/89278264