江苏龙网

  1. 主页 > 生活百科 > >

图解LinkedHashMap原理( 三 )

LinkedHashMa


当再加入一个元素Entry2，假设index为15：

图解LinkedHashMap原理

文章插图
 
LinkedHashMap结构两个元素.png
当再加入一个元素Entry3, 假设index也是0：
图解LinkedHashMap原理

文章插图
 
LinkedHashMap结构三个元素.png
以上，就是LinkedHashMap的put的所有过程了，总体来看，跟HashMap的put类似，只不过多了把新增的Entry加入到双向列表中 。
2.6 扩容
在HashMap的put方法中，如果发现前元素个数超过了扩容阀值时，会调用resize方法，如下：
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing; // 把旧table的数据迁移到新table transfer(newTable, rehash); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }LinkedHashMap重写了transfer方法，数据的迁移，它的实现如下：
void transfer(HashMap.Entry[] newTable, boolean rehash) { // 扩容后的容量是之前的2倍 int newCapacity = newTable.length; // 遍历双向链表，把所有双向链表中的Entry，重新就算hash，并加入到新的table中 for (Entry<K,V> e = header.after; e != header; e = e.after) { if (rehash) e.hash = (e.key == null) ? 0 : hash(e.key); int index = indexFor(e.hash, newCapacity); e.next = newTable[index]; newTable[index] = e; } }可以看出，LinkedHashMap扩容时，数据的再散列和HashMap是不一样的 。
HashMap是先遍历旧table，再遍历旧table中每个元素的单向链表，取得Entry以后，重新计算hash值，然后存放到新table的对应位置 。
LinkedHashMap是遍历的双向链表，取得每一个Entry，然后重新计算hash值，然后存放到新table的对应位置 。
从遍历的效率来说，遍历双向链表的效率要高于遍历table，因为遍历双向链表是N次（N为元素个数）；而遍历table是N+table的空余个数（N为元素个数） 。
2.7 双向链表的重排序
前面分析的，主要是当前LinkedHashMap中不存在当前key时，新增Entry的情况 。当key如果已经存在时，则进行更新Entry的value 。就是HashMap的put方法中的如下代码：
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 = https://www.isolves.com/it/cxkf/bk/2019-08-30/e.value; e.value = value; // 重排序 e.recordAccess(this); return oldValue; } }主要看e.recordAccess(this)，这个方法跟访问顺序有关，而HashMap是无序的，所以在HashMap.Entry的recordAccess方法是空实现，但是LinkedHashMap是有序的,LinkedHashMap.Entry对recordAccess方法进行了重写 。
void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; // 如果LinkedHashMap的accessOrder为true，则进行重排序 // 比如前面提到LruCache中使用到的LinkedHashMap的accessOrder属性就为true if (lm.accessOrder) { lm.modCount++; // 把更新的Entry从双向链表中移除 remove(); // 再把更新的Entry加入到双向链表的表尾 addBefore(lm.header); } }在LinkedHashMap中，只有accessOrder为true，即是访问顺序模式，才会put时对更新的Entry进行重新排序，而如果是插入顺序模式时，不会重新排序，这里的排序跟在HashMap中存储没有关系，只是指在双向链表中的顺序 。
举个栗子：开始时，HashMap中有Entry1、Entry2、Entry3，并设置LinkedHashMap为访问顺序，则更新Entry1时，会先把Entry1从双向链表中删除，然后再把Entry1加入到双向链表的表尾，而Entry1在HashMap结构中的存储位置没有变化，对比图如下所示：
图解LinkedHashMap原理

文章插图
 
LinkedHashMap重排序.png
2.8 get方法
LinkedHashMap有对get方法进行了重写，如下：
public V get(Object key) { // 调用genEntry得到Entry Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; // 如果LinkedHashMap是访问顺序的，则get时，也需要重新排序 e.recordAccess(this); return e.value; }先是调用了getEntry方法，通过key得到Entry，而LinkedHashMap并没有重写getEntry方法，所以调用的是HashMap的getEntry方法，在上一篇文章中我们分析过HashMap的getEntry方法：首先通过key算出hash值，然后根据hash值算出在table中存储的index，然后遍历table[index]的单向链表去对比key，如果找到了就返回Entry 。


推荐阅读


上一篇：Linux系统CPU负载和CPU使用率

下一篇：go语言中关于字符串使用的总结