在设计缓存时，比如Bitmap图片缓存，使用LruCache实现。它内部是LinkedHashMap，继承HashMap，采用数组+双向链表的数据结构。
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;//缓存最大值
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
构造方法，创建一个LinkedHashMap，初始化容量是0，加载因子0.75，容量大于总量的75%时，扩充，继承HashMap的特性。
看一下LruCache的get方法和put方法。
public final V get(K key) {
//key不允许空。
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
...
}
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value);
//previous是之前的值
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
这两个方法都不太复杂，key和value不可以是空，他们都是利用内部LinkedHashMap的方法实现缓存的存取，HashMap线程不安全，访问时加上synchronized同步。
在put方法，最后有个trimToSize方法，若size已经达到maxSize最大值，从LinkedHashMap中找到最不常用的eldest删掉，就是将很少使用的拿出来删除，腾地方。
eldest就是LinkedHashMap双向链表头部节点。
public Entry<K, V> eldest() {
LinkedEntry<K, V> eldest = header.nxt;
return eldest != header ? eldest : null;
}
这说明这个双向链表是有序的，按照使用频率，从尾到头排序，头部最不常用。
下面主要分析一下LinkedHashMap的实现原理。
LinkedHashMap实现原理
LinkedHashMap继承HashMap。
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
LruCache创建它时，accessOrder标志表示是否按照访问顺序排序，false表示按照插入的顺序排序。看一下LinkedHashMap的get方法。
@Override
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
}
当key是空时，与HashMap类似，将内部为空key准备的一个Entry返回，注意，在LruCache使用时是不会有空key的。然后，由key计算哈希值，查找HashMapEntry数组中的坑位，在这里哈希值是相等，遍历坑位处的HashMapEntry链表，找到与key值完全相等的节点，返回它的value值。基本查找流程与HashMap相同，不同点，若有accessOrder标志，需要做一次makeTail操作。该方法将此处的HashMapEntry节点移动到双向链表尾部，即header前面。具体意思就是，若get访问到这一项，就将该项放到尾部，若构造方法未传入accessOrder这个字段，就不需要操作，插入时在什么位置就一直在什么位置。
这种操作让经常访问的节点在尾部，不常用的节点在头部，方便删除不常用节点。
LinkedHashMap内部使用的节点是LinkedEntry，它继承HashMapEntry，增加了nxt和prv，使节点变成双向的。
存入数据采用父类HashMap的put方法，重写addNewEntry方法。
@Override
void addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);
table[index] = oldTail.nxt = header.prv = newTail;
}
将新节点放到数组索引链表头部位置。因为LinkedEntry所有节点是双向链表结构，插入位置在双向链表的尾部。
LinkedHashMap数据存储结构图。
LinkedHashMap存储结构图.png
- 索引0增加对象的情况：当前索引index=0处空，不存在对象，新增一个对象插到header前面(黄色节点)，建立前后指针连接关系，并将该对象放入index=0位置，红线引用。
- 索引8增加对象的情况：当前索引index=8处已经有一个对象(红色节点)，新增一个对象插到header前面(黄色节点)，建立前后指针连接关系，并将新对象放入index=8位置，红线引用1，并指向之前索引8处的节点，红线引用2，虚线为index=8的原引用。
总结
LruCache的key不可以是空。内部采用LinkedHashMap，数组和双向链表，它保留HashMap数组元素的链表形式，同时，将所有节点加上pre和next指针，改装成一个双向链表，使节点集合全部链接。
双向链表按照访问顺序(get)排序，不经常访问的在头部，经常访问的在尾部。
任重而道远
网友评论