Skip to content

Java LinkedHashMap 实现原理

LinkedHashMap 概述

HashMap 是无序的,HashMap 在 put 的时候是根据 key 的 hashcode 进行 hash 然后放入对应的地方。所以在按照一定顺序 put 进 HashMap 中,然后遍历出 HashMap 的顺序跟 put 的顺序不同(除非在 put 的时候 key 已经按照 hashcode 排序号了,这种几率非常小)

JAVA 在 JDK1.4 以后提供了 LinkedHashMap 来帮助我们实现了有序的 HashMap! LinkedHashMap 是 HashMap 的一个子类,它保留插入的顺序,如果需要输出的顺序和输入时的相同,那么就选用 LinkedHashMap。

LinkedHashMap 是 Map 接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

LinkedHashMap 实现与 HashMap 的不同之处在于,LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。 注意,此实现不是同步的。如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步。 根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用 get 方法)的链表。默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。

LinkedHashMap的使用

我在最开始学习 LinkedHashMap 的时候,看到访问顺序、插入顺序等等,有点晕了,随着后续的学习才慢慢懂得其中原理,所以我会先在进行做几个 demo 来演示一下 LinkedHashMap 的使用。看懂了其效果,然后再来研究其原理。

HashMap

看下面这个代码:

public static void main(String[] args) {
    Map<String, String> map = new HashMap<String, String>();
    map.put("apple", "苹果");
    map.put("watermelon", "西瓜");
    map.put("banana", "香蕉");
    map.put("peach", "桃子");

    Iterator iter = map.entrySet().iterator();
    while (iter.hasNext()) {
        Map.Entry entry = (Map.Entry) iter.next();
        System.out.println(entry.getKey() + "=" + entry.getValue());
    }
}

一个比较简单的测试 HashMap 的代码,通过控制台的输出,我们可以看到 HashMap 是没有顺序的。

banana=香蕉
apple=苹果
peach=桃子
watermelon=西瓜

LinkedHashMap

使用LinkedHashMap,在构造函数中指定accessOrder为false。即按插入顺序排序。

Map<String, String> map = new LinkedHashMap<>(16, 0.75f, false);
map.put("one", "1");
map.put("two", "2");
map.put("three", "3");
map.put("four", "4");

map.get("three");
map.get("one");

Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
    Map.Entry entry = (Map.Entry) iter.next();
    System.out.print("{" + entry.getKey() + " : " + entry.getValue() + "}  ");
}
// {one : 1}  {two : 2}  {three : 3}  {four : 4} 

我们可以看到,其输出顺序是完成按照插入顺序的!也就是我们上面所说的保留了插入的顺序。

按访问顺序进行排序。在构造函数中指定accessOrder为true。

    Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
    map.put("one", "1");
    map.put("two", "2");
    map.put("three", "3");
    map.put("four", "4");

    map.get("three");
    map.get("one");

    Iterator iter = map.entrySet().iterator();
    while (iter.hasNext()) {
        Map.Entry entry = (Map.Entry) iter.next();
        System.out.print("{" + entry.getKey() + " : " + entry.getValue() + "}  ");
    } 

上面的代码中最后访问的是”one”,输出结果:

{two : 2}  {four : 4}  {three : 3}  {one : 1}  

这也就是我们之前提到过的,LinkedHashMap 可以选择按照访问顺序进行排序。

LinkedHashMap 的实现

源码来自JDK1.8

对于 LinkedHashMap 而言,它继承与 HashMap(public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>)、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类 HashMap 相似,它通过重写父类相关的方法,来实现自己的链接列表特性。下面我们来分析 LinkedHashMap 的源代码:

成员变量

LinkedHashMap 采用的 hash 算法和 HashMap 相同,但是它重新定义了数组中保存的元素 Entry,该 Entry 除了保存当前对象的引用外,还保存了其上一个元素 before 和下一个元素 after 的引用,从而在哈希表的基础上又构成了双向链接列表。看源代码:

/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*/
final boolean accessOrder; // 如果为true,则按照访问顺序;如果为false,则按照插入顺序。

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
transient LinkedHashMap.Entry<K,V> tail;

/**
* LinkedHashMap的Entry静态内部类。
* 继承HashMap的Node元素,其中保存了其上一个元素before和下一个元素after的引用。
 */
    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);
        }
    }

LinkedHashMap 中的 Entry 继承了 HashMap中的 Node,但是其增加了 before 和 after 的引用,指的是上一个元素和下一个元素的引用。

初始化

通过源代码可以看出,在 LinkedHashMap 的构造方法中,实际调用了父类 HashMap 的相关构造方法来构造一个底层存放的 table 数组,但额外可以增加 accessOrder 这个参数,如果不设置,默认为 false,代表按照插入顺序进行迭代;当然可以显式设置为 true,代表以访问顺序进行迭代。如:

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

存储

LinkedHashMap 并未重写父类 HashMap 的 put 方法。 HashMap中提供了3个方法给LinkedHashMap。

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

afterNodeRemoval是把节点从链表中删去。 LinkedHashMap重写了afterNodeInsertion方法。插入新节点后,有可能会删掉“最老”的节点。 afterNodeAccess方法则是把新插入的节点移到队尾。

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

读取

LinkedHashMap 重写了父类 HashMap 的 get 方法,实际在调用父类getNode() 方法取得查找的元素后,如果 accessOrder 为 true 时,执行afterNodeAccess方法。由于的链表的增加、删除操作是常量级的,对性能影响小。

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

排序模式

LinkedHashMap boolean变量 accessOrder。True按访问顺序排序;为 false按插入顺序。默认为false。

该哈希映射的迭代顺序就是最后访问其条目的顺序,这种映射很适合构建 LRU 缓存。Android中提供了基于LinkedHashMap 构建的 LRU 缓存类 LRUCache。

总结

其实 LinkedHashMap 几乎和 HashMap 一样。它的节点类实现了双向链表,可以支持按插入顺序或访问顺序排序的操作。

参考

  • http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html