目录
1.LinkedHashMap是什么
2.LinkedHashMap的底层结构
3.LinkedHashMap的特性
4.LinkedHashMap的数据迁移
一个基于LinkedList和HashMap实现的Map,继承自HashMap,实现了Map接口。源码上的注释告诉了我们以下几件事:
底层实现:基于LinkedList和HashMap实现,允许null元素,内部维护了一个贯穿所有内部节点的双向链表,可以通过构造函数来指定其迭代顺序(插入顺序/访问顺序)。
性能:与HashMap一样,add、contains、remove提供恒定的时间性能,假设hash函数在bucket之间适当地分散元素。性能可能略低于HashMap,这是因为维护链表会增加额外的开销。LinkedHashMap有两个影响其性能的参数:初始容量和负荷系数。但请注意,对于这个类来说,为初始容量选择一个过高的值的惩罚要比HashMap要轻,因为这个类的迭代次数不受容量的影响。
同步机制:LinkedHashMap的实现是不同步的,如果多个线程同时访问LinkedHashMap实例,并且至少有一个线程在结构上进行了修改,则必须在外部同步。(结构修改是添加或删除一个或多个映射的任何操作,或者在访问有序的LinkedHashMap情况下,影响迭代顺序的任何操作。在保证插入顺序的LinkedHashMap中,仅更改与映射中已包含的键相关联的值不是结构修改。在LinkedHashMap中,仅仅使用get查询映射是一种结构修改 ),这通常是通过在LinkedHashMap实例对象上进行同步来实现。 如果不存在这样的对象,应使用Collections.synchronizedMap(new LinkedHashMap(...))来创建线程同步的集合。
fail-fast特性:迭代器为快速失败,用迭代器遍历LinkedHashMap时,迭代器的remove()和add()会抛出ConcurrentModificationException异常,迭代器的fail-fast行为在不同步的并发修改时不能得到硬性保证,fail fast行为应仅用于检测错误,不要依赖此异常进行编程。
既然是由双向链表维护的内部结构,那么我们先来看一下其基础存储结构:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5SOihjM0YjYyUTZxYTNhlTMkJTNjNTN4YzNlVTO2UmYw8CX3AzLclDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL3M3Lc9CX6MHc0RHaiojIsJye.png)
果然在HashMap的基础上增加了前后两个指针,其实LinkedHashMap底层存储原理如下图所示:
LinkedHashMap最主要的特性为迭代元素的时候支持按照插入顺序或访问顺序迭代,什么是插入顺序和访问顺序呢?插入顺序:
可以看到元素的迭代顺序完全按照元素的插入顺序来迭代,访问顺序:
当我们在构造函数中给accessOrder变量传入true后会发现,元素的迭代顺序会按照我们的访问顺序来迭代(先访问的最后迭代)。accessOrder变量就是控制LinkedHashMap元素迭代顺序的开关,True为按照元素访问顺序迭代,False为按照元素插入顺序迭代。那LinkedHashMap是如何实现这个功能的呢?LinkedHashMap在构造的时候,先调用HashMap构造函数初始化了一个Entry[] table,然后调用自身重写过的init()初始化了一个只有头结点的双向链表:
接下来我们查看LinkedHashMap的put方法,可以看到其内部并无put方法,而是使用的HashMap的put方法,只是重写了其中的recordAccess()和addEntry()方法:
//HashMap中的put方法 public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this);//LinkedHashMap对recordAccess方法进行了重写 return oldValue; } } modCount++; addEntry(hash, key, value, i);//LinkedHashMap对addEntry方法进行了重写 return null; }
看到这不得不佩服JDK的设计如此巧妙,接下来我们重点看一下addEntry():
void addEntry(int hash, K key, V value, int bucketIndex) { super.addEntry(hash, key, value, bucketIndex); // Remove eldest entry if instructed Entry<K,V> eldest = header.after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } } void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; e.addBefore(header); size++; } private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }
由源码可知LinkedHashMap首先调用了HashMap中的addEntry()方法,并对HashMap中的createEntry()方法进行了重写,先将元素添加至table数组(添加过程为HashMap的添加过程),然后将新增结点添加至双向链表中。举个例子:首先是只加入一个元素Entry1,假设index为0:
当再加入一个元素Entry2,假设index为15:
当再加入一个元素Entry3, 假设index也是0:
recordAccess()方法我们去get()的源码中查看:LinkedHashMap的get()显示调用的hashmap的getEntry(),随后调用了LinkedHashMap.Entry的recordAccess方法,进行重新排序,把get的Entry移动到双向链表的表尾(顺序访问)。
public V get(Object key) { Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; e.recordAccess(this); return e.value; } void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; if (lm.accessOrder) { lm.modCount++; //把更新的Entry从双向链表中移除 remove(); // 再把更新的Entry加入到双向链表的表尾 addBefore(lm.header); } }
在LinkedHashMap中,只有accessOrder为true,即是访问顺序模式,才会对更新的Entry进行重新排序,而如果是插入顺序模式时,不会重新排序,这里的排序跟在HashMap中存储没有关系,只是指在双向链表中的顺序。eg:开始时,HashMap中有Entry1、Entry2、Entry3,并设置LinkedHashMap为访问顺序,则更新Entry1时,会先把Entry1从双向链表中删除,然后再把Entry1加入到双向链表的表尾,而Entry1在HashMap结构中的存储位置没有变化,对比图如下所示:
LinkedHashMap重写了HashMap中扩容后数据迁移的方法transfer():
可以看到和HashMap的区别为:
HashMap:先遍历旧table,再遍历旧table中每个元素的单向链表,取得Entry后重新计算其在数组中的位置,然后存放到新table的对应位置。
LinkedHashMap:遍历的双向链表,取得每一个Entry后重新计算其在数组中的位置,然后存放到新table的对应位置。