图解LinkedHashMap原理( 五 ) _LinkedHashMap

这里其实遍历的是双向链表，所以不会存在HashMap中需要寻找下一条单向链表的情况，从头结点Entry header的下一个节点开始，只要把当前返回的Entry的after作为下一个应该返回的节点即可。直到到达双向链表的尾部时，after为双向链表的表头节点Entry header，这时候hasNext就会返回false，表示没有下一个元素了。LinkedHashMap的遍历取值如下图所示：

文章插图

LinkedHashMap遍历.png
易知，遍历出来的结果为Entry1、Entry2...Entry6 。
可得，LinkedHashMap是有序的，且是通过双向链表来保证顺序的。
2.10 remove方法
LinkedHashMap没有提供remove方法，所以调用的是HashMap的remove方法，实现如下：
public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); } final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; // LinkedHashMap.Entry重写了该方法 e.recordRemoval(this); return e; } prev = e; e = next; } return e; }在上一篇HashMap中就分析了remove过程，其实就是断开其他对象对自己的引用。比如被删除Entry是在单向链表的表头，则让它的next放到表头，这样它就没有被引用了；如果不是在表头，它是被别的Entry的next引用着，这时候就让上一个Entry的next指向它自己的next，这样，它也就没被引用了。
在HashMap.Entry中recordRemoval方法是空实现，但是LinkedHashMap.Entry对其进行了重写，如下：
void recordRemoval(HashMap<K,V> m) { remove(); } private void remove() { before.after = after; after.before = before; }易知，这是要把双向链表中的Entry删除，也就是要断开当前要被删除的Entry被其他对象通过after和before的方式引用。
所以，LinkedHashMap的remove操作。首先把它从table中删除，即断开table或者其他对象通过next对其引用，然后也要把它从双向链表中删除，断开其他对应通过after和before对其引用。
3 HashMap与LinkedHashMap的结构对比再来看看HashMap和LinkedHashMap的结构图，是不是秒懂了。LinkedHashMap其实就是可以看成HashMap的基础上，多了一个双向链表来维持顺序。

文章插图

HashMap结构.png

文章插图

LinkedHashMap结构.png
4 LinkedHashMap在Android中的应用在Android中使用图片时，一般会用LruCacha做图片的内存缓存，它里面就是使用LinkedHashMap来实现存储的。
public class LruCache<K, V> { private final LinkedHashMap<K, V> map; public LruCache(int maxSize) { if (maxSize <= 0) { throw new IllegalArgumentException("maxSize <= 0"); } this.maxSize = maxSize; // 注意第三个参数，是accessOrder，这里为true，后面会讲到 this.map = new LinkedHashMap<K, V>(0, 0.75f, true); }前面提到了，accessOrder为true，表示LinkedHashMap为访问顺序，当对已存在LinkedHashMap中的Entry进行get和put操作时，会把Entry移动到双向链表的表尾（其实是先删除，再插入）。
我们拿LruCache的put方法举例：
public final V put(K key, V value) { if (key == null || value =https://www.isolves.com/it/cxkf/bk/2019-08-30/= null) { throw new NullPointerException("key == null || value == null"); } V previous; // 对map进行操作之前，先进行同步操作 synchronized (this) { putCount++; size += safeSizeOf(key, value); previous = map.put(key, value); if (previous != null) { size -= safeSizeOf(key, previous); } } if (previous != null) { entryRemoved(false, key, previous, value); } // 整理内存，看是否需要移除LinkedHashMap中的元素 trimToSize(maxSize); return previous; }之前提到了，HashMap是线程不安全的，LinkedHashMap同样是线程不安全的。所以在对调用LinkedHashMap的put方法时，先使用synchronized 进行了同步操作。
我们最关心的是倒数第一行代码，其中maxSize为我们给LruCache设置的最大缓存大小。我们看看该方法：
/** * Remove the eldest entries until the total of remaining entries is at or * below the requested size. * * @param maxSize the maximum size of the cache before returning. May be -1 * to evict even 0-sized elements. */ public void trimToSize(int maxSize) { // while死循环，直到满足当前缓存大小小于或等于最大可缓存大小 while (true) { K key; V value; // 线程不安全，需要同步 synchronized (this) { if (size < 0 || (map.isEmpty() && size != 0)) { throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!"); } // 如果当前缓存的大小，已经小于等于最大可缓存大小，则直接返回 // 不需要再移除LinkedHashMap中的数据 if (size <= maxSize || map.isEmpty()) { break; } // 得到的就是双向链表表头header的下一个Entry Map.Entry<K, V> toEvict = map.entrySet().iterator().next(); key = toEvict.getKey(); value = https://www.isolves.com/it/cxkf/bk/2019-08-30/toEvict.getValue(); // 移除当前取出的Entry map.remove(key); // 从新计算当前的缓存大小 size -= safeSizeOf(key, value); evictionCount++; } entryRemoved(true, key, value, null); } }