Java 8 容器源码-LinkedHashMap

扫码关注公众号:Java 技术驿站

发送:vip
将链接复制到本浏览器,永久解锁本站全部文章

【公众号:Java 技术驿站】 【加作者微信交流技术,拉技术群】

作者:潘威威 出处:https://blog.csdn.net/panweiwei1994


LinkedHashMap继承了HashMap,是Map接口的哈希表和链接列表实现。哈希表的功能通过继承HashMap实现了。LinkedHashMap还维护着一个双重链接链表。此链表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。本文主要讲解双重链接链表的部分,看看它是如何实现有序性的。

数据结构

在分析LinkedHashMap源码之前,有必要了解LinkedHashMap的数据结构,否则很难理解下面的内容。

MarkdownPhotos/master/CSDNBlogs/container/LinkedHashMap/LinkedHashMapDateStructure.jpg

从上图中可以很清楚的看到,HashMap的数据结构是数组+链表+红黑树(since JDK1.8)+ 双重链接列表。数组+链表+红黑树的部分请参考HashMap源码一文中关于数据结构的讲解,HashMap和LinkedHashMap在这部分的实现是几乎相同的。LinkedHashMap为每个Entry添加了前驱和后继,构成了一个双向循环链表,每次向linkedHashMap插入键值对,除了将其插入到哈希表的对应位置之外,还要将其插入到双向循环链表的尾部。

部分顶部注释

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)

大意为LinkedHashMap是Map的哈希表和链接列表的实现,具有可预知的迭代顺序。LinkedHashMap和HashMap的不同之处在于它包含一个贯穿于所有entry的双重链接列表。双重链接列表定义了迭代顺序,默认是插入顺序。值得注意的是,如果一个key被重插入,插入顺序不受影响。

层次结构图

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

从中我们可以了解到:

  • LinkedHashMap<K,V>:HashMap是以key-value形式存储数据的
  • extends HashMap<K,V>:继承了HashMap,哈希表部分的功能和HashMap相似。
  • implements Map<K,V>:实现了Map。HashMap已经继承了Map接口,为什么LinkedHashMap还要实现Map接口呢? 仔细看过Java容器其他源码的朋友会发现,不仅仅LinkedHashMap这样做,其他实现类也经常这样做。网上的一些看法是这样做可以直观地表达出LinkedHashMap实现了Map。如果大家有其他看法,欢迎留言。

说到直观地展示出一个类的继承实现结构,eclipse的类层次结构图就可以实现这个功能。下图是LinkedHashMap类结构层次图

MarkdownPhotos/master/CSDNBlogs/container/LinkedHashMap/LinkedHashMapTH.jpg

    /**
     * 双向循环链表的头结点
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 双向循环链表的尾结点
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * 迭代顺序。
     * true代表按访问顺序迭代
     * false代表按插入顺序迭代
     *
     * @serial
     */
    final boolean accessOrder;

这里有必要看下LinkedHashMap的Entry的定义。LinkedHashMap的Entry继承了HashMap的Node,并且每个entry都包含前指针和后指针,这是双向循环链表的特点。

    /**
     * LinkedHashMap的Entry继承了HashMap的Node
     */
    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);
        }
    }

私有方法

linkNodeLast( LinkedHashMap.Entry<K,V> p)

    /**
     * 将指定entry插入到双向链表末尾
     */
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        //尾指针执行p
        tail = p;
        //如果旧的尾节点指向null,意味着双向循环链表为空,这时头尾指针都要指向p
        if (last == null)
            head = p;
        else {//否则将p插入到旧尾节点的后面
            p.before = last;
            last.after = p;
        }
    }

transferLinks( LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst)

    // 将src替换为dst
    private void transferLinks(LinkedHashMap.Entry<K,V> src,
                               LinkedHashMap.Entry<K,V> dst) {
        LinkedHashMap.Entry<K,V> b = dst.before = src.before;
        LinkedHashMap.Entry<K,V> a = dst.after = src.after;
        //如果src的前指针指向null,说明src为头节点,这时将dst替换为头节点即可
        if (b == null)
            head = dst;
        else//否则,将dst的前指针指向的节点的后指针指向dst
            b.after = dst;
        //如果src的后指针指向null,说明src为尾节点,这时将dst替换为尾节点即可
        if (a == null)
            tail = dst;
        else//否则,将dst的后指针指向的节点的前指针指向dst
            a.before = dst;
    }

重写HashMap的方法

reinitialize()

    //将linkedHashMap重置到初始化的默认状态
    void reinitialize() {
        //重置哈希表
        super.reinitialize();
        //重置双向循环链表
        head = tail = null;
    }

newNode( int hash, K key, V value, Node<K,V> e)

    /**
     * 创建一个普通entry,将entry插入到双向循环链表的末尾,最后返回entry
     */
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        //创建一个entry
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        //将entry插入到双向循环链表的末尾
        linkNodeLast(p);
        //返回entry
        return p;
    }

replacementNode( Node<K,V> p, Node<K,V> next)

    /**
     * 替换普通节点
     */
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        LinkedHashMap.Entry<K,V> t =
            new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

newTreeNode( int hash, K key, V value, Node<K,V> next)

    /**
     * 创建一个树的entry,将entry插入到双向循环链表的末尾,最后返回entry
     */
    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);
        linkNodeLast(p);
        return p;
    }

replacementTreeNode( Node<K,V> p, Node<K,V> next)

    /**
     * 替换树节点
     */
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

afterNodeRemoval( Node<K,V> e)

    /**
     * 保证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;
    }

这个方法是用来在LinkedHashMap的哈希表中删除一个键值对后同时将键值对从双向循环链表中删除,保证哈希表和双向循环链表的一致性。

如果你有仔细看过HashMap的源码,你就会发现源码里有这么三个空方法:

  • void afterNodeAccess(Node<K,V> p) { }
  • void afterNodeInsertion(boolean evict) { }
  • void afterNodeRemoval(Node<K,V> p) { }

你当时有没有疑问,这三个方法方法体为空,为什么存在?这三个方法表示在访问、插入、删除某个节点之后,进行一些处理,它们在LinkedHashMap都有重写。LinkedHashMap正是通过重写这三个方法来保证链表的插入、删除的有序性。

afterNodeInsertion( boolean evict)

    /**
     * 可能把头节点删除
     */
    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);
        }
    }

从代码中可以看出,如果evict && (first = head) != null && removeEldestEntry(first)条件为true,将删除头节点。看下removeEldestEntry方法的实现,发现永远返回false。

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

这意味着afterNodeInsertion这个方法什么都做不了。那这个方法有什么用?

如果重写removeEldestEntry方法,就能定义是否删除的规则,afterNodeInsertion就有用了。对removeEldestEntry方法的详细解释请往下看。

afterNodeAccess( Node<K,V> e)

    /**
     * 若迭代顺序为true,且指定参数节点e不是尾结点,把指定参数节点e移到末尾
     */
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        //若迭代顺序为true,且指定参数节点e不是尾结点
        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;
        }
    }

internalWriteEntries( java.io.ObjectOutputStream s)

    /**
     * 写入键值对到ObjectOutputStream中
     */
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
            s.writeObject(e.key);
            s.writeObject(e.value);
        }
    }

构造方法

LinkedHashMap有五种构造方法:

  • LinkedHashMap( int initialCapacity, float loadFactor)。使用指定的初始化容量initial capacity 和负载因子load factor构造一个空LinkedHashMap。
  • LinkedHashMap( int initialCapacity)。使用指定的初始化容量initial capacity和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空LinkedHashMap。
  • LinkedHashMap()。使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空HashMap。
  • LinkedHashMap(Map<? extends K, ? extends V> m)。使用指定Map m构造新的LinkedHashMap。使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)。
  • LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)。使用指定的初始化容量initial capacity 和负载因子load factor和迭代顺序accessOrder构造一个空LinkedHashMap。

LinkedHashMap( int initialCapacity, float loadFactor)

    /**
     * 使用指定的初始化容量initial capacity 和负载因子load factor构造一个空LinkedHashMap
     *
     * @param  initialCapacity 初始化容量
     * @param  loadFactor      负载因子
     * @throws IllegalArgumentException 如果指定的初始化容量为负数或者加载因子为非正数。
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        //默认迭代顺序为插入顺序
        accessOrder = false;
    }

LinkedHashMap( int initialCapacity)

    /**
     * 使用指定的初始化容量initial capacity和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空LinkedHashMap
     *
     * @param  initialCapacity 初始化容量
     * @throws IllegalArgumentException 如果指定的初始化容量为负数
     */
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        //默认迭代顺序为插入顺序
        accessOrder = false;
    }

LinkedHashMap()

    /**
     * 使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空HashMap
     */
    public LinkedHashMap() {
        super();
        //默认迭代顺序为插入顺序
        accessOrder = false;
    }

LinkedHashMap( Map<? extends K, ? extends V> m)

    /**
     * 使用指定Map m构造新的LinkedHashMap。使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)
     * @param   m 指定的map
     * @throws  NullPointerException 如果指定的map是null
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        //默认迭代顺序为插入顺序
        accessOrder = false;
        putMapEntries(m, false);
    }

LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)

    /**
     * 使用指定的初始化容量initial capacity 和负载因子load factor和迭代顺序accessOrder构造一个空LinkedHashMap
     *
     * @param  initialCapacity 初始化容量
     * @param  loadFactor      负载因子
     * @param  accessOrder    迭代顺序
     *
     * @throws IllegalArgumentException 如果指定的初始化容量为负数或者加载因子为非正数。
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        //默认迭代顺序为插入顺序
        this.accessOrder = accessOrder;
    }

常用方法

containsValue( Object value)

    /**
     * 如果linkedHashMap中的键值对有一对或多对的value为参数value,返回true
     *
     * @param value 参数value
     * @return 如果linkedHashMap中的键值对有一对或多对的value为参数value,返回true
     */
    public boolean containsValue(Object value) {
        //遍历双向循环链表,如果有一对或多对的键值对value为参数value,返回true
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
            V v = e.value;
            if (v == value || (value != null && value.equals(v)))
                return true;
        }
        //否则返回false
        return false;
    }

get( Object key)

    /**
     * 返回指定的key对应的entry的value,如果entry为null或者value为null,则返回null
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        Node<K,V> e;
        //如果key对应的entry为null,返回null
        if ((e = getNode(hash(key), key)) == null)
            return null;
        //如果迭代顺序为按访问顺序迭代
        if (accessOrder)
            //将e插入双向链表末尾
            afterNodeAccess(e);
        //返回value
        return e.value;
    }

getOrDefault( Object key, V defaultValue)

    /**
     * 通过key映射到对应entry,如果没映射到则返回默认值defaultValue
     *
     * @return key映射到对应的entry,如果没映射到则返回默认值defaultValue
     */
    public V getOrDefault(Object key, V defaultValue) {
       Node<K,V> e;
       //如果key对应的entry为null,返回defaultValue
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;
       //如果迭代顺序为按访问顺序迭代
       if (accessOrder)
            //将e插入双向链表末尾
           afterNodeAccess(e);
        //返回value
       return e.value;
    }

clear()

    /**
     * 清空linkedHashMap。
     */
    public void clear() {
        //清空哈希表
        super.clear();
        //清空双向循环链表
        head = tail = null;
    }

removeEldestEntry( Map.Entry<K,V> eldest)

    /**
     * 如果map应该删除头节点,返回true
     *
     * 这个方法在被put和putAll方法被调用,当向map中插入一个新的entry时被执行。
     *
     * 这个方法提供了当一个新的entry被添加到linkedHashMap中,删除头节点的机会。
     *
     * 这个方法是很有用的,可以通过删除头节点来减少内存消耗,避免溢出。
     *
     * 简单的例子:这个方法的重写将map的最大值设为100,到100时,每次增一个entry,就删除一次头节点。
     *
     *     private static final int MAX_ENTRIES = 100;
     *
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
     *        return size() > MAX_ENTRIES;//当map大小大于100时,返回true。意为允许删除头节点
     *     }
     *
     * 这个方法一般不会直接修改map,而是通过返回true或者false来控制是否修改map。
     *
     * 这个方法仅仅返回false,这样头节点就永远都不会被删除了。
     *
     * @param    eldest 头节点
     * @return   如果map应该删除头节点就返回true,否则返回false
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

keySet()

    /**
     * 返回linkedHashMap中所有key的视图。
     * 改变linkedHashMap会影响到set,反之亦然。
     * 如果当迭代器迭代set时,linkedHashMap被修改(除非是迭代器自己的remove()方法),迭代器的结果是不确定的。
     * set支持元素的删除,通过Iterator.remove、Set.remove、removeAll、retainAll、clear操作删除hashMap中对应的键值对。不支持add和addAll方法。
     *
     * @return 返回linkedHashMap中所有key的set视图
     */
    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()

    /**
     * 返回linkedHashMap中所有value的collection视图
     * 改变linkedHashMap会改变collection,反之亦然。
     * 如果当迭代器迭代collection时,linkedHashMap被修改(除非是迭代器自己的remove()方法),迭代器的结果是不确定的。
     * collection支持元素的删除,通过Iterator.remove、Collection.remove、removeAll、retainAll、clear操作删除linkedHashMap中对应的键值对。不支持add和addAll方法。
     *
     * @return 返回linkedHashMap中所有key的collection视图
     */
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new LinkedValues();
            values = vs;
        }
        return vs;
    }

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

entrySet()

    /**
     * 返回hashMap中所有键值对的set视图
     * 改变hashMap会影响到set,反之亦然。
     * 如果当迭代器迭代set时,hashMap被修改(除非是迭代器自己的remove()方法),迭代器的结果是不确定的。
     * set支持元素的删除,通过Iterator.remove、Set.remove、removeAll、retainAll、clear操作删除hashMap中对应的键值对。不支持add和addAll方法。
     *
     * @return 返回hashMap中所有键值对的set视图
     */
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }

LinkedHashMap到这里就看完了,LinkedHashMap和HashMap确实很相似,HashMap的特性LinkedHashMap都有,LinkedHashMap中的操作基本上都是为了维护具有访问顺序的双向循环链表。

总结

HashMap与LinkedHashMap比较

不同点

不同点 HashMap LinkedHashMap
数据结构 数组+链表+红黑树 数组+链表+红黑树+双向循环链表
是否有序 无序 有序

相同点

  • 都是基于哈希表的实现。
  • 存储的是键值对映射。
  • 都继承了AbstractMap,实现了Map、Cloneable、Serializable。
  • 它们的构造函数都一样。
  • 默认的容量大小是16,默认的加载因子是0.75。
  • 都允许key和value为null。
  • 都是线程不安全的。
赞(1) 打赏
版权归原创作者所有,任何形式的转载请联系博主:daming_90:Java 技术驿站 » Java 8 容器源码-LinkedHashMap

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏