转载

解读java集合框架源码-LinkedHashMap

LinkedHashMap，通过hash表和链表实现。保持迭代有序，与HashMap不同的是，其内部维护了一个双向链表，该链表贯穿了所有元素。

这个列表定义了迭代排序，通常是键插入的顺序（insertion-order）。需要注意的是，在insertion-order时，一个键重复插入时，顺序不会受影响。

JDK注释

解读java集合框架源码-LinkedHashMap 看了注释，在最后一段懵逼了

什么是结构化修改？
在insertion-ordered的LinkedHashMap中，仅仅修改已存在的元素不是结构化修改？
在access-ordered的LinkedHashMap中，仅仅查询（get方法）是结构化修改？
带着这三个疑问，看看接下来的源码

类继承图

解读java集合框架源码-LinkedHashMap

内部节点类和成员属性

解读java集合框架源码-LinkedHashMap

构造器

解读java集合框架源码-LinkedHashMap

插入元素

public class Main {
    public static void main(String[] args) {
        LinkedHashMap<String, String> map = new LinkedHashMap<>();

        map.put("aa", "a");
        map.put("bb", "b");
    }
}

解读java集合框架源码-LinkedHashMap debug上面这段代码，可以看到：

LinkedHashMap添加元素时，调用的是HashMap的put方法 -> putVal -> LinkedHashMap的newNode方法。
如果重写了removeEldestEntry,并且该方法在添加元素时返回了true，那么LinkedHashMap默认将删除第一个添加的元素。
使用空参构造器实例化的对象，默认为插入顺序的，即注释中所说的insertion-ordered（即accessOrder为false）。对于access-ordered，我们在get方法（即访问元素）分析中提到
当key被重复加入时，

访问元素

解读java集合框架源码-LinkedHashMap

如果accessOrder为true时，在调用get方法时，会把LinkedHashMap内部双向链表的首节点挪到尾部，并且递增修改了modCount的值，即结构化修改。（解开了我们在JDK注释中发现的第一和第三个问题）
要利用LinkedHashMap实现LRU cache，除了要重写removeEldestEntry，还需要指定accessOrder为true。
说到这里，我们可以试着解开第二个问题了，在添加元素时，如果key已存在将会调用afterNodeAccess方法

总结

LinkedHashMap继承于HashMap，其内部维护了一个双向链表来保证迭代有序.其迭代时间复杂度不受capacity影响，只受其中存在的元素个数所影响
由于access-order在调用get方法时，会修改modCount的值，因此不能在遍历这种状态的LinkedHashMap时同时调用get，将触发ConcurrentModificationException异常
可以利用LinkedHashMap实现LRU cache，前提是实现removeEldestEntry（满足删除首节点时返回true）、声明LinkedHashMap为access-ordered

原文 https://blog.luhuancheng.com/2019/03/20/解读java集合框架源码-LinkedHashMap/

正文到此结束