LinkedHashMap深度解析

概述

在平时开发的过程中，大部分都是使用HashMap存储key value结构的数据，但是它是没有顺序的，如果你想要一个有顺序的Map，这时候LinkedHashMap就闪亮登场, 本篇文章主要基于jdk1.8学习下LinkedHashMap的功能和原理。在学习LinkedHashMap你需要对HashMap底层实现和源码有一定了解。

介绍

LinkedHashMap是一个有顺序的Hash表，它可以是元素插入顺序或者访问顺序。

• LinkedHashMap最大的特点是有顺序的
• LinkedHashMap的key 和value都可以为空
• LinkedHashMap不是线程安全

以上是LinkedHashMap的类结构图:

• 继承了HashMap，在HashMap的功能基础上，增加了访问顺序的能力

使用案例

LinkedHashMap基于插入顺序

@Test
    public void test1() {
        // 创建默认的 LinkedHashMap
        Map<String, String> map = new LinkedHashMap<>();
        // 插入
        map.put("1", "1");
        map.put("2", "2");
        map.put("5", "5");
        map.put("4", "4");
        System.out.println(map);

        // 访问
        map.get("2");
        map.get("1");

        System.out.println(map);
    }

运行结果：

小结：

1. 默认LinkedHashMap是维护插入顺序，访问不会改变顺序

LinkedHashMap基于插入顺序和访问顺序

@Test
    public void test2() {
        // 创建 LinkedHashMap, accessOrder设置为true
        Map<String, String> map = new LinkedHashMap<String, String>(16, 0.75f, true);
        // 插入
        map.put("1", "1");
        map.put("2", "2");
        map.put("5", "5");
        map.put("4", "4");
        System.out.println(map);

        // 访问
        map.get("2");
        map.get("1");

        System.out.println(map);
    }

运行结果：

小结：

1. 通过3个参数的构造函数可以创建出基于插入顺序+访问顺序的LinkedHashMap

核心机制

实现机制

LinkedHashMap继承了HashMap, 那么它也就拥有了HashMap的一些机制，包括扩容机制、转换成红黑树等都是一样的逻辑，但是LinkedHashMap拥有了一个更强的能力，就是有顺序，那么它是怎么维护节点的顺序呢？

LinkedHashMap额外维护了一个双向链表，在在每次插入数据，或者访问、修改数据时，会对这个双向链表增加节点、或调整链表的节点顺序，从而保证这个有序性。

源码解析

成员变量

通过成员变量我们看出LinkedHashMap底层的数据结构。

// 双向链表的头部节点（最早插入的，年纪最大的节点）
transient LinkedHashMap.Entry<K,V> head;

// 双向链表的尾部节点（最新插入的，年纪最小的节点）
transient LinkedHashMap.Entry<K,V> tail;

// 用于控制访问顺序，为true时，按插入顺序；为false时，按访问顺序
final boolean accessOrder;

LinkedHashMap继承自HashMap，所以内部存储数据的方式和HashMap一样，使用数组加链表（红黑树）的结构存储数据，LinkedHashMap和HashMap相比，额外的维护了一个双向链表，用于存储节点的顺序。这个双向链表的类型为LinkedHashMap.Entry：

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多个一个accessOrder, 用于控制访问顺序。

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

只有这个构造函数可以通过参数修改accessOrder。

当accessOrder属性为true时，元素按访问顺序排列，即最近访问的元素会被移动到双向列表的末尾。所谓的“访问”并不是只有get方法，符合“访问”一词的操作有put、putIfAbsent、get、getOrDefault、compute、computeIfAbsent、computeIfPresent和merge方法。

关键方法

put方法

LinkedHashMap并没有put方法，而是使用的父类HashMap的put方法，那么它是怎么做到维护链表的呢？答案就是重写，HashMap提供了一些可以重写的入口。关于HashMap的源码这里就不详细分析了。

put方法最后是调到HashMap#putVal。

newNode方法用于创建链表节点，LinkedHashMap重写了newNode方法：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        // 创建LinkedHashMap.Entry实例
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
         // 将新节点放入LinkedHashMap维护的双向链表尾部
        linkNodeLast(p);
        return p;
    }

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // 如果尾节点为空，说明双向链表是空的，所以将该节点赋值给头节点，双向链表得以初始化
    if (last == null)
        head = p;
    else {
        // 否则将该节点放到双向链表的尾部
        p.before = last;
        last.after = p;
    }
}

所以可以看到，在put方法的时候调用newNode方法，LinkedHashMap会维护这个双向链表。

LinkedHashMap也重写了afterNodeAccess方法，顾名思义，就是当节点被访问后执行某些操作。

void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        // 如果accessOrder属性为true，并且当前节点不是双向链表的尾节点的话执行if内逻辑
        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也重写了afterNodeInsertion方法，执行节点插入成功后的逻辑：

 void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        // 如果头部节点不为空并且removeEldestEntry方法返回true的话
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            // 获取头部节点的key
            K key = first.key;
             // 调用父类HashMap的removeNode方法，删除这个key的节点，也就是第一个节点
            removeNode(hash(key), key, null, false, true);
        }
    }

get方法

LinkedHashMap重写了HashMap的get方法，逻辑如下：

 public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        // 当accessOrder属性为true时，将key对应的键值对节点移动到双向列表的尾部
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

这里的afterNodeAccess方法上面讲过了，用来节点访问时候的回调，需要通过构造方法设置accessOrder的属性为true才会生效。

remove方法

LinkedHashMap没有重写remove方法，查看HashMap的remove相关方法发现如下：

LinkedHashMap重写了这个afterNodeRemoval方法：

// 逻辑简单，改变节点的前继后继引用
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的双向链表中删除对应的节点。

总结

本文主要分析了LinkedHashMap的有序性的这一特性，从源码层面理解它是如何保证有序的，但是前提希望大家能够对HashMap的实现或者源码有一定的基础，你才能够更好的理解LinkedHashMap。

参考

segmentfault.com/a/119000001…

blog.csdn.net/zxt0601/art…

juejin.cn/post/684490…

mrbird.cc/LinkedHashM…

\