Java数据结构 - LinkedHashMap 与 LruCache

1. 与HashMap的区别

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

//LinkedHashMap.java
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}
//队头、队尾，使用transient关键字来避免序列化
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> 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<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //如果维护访问顺序（LRU），就需要调整链表结构
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

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

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    //如果需要按访问顺序，并且队尾现在不是e，就将e调整到队尾
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = 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 eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

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

//LRU应该不是这么写的，需要改进
public static class LruMap extends LinkedHashMap<Class<?>, Template> {
    int capacity;

    public LruMap(int initialCapacity) {
        //注意LRU要这么写
        super(initialCapacity+1,1.0F,true);
        this.capacity = initialCapacity;
    }

    //超过了就删掉最少访问的
    @Override
    protected boolean removeEldestEntry(Map.Entry<Class<?>, Template> eldest) {
        return this.size()>this.capacity;
    }

    @Override
    public Template remove(Object key) {
        //截获删除的节点，从其他map中把它也删掉
        //其实也不用截获，它本身被删除之后就没有引用了
        //如果还有引用，在这里要做后续断掉引用的操作，避免内存泄漏
        Template removed = super.remove(key);
        return removed;
    }
}

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

final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().getKey(); }
}

final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> 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 HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

final class ValueIterator extends HashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

final Node<K,V> nextNode() {
    Node<K,V>[] t;
    Node<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    //访问 e.next 也就是 Node对象的 next
    if ((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<K,V>{
    private final LinkedHashMap<K,V> map;
    private int size;
    private int maxSize;
    
    public LruCache(int maxSize) {
        this.maxSize = maxSize;
        //维护了一个初始大小为0的LinkedHashMap，accessOrder = true，意味着队列维护着最近最少使用顺序
        this.map = new LinkedHashMap<K, V>(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<K, V> toEvict = map.entrySet().iterator().next();
            key = toEvict.getKey();
            value = toEvict.getValue();
            //删除
            map.remove(key);
            //更新size
            size -= 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();
}