LinkedHashMap底层实现原理与使用详解

LinkedHashMap就是HashMap和双向链表合二为一的结果，本篇将详解LinkedHashMap的底层实现与使用详解@mikechen

LinkedHashMap概述

LinkedHashMap继承了HashMap类，它的多种操作都是建立在HashMap操作的基础上的，只是在原来的单链表的基础上改成了双向链表。

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

这样做的目的是为了让它能够实现插入数据的排序，也就是说如果遍历整个LinkedHashMap时，是会按照插入数据的顺序来遍历数据的。

 

LinkedHashMap的特点

• 每个节点间由一个before引用 和 after 引用串联起来成为一个双向链表；
• 链表节点按照访问时间进行排序，最近访问过的链表放在链表尾；
• key和value都允许为空;
• key重复会覆盖,value可以重复;
• 有序的;
• LinkedHashMap是非线程安全的。

 

LinkedHashMap数据结构

HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap，如下图所示：

LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的，这样在查询的时候就可以通过散列表来操作，遍历的时候通过双向链表来操作。

 

LinkedHashMap使用

LinkedHashMap<String,String> hm=new LinkedHashMap<String,String>();

//创建并添加元素
hm.put("1", "mike");
hm.put("2", "chen");
hm.put("3", "hello");
hm.put("4", "world");
hm.put("5", "java");
hm.put("6", "javaee");

//遍历
Set<String> set=hm.keySet();
for(String x:set){
    String value=hm.get(x);
    System.out.println(x+"---"+value);
}

输出结果为：

1---mike
2---chen
3---hello
4---world
5---java
6---javaee

 

LinkedHashMap底层原理

1.继承结构继承结构

LinkedHashMap也就是继承HashMap,所以HashMap大都方法，它是可以直接使用的。

 

2.LinkedHashMap主要属性

//双向链表的头节点
  transient LinkedHashMap.Entry<K,V> head;
  
   //双向链表的尾节点
  transient LinkedHashMap.Entry<K,V> tail;

 //排序的规则，false按插入顺序排序，true访问顺序排序 
  final boolean accessOrder;
  
  //所以说accessOrder的作用就是控制访问顺序，设置为true后每次访问一个元素，就将该元素所在的Node变成最后一个节点，
  改变该元素在LinkedHashMap中的存储顺序。

 

3.LinkedHashMap构造函数

LinkedHashMap有五个构造器:

//用默认的初始容量和负载因子构建一个LinkedHashMap,取出键值对的方式是插入顺序
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    //构造一个指定初始容量的LinkedHashMap,取得键值对的顺序
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    //构造一个指定初始容量和负载因子,按照插入顺序的LinkedHashMap
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    //根据给定的初始容量,负载因子和键值对迭代顺序构建一个LinkedHashMap
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

    //通过给定的map创建一个LinkedHashMap,负载因子是默认值,迭代方式是插入顺序.
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

从构造方法可以看出,默认都是采用插入顺序来维持取出键值对的次序.所有的构造方法都是通过父类的构造方法来建造对象的。

 

4.LinkedHashMap Entry

LinkedHashMap和HashMap的区别在于他们的基本数据机构上,我们来看一下LinkedHashMap的基本数据结构Entry，这个比较重要：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    //定义Entry类型的两个变量，或者称之为前后的两个指针    
    Entry<K,V> before, after;
    //构造方法与HashMap的没有区别，也是调用父类的Entry构造方法
    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
    }

    //删除
    private void remove() {
        before.after = after;
        after.before = before;
    }

    //插入节点到指定的节点之前
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }

    //方法重写，HashMap中为空
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }
    //方法重写 ，HashMap中方法为空
    void recordRemoval(HashMap<K,V> m) {
        remove();
    }
}

到这里已经可以知道，相对比HashMap，LinkedHashMap内部不光是使用HashMap中的哈希表来存储Entry对象。

另外维护了一个LinkedHashMapEntry，这些LinkedHashMapEntry内部又保存了前驱跟后继的引用，可以确定这是个双向链表。

而这个LinkedHashMapEntry提供了对象的增加删除方法都是去更改节点的前驱后继指向。

 

5.put()/get()方法

在LinkedHashMap类使用的仍然是父类HashMap的put方法，所以插入节点对象的流程基本一致。

不同的是，LinkedHashMap重写了afterNodeInsertion和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;
}

afterNodeInsertion方法用于移除链表中的最旧的节点对象，也就是链表头部的对象。

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

afterNodeAccess方法实现的逻辑，是把入参的节点放置在链表的尾部。

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总结

LinkedHashMap 内部包含一个双向链表维护顺序，支持两种顺序——添加顺序，访问顺序。

默认就是按照添加顺序来的，如果要改成访问顺序的话，构造方法中的 accessOrder 需要设置成 true。这样，每次调用 get 方法，就会将刚刚访问的元素更新到链表尾部。

作者简介

陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号，获取更多技术干货！

后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》