image.png
緩存算法的基本概念
源碼基于JDK1.7
緩存機(jī)制
內(nèi)存緩存
本地緩存
網(wǎng)絡(luò)緩存
本節(jié)記錄的是內(nèi)存緩存
什么是內(nèi)存緩存得封？
將數(shù)據(jù)寫到了容器(list,map,set)等數(shù)據(jù)存儲單元中尸疆。
緩存淘汰機(jī)制
緩存是不能無限制緩存的搬设，所以就有一套緩存淘汰機(jī)制
- FIFO （First In, First Out）
- LFU (Least Frequently Used)
- LRU (Least Recently Used) 最近最少使用算法
LRU 的工作原理
- 新數(shù)據(jù)插入到鏈表頭部
- 當(dāng)緩存命中(即緩存數(shù)據(jù)被訪問)器仗，數(shù)據(jù)要移到表頭
- 當(dāng)鏈表滿的時候逢慌，將鏈表尾部的數(shù)據(jù)丟棄
鏈表表頭就表示最近訪問的數(shù)據(jù)泳姐，鏈表尾表示即將被淘汰的數(shù)據(jù)
LinkedHashMap 是如何實現(xiàn) LruCache 算法的乍赫？
LinkedHashMap的使用
final LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<Integer, String>(0, 0.75f, true) {
//3.當(dāng)鏈表滿的時候温峭，將鏈表尾部的數(shù)據(jù)丟棄
@Override
protected boolean removeEldestEntry(Entry eldest) {
if (size() > 5) {
System.out.println("remove ：" + eldest.getKey());
return true;
}
return false;
}
};
//1.新數(shù)據(jù)插入到鏈表頭部
lruCache.put(1, "1");
lruCache.put(2, "2");
lruCache.put(3, "3");
lruCache.put(4, "4");
lruCache.put(5, "5");
lruCache.put(6, "6");
//2.緩存命中
//String s = lruCache.get(3);
Set<Map.Entry<Integer, String>> entries = lruCache.entrySet();
for (Map.Entry<Integer, String> entry : entries) {
Integer key = entry.getKey();
String value = entry.getValue();
System.out.println("key:" + key + ",value = " + value);
}
-----打印結(jié)果----
remove ：1
key:2,value = 2
key:3,value = 3
key:4,value = 4
key:5,value = 5
key:6,value = 6
LinkedHashMap 的內(nèi)部實現(xiàn)原理
LinkedHashMap 是繼承至 HashMap 猛铅，它工作原理是是由 HashMap 的散列表和 LinkedHashMap 的雙鏈表組成。
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
- put(key凤藏，value)
因為 LinkedHashMap 沒有重寫 put 方法奸忽，因此會走 HashMap 的 put 方法，最終執(zhí)行 LinkedHashMap 的 createEntry 函數(shù)揖庄，將要插入地數(shù)據(jù)添加到鏈表表頭栗菜。
HashMap 的實現(xiàn)
public V put(K key, V value) {
//hashMap 存儲邏輯，找到 hash,key,value,i 等值
addEntry(hash, key, value, i);
return null;
}
//擴(kuò)容判斷
//createEntry將數(shù)據(jù)插入到hashmap的散列表中
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
LinkedHashMap 的實現(xiàn)
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
//3.當(dāng)鏈表滿的時候蹄梢，將鏈表尾部的數(shù)據(jù)丟棄
//在插入數(shù)據(jù)時回調(diào)給外層是否要移除該數(shù)據(jù)
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
//1.將要插入數(shù)據(jù)移到鏈表頭部
e.addBefore(header);
size++;
}
當(dāng)緩存命中(即緩存數(shù)據(jù)被訪問)疙筹，數(shù)據(jù)要移到表頭
//LinkedHashMap#get
public V get(Object key) {
//從 hashmap 中獲取對應(yīng)的 Enrty
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
//2.緩存命中
e.recordAccess(this);
return e.value;
}
//LinkedHashMap$Enrty.recordAccess
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//如果是按照訪問順序進(jìn)行存儲
if (lm.accessOrder) {
lm.modCount++;
//先將該 Entry進(jìn)行移除
remove();
//將該 Entry 添加到表頭
addBefore(lm.header);
}
}
當(dāng)鏈表滿的時候，將鏈表尾部的數(shù)據(jù)丟棄
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
這里就需要開發(fā)者去定義什么時候禁炒，緩存已滿而咆，這里官方文檔有一個栗子：
//重寫 LinkedHashMap 的這個方法，實現(xiàn) removeEldestEntry 的邏輯即可幕袱。
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
ImageLoader 的 LruCache 算法的實現(xiàn)
源碼地址：LruMemoryCache.java
LruMemoryCache的初始化
LruMemoryCache 內(nèi)部就是根據(jù) LinkedHashMap 來進(jìn)行 LruCache 算法的
private final LinkedHashMap<String, Bitmap> map;
private final int maxSize;
/** Size of this cache in bytes */
private int size;
/** @param maxSize Maximum sum of the sizes of the Bitmaps in this cache */
public LruMemoryCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap<String, Bitmap>(0, 0.75f, true);
}
存儲數(shù)據(jù)
@Override
public final boolean put(String key, Bitmap value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
synchronized (this) {
//計算要緩存圖片的大小
size += sizeOf(key, value);
//將圖片存儲到 LinkedHashMap 中
//previous 不為 null 表示之前存在相同 key
//previous 為 null 表示 key 是第一次存儲
Bitmap previous = map.put(key, value);
if (previous != null) {
//把先前的bitmap的大小進(jìn)行移除
size -= sizeOf(key, previous);
}
}
//判斷是否要 lru 淘汰
trimToSize(maxSize);
return true;
}
取數(shù)據(jù)
緩存命中
@Override
public final Bitmap get(String key) {
if (key == null) {
throw new NullPointerException("key == null");
}
synchronized (this) {
//通過上面分析的 LinkedHashMap 的 get 函數(shù)可以知道
//它內(nèi)部將從散列表中查詢到數(shù)據(jù)Entry 從雙向鏈表移除暴备，然后添加到雙向鏈表的表頭
return map.get(key);
}
}
移除數(shù)據(jù)
private void trimToSize(int maxSize) {
while (true) {
String key;
Bitmap value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
}
//緩存夠用
if (size <= maxSize || map.isEmpty()) {
break;
}
//緩存不夠用
Map.Entry<String, Bitmap> toEvict = map.entrySet().iterator().next();
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
//從 linkedHashMap 中移除
map.remove(key);
//將數(shù)據(jù)的 size 更新
size -= sizeOf(key, value);
}
}
}
本文是筆者學(xué)習(xí)之后的總結(jié)，方便日后查看學(xué)習(xí)凹蜂，有任何不對的地方請指正馍驯。
記錄于 2019年6月3號
