LinkedHashMap的实现原理浅析

孟君

发布于 2020-04-22 16:32:51

7070

发布于 2020-04-22 16:32:51

文章被收录于专栏：孟君的编程札记孟君的编程札记

本文简单分析一下JDK1.7的LinkedHashMap源码，看一下其内部的结构以及典型方法的实现

LinkedHashMap的内部结构

查看JDK中LinkedHashMap的源码，我们发现LinkedHashMap实现了Map接口，并且其继承于HashMap，源码如下：

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

我们知道，

在HashMap中，元素的迭代顺序是无序的，不可控的

如

public class HashMapExample {

    public static void main(String[] args) {

        Map<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        map.put("Three", 3);
        map.put("Four", 4);
        map.put("Five", 5);
        map.put("Six", 6);
        map.put("Seven", 7);
        map.put("Eight", 8);
        map.put("Nine", 9);
        map.put("Ten", 10);
        
        for(Entry<String,Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

    }

}

输出结果

Six=6
Nine=9
Ten=10
Seven=7
Five=5
Three=3
One=1
Eight=8
Four=4
Two=2

其输出的结构取决于table中存的内容来处理的，在HashMap中，其数据结构基于数组+链表~ 迭代获取元素的时，其先遍历数组（table[]），table中的元素是链表，然后遍历链表，所以上述输出的结果和如下debug结果图是一致的

因为LinkedHashMap继承自HashMap，所以，如果想对HashMap有更好的了解，可以参考我之前写的博文HashMap的实现原理浅析

然后，使用LinkedHashMap来完成上述示例，看看有什么不同

public class LinkedHashMapExample {

    public static void main(String[] args) {

        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        map.put("Three", 3);
        map.put("Four", 4);
        map.put("Five", 5);
        map.put("Six", 6);
        map.put("Seven", 7);
        map.put("Eight", 8);
        map.put("Nine", 9);
        map.put("Ten", 10);
        
        for(Entry<String,Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

    }

}

输出结果

One=1
Two=2
Three=3
Four=4
Five=5
Six=6
Seven=7
Eight=8
Nine=9
Ten=10

从上述结果可以看出，输出的结果和存放的顺序是一致的，也就是说LinkedHashMap的元素是有序的

那么，LinkedHashMap是如何做的呢？

带着问题，查看LinkedHashMap的实现，我们可以看到，LinkedHashMap使用双端队列来存储元素

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

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * The head of the doubly linked list.
     */
    private transient Entry<K,V> header;

LinkedHashMap的内部类Entry

    /**
     * LinkedHashMap entry.
     */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

从上述Entry代码可以看出，

LinkedHashMap的内部类Entry继承自 HashMap.Entry<K,V>

也就是说其在HashMap.Entry<K,V> 的基础上又添加了两个属性after和before，分别表示下一个节点和前一个节点，正是这些额外的操作，才可以让LinkedHashMap变得有序

接下来，我们一起来看一些LinkedHashMap的实现

方法containsValue的实现

源代码


    /**
     * Returns <tt>true</tt> if this map maps one or more keys to the
     * specified value.
     *
     * @param value value whose presence in this map is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     */
    public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }

判断一个对象是否在LinkedHashMap中存在，查找的对象区分null和非null，两者都是以header.after作为第一个节点，然后使用节点的after属性依次判断。其中，对象为null，则直接比较null值；如果不为null，则使用equals方法来判断

方法get(Object key)的实现

源代码

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     */
    public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

LinkedHashMap的get(Object o)方法，主要调用了父类HashMap的getEntry方法

方法clear的实现

源代码

    /**
     * Removes all of the mappings from this map.
     * The map will be empty after this call returns.
     */
    public void clear() {
        super.clear();
        header.before = header.after = header;
    }

LinkedHashMap的clear方法，也调用了父类HashMap的方法，然后将header.before和header.after都指向header

LinkedHashMap中Iterator的实现

源代码

LinkedHashMap定义了一个实现Iterator<T>接口的抽象类

 private abstract class LinkedHashIterator<T> implements Iterator<T> {
        Entry<K,V> nextEntry    = header.after;
        Entry<K,V> lastReturned = null;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            return nextEntry != header;
        }

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }

从上述可以看出，迭代器使用的使用会将header.after作为下一个节点nextEntry，然后hashNext()方法通过nextEntry ！= header来判断

LinkedHashMap定义了继承抽象类LinkedHashIterator的三个内部类，KeyItertor, ValueIterator以及EntryIterator, 分别用于key值的迭代、value值的迭代以及Entry的迭代


    private class KeyIterator extends LinkedHashIterator<K> {
        public K next() { return nextEntry().getKey(); }
    }

    private class ValueIterator extends LinkedHashIterator<V> {
        public V next() { return nextEntry().value; }
    }

    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { return nextEntry(); }
    }

这些Iterator将重写父类的iterator（）方法


    // These Overrides alter the behavior of superclass view iterator() methods
    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
    Iterator<V> newValueIterator() { return new ValueIterator(); }
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

New Entry的实现

源代码

    /**
     * This override alters behavior of superclass put method. It causes newly
     * allocated entry to get inserted at the end of the linked list and
     * removes the eldest entry if appropriate.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

    /**
     * This override differs from addEntry in that it doesn't resize the
     * table or remove the eldest entry.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

addBefore方法如下：

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

因为调用addBefore传的参数为header，所以做了如下几个步骤：

新的节点next引用指向header
新的节点before引用将指向当前最后一个节点，也即headerbefore
当前最后一个节点的next引用将不在指向header，而指向当前节点
Header的before引用将指向新的节点

一个简单示例

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


public class LinkedHashMapExample {

    public static void main(String[] args) {

        Map<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "One");
        map.put(2, "Two");
        for (Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

    }

}

未添加元素之前，以及每次添加节点的debug截图如下：

accessOrder的作用

源代码


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

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * The head of the doubly linked list.
     */
    private transient Entry<K,V> header;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial
     */
    private final boolean accessOrder;

accessOrder的作用

从LinkedHashMap的源码可以发现一个属性accessOrder~ 从描述可以看出该字段用于迭代的顺序，其中：

如果accessOrder的值为true，则使用访问顺序
如果accessOrder的值为false，则使用插入顺序

该值不指定的时候，会赋值为false，也就是迭代输出的顺序为插入的顺序，这个在本文开头的示例中以有展示。如，在构造函数中赋值为false


    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the specified initial capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the specified initial capacity and a default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity
     * @throws IllegalArgumentException if the initial capacity is negative
     */
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the default initial capacity (16) and load factor (0.75).
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

当然，还有一个构造函数，可以制定accessOrder的值

    /**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
     *         access-order, <tt>false</tt> for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

接下来，我们一下来看一下accessOrder为false和为true的示例：

accessOrder为true和false的示例

public class AccessOrderExample {

    public static void main(String[] args) {

        Map<Integer, String> insertOrder = new LinkedHashMap<>(16, 0.75f, false);

        insertOrder.put(1, "a");
        insertOrder.put(3, "c");
        insertOrder.put(2, "b");
        System.out.println("insertOrder执行get方法之前的内容:" + insertOrder);
        String v = insertOrder.get(3);
        System.out.println("insertOrder执行get方法之后的内容:" + insertOrder);

        System.out.println();
        
        Map<Integer, String> accessOrder = new LinkedHashMap<>(16, 0.75f, true);
        accessOrder.put(1, "a");
        accessOrder.put(3, "c");
        accessOrder.put(2, "b");
        System.out.println("accessOrder执行get方法之前的内容:" + accessOrder);
        v = accessOrder.get(3);
        System.out.println("accessOrder执行get方法之后的内容:" + accessOrder);
    }
}

输出结果

insertOrder执行get方法之前的内容:{1=a, 3=c, 2=b}
insertOrder执行get方法之后的内容:{1=a, 3=c, 2=b}

accessOrder执行get方法之前的内容:{1=a, 3=c, 2=b}
accessOrder执行get方法之后的内容:{1=a, 2=b, 3=c}

从上述结果可以看出，如果accessOrder为true，则其使用基于访问顺序来操作，上述实例中，执行

v = accessOrder.get(3);操作之后，这个元素被加到最后，所以get操作之前和之后的链表内容发生了变化，这里使用了使用了LRU（ 最近最少被使用的调度算法)。

LinkedHashMap有序 VS. TreeMap排序

从上面的分析，我们看到LinkedHashMap通过双端链表能够保证元素的有序性，但是，有序不是排序，如果要使Map中的元素排序，则需要使用TreeMap【使用红黑树实现】

示例代码

 public static void main(String[] args) {

        Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("One", 1);
        linkedHashMap.put("One", 1);
        linkedHashMap.put("Two", 2);
        linkedHashMap.put("Three", 3);
        linkedHashMap.put("Four", 4);
        linkedHashMap.put("Five", 5);
        linkedHashMap.put("Six", 6);
        linkedHashMap.put("Seven", 7);
        linkedHashMap.put("Eight", 8);
        linkedHashMap.put("Nine", 9);
        linkedHashMap.put("Ten", 10);
        
        System.out.println("linkedHashMap内容:");
        for(Entry<String,Integer> entry : linkedHashMap.entrySet()) {
            System.out.println(entry);
        }

        System.out.println();
        
        
        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("One", 1);
        treeMap.put("One", 1);
        treeMap.put("Two", 2);
        treeMap.put("Three", 3);
        treeMap.put("Four", 4);
        treeMap.put("Five", 5);
        treeMap.put("Six", 6);
        treeMap.put("Seven", 7);
        treeMap.put("Eight", 8);
        treeMap.put("Nine", 9);
        treeMap.put("Ten", 10);
        
        System.out.println("treeMap内容:");
        for(Entry<String,Integer> entry : treeMap.entrySet()) {
            System.out.println(entry);
        }
    }

输出结果：

linkedHashMap内容:
One=1
Two=2
Three=3
Four=4
Five=5
Six=6
Seven=7
Eight=8
Nine=9
Ten=10

treeMap内容:
Eight=8
Five=5
Four=4
Nine=9
One=1
Seven=7
Six=6
Ten=10
Three=3
Two=2

从结果可以看出： LinkedHashMap输出结果和插入结果一致，保持了有序性； TreeMap输出结果是按照key值排序输出的~

上述是一个简单的LinkedHashMap的TreeMap的示例比较，TreeMap的实现细节将在后续做分析~这里就不再说明了。

夜深了，本次，源码阅读就到这里了

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自孟君的编程札记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度