解读java集合框架源码-LinkedHashMap

LinkedHashMap,通过hash表和链表实现。保持迭代有序,与HashMap不同的是,其内部维护了一个双向链表,该链表贯穿了所有元素。
这个列表定义了迭代排序,通常是键插入的顺序(insertion-order)。需要注意的是,在insertion-order时,一个键重复插入时,顺序不会受影响。

JDK注释



看了注释,在最后一段懵逼了

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

类继承图

内部节点类和成员属性

构造器


插入元素

1
2
3
4
5
6
7
8
public class Main {
public static void main(String[] args) {
LinkedHashMap<String, String> map = new LinkedHashMap<>();

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







debug上面这段代码,可以看到:

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

访问元素


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

总结

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