LinkedHashMap源码解析

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

![在这里插入图片描述](https://img-blog.csdnimg.cn/20190413100631395.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly94aW5kb28uYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70 =400x)
  从类图其实可以看出来,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());
        }
    }

它不仅仅能保持插入顺序,也可以看元素是否访问调整顺序,下面代码和上面代码的区别是多了构造函数和一个元素的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());
        }
    }

实现

![在这里插入图片描述](https://img-blog.csdnimg.cn/20190413100631395.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly94aW5kb28uYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70 =400x)
  从类图其实可以看出来,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;
    }

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);
        }
    }

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) { }

  如果你之前看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;
        }
    }

  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();
        }
    }

   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;
    }
}
打赏

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.