1. 与HashMap的区别

LinkedHashMap继承自HashMap，与HashMap的区别就是，LinkedHashMap还维护了一个双向队列：

//LinkedHashMap.java
static class Entry extends HashMap.Node {Entry before, after;Entry(int hash, K key, V value, Node next) {super(hash, key, value, next);}
}
//队头、队尾，使用transient关键字来避免序列化
transient LinkedHashMap.Entry head;
transient LinkedHashMap.Entry tail;

双向队列可以有两种模式：

• 维护插入顺序 （accessOrder = false）
• 维护访问顺序 （AccessOrder= true）

这两种模式的设置可以通过 accessorder 变量来控制，在构造器中，默认是插入顺序：

public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
}

如果要维护访问顺序，就需要在访问节点的时候，调整双向链表结构：

public V get(Object key) {Node e;if ((e = getNode(hash(key), key)) == null)return null;//如果维护访问顺序（LRU），就需要调整链表结构if (accessOrder)afterNodeAccess(e);return e.value;
}

afterNodeAccess(e) 其实就是将刚访问过的节点放到队尾，认为是最近访问的：

void afterNodeAccess(Node e) { // move node to lastLinkedHashMap.Entry last;//如果需要按访问顺序，并且队尾现在不是e，就将e调整到队尾if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry p =(LinkedHashMap.Entry)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;//记录HashMap结构性调整的次数：modify count//除了双向队列的调整，也有HashMap本身的调整，例如插入节点++modCount;}
}

插入元素putVal()方法中，HashMap提供了一个钩子函数 afterNodeInsertion():

//HashMap.java
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//...插入节点...++modCount;if (++size > threshold)//扩容resize();//钩子函数afterNodeInsertion(evict);return null;
}

这个钩子函数默认是空实现，而LinkedHashMap如果想要改为LRU，就需要在超出容量的时候，将最近最少使用的从集合中去除。LinkedHashMap重写了这个钩子函数：

//LinkedHashMap.java
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}
}protected boolean removeEldestEntry(Map.Entry eldest) {return false;
}

到底该不该调用removeNode()删除节点，核心看到 removeEldestEntry() 方法，这个方法在 LinkedHashMap 中默认返回 false，也就是总不会做元素删除的任务。如果我们要改为LRU，就可以在这里修改判断逻辑：

//LRU应该不是这么写的，需要改进
public static class LruMap extends LinkedHashMap, Template> {int capacity;public LruMap(int initialCapacity) {//注意LRU要这么写super(initialCapacity+1,1.0F,true);this.capacity = initialCapacity;}//超过了就删掉最少访问的@Overrideprotected boolean removeEldestEntry(Map.Entry, Template> eldest) {return this.size()>this.capacity;}@Overridepublic Template remove(Object key) {//截获删除的节点，从其他map中把它也删掉//其实也不用截获，它本身被删除之后就没有引用了//如果还有引用，在这里要做后续断掉引用的操作，避免内存泄漏Template removed = super.remove(key);return removed;}
}

同时，为了提供迭代查询的功能，LinkedHashMap 迭代器的实现，与HashMap不同，LinkedHashMap的迭代器是走得双向链表逻辑，遍历的是 LinkedhashMap.Entry ：

final class LinkedKeyIterator extends LinkedHashIteratorimplements Iterator {public final K next() { return nextNode().getKey(); }
}final class LinkedValueIterator extends LinkedHashIteratorimplements Iterator {public final V next() { return nextNode().value; }
}final class LinkedEntryIterator extends LinkedHashIteratorimplements Iterator> {public final Map.Entry next() { return nextNode(); }
}final LinkedHashMap.Entry nextNode() {LinkedHashMap.Entry e = next;if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();current = e;//链表下一个节点next = e.after;return e;
}

在迭代器中的遍历访问，默认不会影响节点访问情况。HashMap中的迭代器的迭代逻辑则是通过 Node 节点的 next 找到下一个节点。

//HashMap.java
final class KeyIterator extends HashIteratorimplements Iterator {public final K next() { return nextNode().key; }
}final class ValueIterator extends HashIteratorimplements Iterator {public final V next() { return nextNode().value; }
}final class EntryIterator extends HashIteratorimplements Iterator> {public final Map.Entry next() { return nextNode(); }
}final Node nextNode() {Node[] t;Node e = next;if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();//访问 e.next 也就是 Node对象的 nextif ((next = (current = e).next) == null && (t = table) != null) {do {} while (index < t.length && (next = t[index++]) == null);}return e;
}

2. LruCache

LinkedHashMap提供了访问顺序的Lru功能，但默认元素大小只占1个单元。在很多场景中，例如Android中，可能需要使用 Lru 作为缓存存储Bitmap等“大小”不定的对象。如此就不能简单地按元素大小为1来计算了。需要额外计算大小。

LruCache工具在Android中有现成的实现

其原理就是 LruCache 类内维护了一个 LinkedHashMap，同时记录了 size 和 maxSize，这个 size 用于记录当前map内元素的总大小，maxSize 表示map内元素能够放的最大空间。注意，这里的元素大小就不是默认占 1 单元了。

下述源码只取核心思想相关源码：

//LruCache.java
public class LruCache{private final LinkedHashMap map;private int size;private int maxSize;public LruCache(int maxSize) {this.maxSize = maxSize;//维护了一个初始大小为0的LinkedHashMap，accessOrder = true，意味着队列维护着最近最少使用顺序this.map = new LinkedHashMap(0, 0.75f, true);}
}

访问元素的时候，调用 map.get() 由于维护的 LinkedHashMap 的 AccessOrder = true 所以 map 本身就维护了最近最少使用链表结构。

public final V get(@NonNull K key) {V target;synchronized (this) {target = map.get(key);}return target;
}

当我们添加元素的时候，需要计算 size，如果大小超了，就要进行元素删除：

public final V put(@NonNull K key, @NonNull V value) {//1.计算大小size += safeSizeOf(key,value);//2.如果覆盖了原来的元素，原先的value将被返回，新的value和旧的value大小可能不同，所以要更新大小V previous = map.put(key,value);if(previous != null){size -= safeSizeOf(key,previous);}//3. 检查容量，如果超出容量了，把最近最少使用的节点移除trimToSize(maxSize);return previous;
}

如果添加的key-value将原有的值覆盖了，由于新旧Value的大小不一定是相同的，所以需要计算更新大小。添加完毕后，通过 trimToSize()检查容量，如果容量超了，根据Lru调度，将最近最少使用的节点移除：

public void trimToSize(int maxSize) {while (true) {K key;V value;synchronized (this) {//移除停止条件是：容量减到不超过 maxSize 为止if (size <= maxSize || map.isEmpty()) {break;}//最先遍历到的是队头，也就是最近最少使用的节点//还记得LinkedHashMap中访问节点时，将节点放到了队尾//插入元素也直接加到队尾（因为插入元素也认为是最近访问）Map.Entry toEvict = map.entrySet().iterator().next();key = toEvict.getKey();value = toEvict.getValue();//删除map.remove(key);//更新sizesize -= safeSizeOf(key, value);}//钩子函数entryRemoved(true, key, value, null);}
}

可能不止移除一个节点，移除停止的条件是容量减到不超过 maxSize 为止。

如果我们要主动移除某个元素，也需要更新 size：

public final V remove(K key){V previous;synchronized (this) {previous = map.remove(key);if (previous != null) {size -= safeSizeOf(key, previous);}}return previous;
}

其中，计算大小的方式是模板方法，具体实现交给上层，具体场景具体计算：

private int safeSizeOf(K key, V value){int result = sizeOf(key, value);return result;
}
//模板方法，默认实现
protected int sizeOf(@NonNull K key, @NonNull V value) {return 1;
}

例如我们存放的是 Bitmap，我们可以计算其内存占用大小:

占用内存 = 图片宽度 / inSampleSize * 图片高度 / inSampleSize * 每个像素所占内存

通过重写 sizeOf()方法：

@Override protected int sizeOf(String key, Bitmap bitmap){return bitmap.getHeight() * bitmap.getWidth() * bitmap.getByteCount();//API 19 以上：return bitmap.getAllocationByteCount();
}