Java LinkedHashMap 实现原理¶

更新日期 2020-5-25

2020-5-25 创建

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。

vo vo vo

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

     } vo

href="#__codelineno-7-1">// Callbacks to allow LinkedHashMap post-actions id afterNodeAccess(Node<K,V> p) { } id afterNodeInsertion(boolean evict) { } id afterNodeRemoval(Node<K,V> p) { } ”的节点。 href="#__codelineno-8-1">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); } span> id 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

本站说明

一起在知识的海洋里呛水吧。广告内容与本站无关。如果喜欢本站内容，欢迎投喂作者，谢谢支持服务器。如有疑问和建议，欢迎在下方评论~

📖AndroidTutorial 📚AndroidTutorial 🙋反馈问题 🔥最近更新 🍪投喂作者

Ads