LinkedHashMap是LruCache的基础,可以认为,LinkedHashMap是不限容量的Lru,Lru是限制了容量的LinkedHashMap。
LinkedHashMap
LinkedHashMap扩展自HashMap,而且数据存储对象改为扩展自HashMapEntry的LinkedHashMapEntry,主要是增加了before和after,实现双向链表。
LinkedHashMap持有一个LinkedHashMapEntry类型的header,作为链表的表头。
所以LinkedHashMap既有HashMap的数组+链表的二维存储结构,又有链表的前后关系的查找结构。
所以,清空数据集合时,既要调用父类HashMap的数据清空,又要调用自身链表的前后关系清空(把header的before和after全都指向header自己)。
LinkedHashMap自带部分LRU功能,构造函数:
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
其中,第三个参数就代表是否开启LRU,如果为true,在get时,会挪到header前面,注意,header是不变的:
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();//从当前链表节点挪走
addBefore(lm.header);//添加为新的header
}
}
所以,多次访问后,链表的数据关系为:
-第一个访问--第二个访问--第三个访问--header--最久没有访问-(这是一个双向链表)
所以,header前面是最近访问的,header后面是最久没有访问的。
因为遍历地时候会从header开始:
private abstract class LinkedHashIterator<T> implements Iterator<T> {
LinkedHashMapEntry<K,V> nextEntry = header.after;
所以,最前面取得的数据就是最久没有访问的数据。
LruCache
因为LinkedHashMap可以根据最近访问进行排序,所以LruCache使用LinkedHashMap来存储数据:
public LruCache(int maxSize) {
...
this.maxSize = maxSize;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);//开启LinkedHashMap的访问排序
}
LinkeHashMap是可以自动扩容的,所以在LruCache中需要限制数据集合的上限,主要方法就是在put时,挤走最久没有访问的数据:
public final V put(K key, V value) {
...
trimToSize(maxSize);//挤走最久没有访问的数据
return previous;
}
其实就是从header头开始遍历LinkedHashMap,依次从最久没有访问的数据开始清理:
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
...
if (size <= maxSize) {
break;
}
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
...
map.remove(key);
...
}
entryRemoved(true, key, value, null);
}
}
网友评论