6.1 （番外）深入源碼理解HashMap沛申、LinkedHashMap劣领，DiskLruCache
我們看OkHttp的源碼可以知道，他的緩存算法主要是用LruCache算法實現(xiàn)的铁材，Lru的一個典型的實現(xiàn)就是LinedkHashMap尖淘，LinkedHashMap又是基于HashMap實現(xiàn)的，所以要探究他的原理著觉，我們要從HashMap開始說起了
（前排出售香煙啤酒火腿腸村生。。固惯。）
（本文用的是java7，java8 HashMap有部分改動）
HashMap
HashMap繼承自AbstactMap缴守，實現(xiàn)的是Map接口,Map的實現(xiàn)類有一下幾種
Map
├Hashtable
├HashMap
└WeakHashMap
get知識點
HashMap 和 HashTable 的區(qū)別是什么
自行搜索去葬毫，我不說镇辉，有本事你們打我??
laji.jpg
我們要看HashMap的話首先要看他的父類，我們點到AbstractMap<K,V>類,大概看一下 贴捡，里面有兩個內(nèi)部類忽肛，
SimpleEntry SimpleImmutableEntry,他們兩個都是實現(xiàn)了Entry 接口的，我們來看一下比較重要（常用）的幾個方法
-
構(gòu)造函數(shù)
? 構(gòu)造方法AbstractMap只有一種烂斋，屹逛，就是默認的 不過他設置為了protected。
-
put
? Put方法在AbstractMap中只定義了出來汛骂，具體實現(xiàn)給子類實現(xiàn)
-
get
? get方法在AbstractMap中是有實現(xiàn)的罕模，我們都知道HashMap是支持null的 所以這邊先做了一個空的判斷，如果是null帘瞭，那么找key為null的值淑掌，否則的話遍歷尋找key相同的Entry返回，如果都沒找到返回null
public V get(Object key) { Iterator<Entry<K,V>> i = entrySet().iterator(); if (key==null) { while (i.hasNext()) { Entry<K,V> e = i.next(); if (e.getKey()==null) return e.getValue(); } } else { while (i.hasNext()) { Entry<K,V> e = i.next(); if (key.equals(e.getKey())) return e.getValue(); } } return null; }?
-
remove
? 這個remove和get的方法基本是一樣的蝶念，最后的差別是多了一個返回當前移除的值
-
containsKey
和get差不多抛腕，，媒殉，自己瞅担敌，
-
containsValue
同上
上面寫的好輕松，不過下面就開始悲劇了廷蓉，我們來看HashMap全封，在java上HashMap的默認大小是16，在安卓上是4
還有幾個比較重要的參數(shù)來解釋一下
| 參數(shù)名字 | 默認值 | 描述 |
|---|---|---|
| DEFAULT_INITIAL_CAPACITY | java 16苦酱，安卓 4 | HashMap默認的大小 |
| MAXIMUM_CAPACITY | 1<<30 具體數(shù)字1073741824 | HashMap的最大容量 |
| DEFAULT_LOAD_FACTOR | 0.75 | 加載因子（ 加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度售貌，它衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高疫萤，反之愈小 |
以上就是幾個比價重要的參數(shù)颂跨，然后我們按照上面的來分析代碼，首先看他的構(gòu)造函數(shù)
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
HashMap(Map<? extends K, ? extends V> m)
上面的構(gòu)造函數(shù)扯饶，前兩個都是調(diào)用的第三個恒削，默認都是傳的默認值，我們直接看第三個
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* 構(gòu)造具有指定的初始容量和負載因子的空HashMap尾序。
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//如果是用的這個構(gòu)造函數(shù)钓丰，那么初始大小和加載因子需要指明
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
void init() {
}
這邊就是對于默認的幾個數(shù)值做了一下過濾與判斷，init方法是個空方法每币，接著我們看常用的put和get方法
put（key,value）
/**
* An empty table instance to share when the table is not inflated.
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
(省略 携丁、、、梦鉴、李茫、、)
public V put(K key, V value) {
//如果table等于一個空table的話肥橙，初始化table魄宏，大小如果沒有指定的話就是默認的大小
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果是null鍵的話 ，添加null的字符串
if (key == null)
return putForNullKey(value);
//獲取key的hash值進行兩次hash計算
int hash = hash(key);
//根據(jù)hash的值進行尋址存筏，返回的是下標
int i = indexFor(hash, table.length);
//如果第table里面的的entry不為空宠互，然后根據(jù)下標和引用開始向散列表里放值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果添加成功則返回
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
//每當一個條目中的值被對于已經(jīng)在HashMap中的密鑰k調(diào)用put（k，v）覆蓋時椭坚，這個方法被調(diào)用予跌。例如linkedHashMap
e.recordAccess(this);
return oldValue;
}
}
/**這里當他是當前索引的第一個，調(diào)用addEntry添加**/
//模數(shù)加一
modCount++;
//添加到table上藕溅，如果大小不夠的話會進行擴容匕得，倍數(shù)是2的整數(shù)倍
addEntry(hash, key, value, i);
return null;
}
把以上的步驟總結(jié)來說就是這樣
- 如果table是空的話初始化table的大小為默認值
- 如果key是null的話處理null值的value，hash值為0巾表，index也是0汁掠，添加之后return
- 如果key不為null的話，獲取他的hash值集币，獲得再次進行兩次hash的hash值考阱，與table的長度進行&操作獲取下標
- 遍歷table，如果當前的下邊的entry不為null鞠苟，并且key和hash相同乞榨，就進行覆蓋操作
- 如果不是的話新建一個entry，添加到table下標為i的地方当娱，原來下標上的entry做為entry的下個節(jié)點
整個步驟拿圖來講的話是這樣
流程.png
如果是null的鍵的話他永遠在table的第0個下標吃既，如果存在就是覆蓋掉原來的value, 這就是他put 操作 ，核心就在他的散列算法跨细，如何讓各個不同的鍵均勻的分布鹦倚，不然就會造成一個index下的entry有很長，這樣效率會被降低冀惭。
他的散列就是Hash算法
final int hash(Object k) {
int h = hashSeed;
//hashSeed只有在hash表的大與等于 Integer.MAX_VALUE或者是設置的系統(tǒng)變量jdk.map.althashing.threshold震叙， 才不為0(好多博客對這塊描述不多或者理解有誤，以為key是String 直接就進來了)
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
//此功能可確保每個位位置上不同倍數(shù)不同的hashCode具有有界數(shù)量的沖突（默認加載因子約為8）散休。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
里面的hashSeed正常情況下都是0媒楼，非0的情況是你的table size大于等于設置的系統(tǒng)變量jdk.map.althashing.threshold 或者 Integer.MAX_VALU，一般都不會碰到這種情況
后面的hash看起來就關系就簡單多了戚丸。獲取key的hashCode划址，因為是native方法 看不到。h默認是0，進行的是一個^（異或）運算夺颤，然后下面的就是對h一頓無符號位移操作对人，進行了兩次，確保他的不同拂共。
接著的一個算法是尋找合適的下標的算法，indexFor
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
這不用多講姻几，一個與運算宜狐，基本put方法重要且難理解的都在這邊講解了，下面講get方法
get
get的代嗎還是比較少比較好理解的
public V get(Object key) {
//null key 獲取null key的值 table的第0位 尋找key為null的
if (key == null)
return getForNullKey();
//和上面的套路差不多蛇捌，通過調(diào)用hash 和 indexFor的方法找到他的下標抚恒，在下標里面遍歷尋找到他的值
Entry<K,V> entry = getEntry(key);
//null的話返回null
return null == entry ? null : entry.getValue();
}
----- 我是一個漂亮的分割線 ------
//上面方法用用到的方法
//找null key
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
//找非null key
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
其他幾個方法我就不起一一分析了，基本上就是根據(jù)getEntry（）來進行判斷的 络拌，沒辦法 誰讓我這么懶俭驮。。
HashMap看完之后我們來看LinkedHashMap春贸，就輕松多了
LinkedHashMap
LinkedHashMap繼承自HashMap混萝，我們按照一樣的套路去看LinkedHashMap，發(fā)現(xiàn)他的構(gòu)造函數(shù)和HashMap的構(gòu)造函數(shù)是一樣的萍恕，不同的地方是多了一個accessOrder逸嘀，acessOrder上面的描述是
該鏈接哈希映射的迭代排序方法：對于訪問順序為true，對于插入順序為false允粤。
這樣的操作像不像LRU崭倘，不過默認是按照插入順序排序的，也就是默認值是false
init方法里类垫，初始化了header，是個Entry，繼承自HashMap的Entry责鳍，是個雙向鏈表挡鞍，里面包含他的前一個節(jié)點和后一個節(jié)點
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
(省略 添加和刪除部分。购撼。跪削。。)
//這個方法在HashMap中put操作的時候有被調(diào)用過迂求，我們發(fā)現(xiàn)LinkedHashMap沒有重寫put方法碾盐，所以我們就分析這個方法，這個方法就是在插入的時候記錄他的插入順序(心機boy揩局，藏得這么深毫玖，搞的這么巧妙)
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
}
用圖片表示的話就是這樣
LinkedHashMap.png
他這邊記錄了兩份，一份是在Hash表里的，一份是雙向鏈表付枫，如果accessOrder為true的話烹玉，每次都會把最近調(diào)用的放到鏈表的最后方，他調(diào)用的地方有兩處
- get方法
- HashMap中put的方法（覆蓋）
我們來運行個例子
LinkedHashMap linedHashMap = new LinkedHashMap(16,0.75f,true);
linedHashMap.put("key1","test1");
linedHashMap.put("key2","test2");
linedHashMap.put("key3","test3");
linedHashMap.put("key4","test4");
linedHashMap.put("key5","test5");
for (Iterator<String> iterator = linedHashMap.values().iterator(); iterator
.hasNext();) {
String name = (String) iterator.next();
System.out.println(name);
}
link1.png
當我們進行一些操作的時候
LinkedHashMap linedHashMap = new LinkedHashMap(16,0.75f,true);
linedHashMap.put("key1","test1");
linedHashMap.put("key2","test2");
linedHashMap.put("key3","test3");
linedHashMap.put("key4","test4");
linedHashMap.put("key5","test5");
linedHashMap.get("key1");
linedHashMap.get("key3");
for (Iterator<String> iterator = linedHashMap.values().iterator(); iterator
.hasNext();) {
String name = (String) iterator.next();
System.out.println(name);
}
link.png
我們發(fā)現(xiàn)阐滩， 最近使用的就排到了這個鏈表的最后面二打，nice，知道了這個原理之后掂榔，感覺自己都能寫一個LRUcache算法了是不是
有沒有很開心很激動继效？
別著急，装获，接著看
DiskLruCache
Jake Wharton的微笑鎮(zhèn)樓
DisLruCache 這邊我們拿JW大神的來講瑞信，OkHttp里面的是被改造過的 ，會有點小的不同穴豫，不過問題不大凡简，還有就是 ，我們是按照大體的流程來梳理一下精肃，具體的細節(jié)就要考大家去自己看源碼了秤涩。
我們的測試程序如下
public class TestMain {
private static final long cacheSize = 1024 * 1024 * 20;//緩存文件最大限制大小20M
private static String cachedirectory = "/Users/Mirsfang/Desktop" + "/caches"; //設置緩存文件路徑,自己設置
public static void main(String[] args) {
testWirteDiskLruCache();
}
//寫入
private static void testWirteDiskLruCache() {
DiskLruCache diskCache = null;
try {
diskCache = DiskLruCache.open(new File(cachedirectory), 10010, 1, cacheSize);
String urlKey = "test_request1_1";
String testJson = "{\"result\":{\"errmsg\":\"令牌失效\",\"errcode\":\"101\"}}";
try {
DiskLruCache.Editor editor = diskCache.edit(urlKey);
OutputStream outPutStream = editor.newOutputStream(0);
OutputStreamWriter steamWriter = new OutputStreamWriter(outPutStream);
steamWriter.write(testJson);
steamWriter.close();
outPutStream.flush();
outPutStream.close();
editor.commit();
diskCache.flush();
diskCache.close();
} catch (IOException e) {
e.printStackTrace();
} finally {
}
} catch (IOException e) {
e.printStackTrace();
}
}
//讀取
private static void testGetDiskLruCache() {
DiskLruCache diskCache = null;
StringBuilder sb = new StringBuilder();
try {
diskCache = DiskLruCache.open(new File(cachedirectory), 10010, 1, cacheSize);
String urlKey = "test_request1_1";
try {
DiskLruCache.Snapshot snapshot = diskCache.get(urlKey);
String inputSteam = snapshot.getString(0);
diskCache.flush();
diskCache.close();
System.out.print("得到文本: "+inputSteam);
} catch (IOException e) {
e.printStackTrace();
} finally {
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
首先還是從構(gòu)建方法搞起，構(gòu)建方法是不對外公開的 只能通過open去構(gòu)建
/**
* 傳入的參數(shù)
* @param directory 可寫入的目錄
* @param valueCount 每個緩存條目的值的數(shù)量司抱。 必須是正的溉仑。
* @param maxSize 該緩存應用于存儲的最大字節(jié)數(shù)
* @throws IOException if reading or writing the cache directory fails
*
**/
public static DiskLruCache open(File directory, int appVersion, int valueCount, long maxSize)
throws IOException {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
if (valueCount <= 0) {
throw new IllegalArgumentException("valueCount <= 0");
}
// If a bkp file exists, use it instead.如果存在bkp文件，請改用它状植。
File backupFile = new File(directory, JOURNAL_FILE_BACKUP);
if (backupFile.exists()) {
File journalFile = new File(directory, JOURNAL_FILE);
// If journal file also exists just delete backup file.
// 如果日記文件也存在只是刪除備份文件浊竟。
if (journalFile.exists()) {
backupFile.delete();
} else {
renameTo(backupFile, journalFile, false);
}
}
// 初始化DisLruCache ，如果日志文件存在津畸，振定，那么就用原來的
DiskLruCache cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
if (cache.journalFile.exists()) {
try {
cache.readJournal();
cache.processJournal();
return cache;
} catch (IOException journalIsCorrupt) {
System.out
.println("DiskLruCache "
+ directory
+ " is corrupt: "
+ journalIsCorrupt.getMessage()
+ ", removing");
cache.delete();
}
}
//否則的話重新創(chuàng)建
directory.mkdirs();
cache = new DiskLruCache(directory, appVersion, valueCount, maxSize);
//構(gòu)建日志文件，寫入日志的頭
cache.rebuildJournal();
return cache;
}
然后是edit（key）方法肉拓，構(gòu)建一個DiskLruCache.Editor
public Editor edit(String key) throws IOException {
return edit(key, ANY_SEQUENCE_NUMBER);
}
private synchronized Editor edit(String key, long expectedSequenceNumber) throws IOException {
//判斷journalWriter是否關閉
checkNotClosed();
//驗證key是否合法(正則驗證)
validateKey(key);
//從linkedHashMap中檢查一下是否存在Entry
Entry entry = lruEntries.get(key);
//如果緩存是無效的后频，返回null
if (expectedSequenceNumber != ANY_SEQUENCE_NUMBER && (entry == null
|| entry.sequenceNumber != expectedSequenceNumber)) {
return null; // Snapshot is stale.
}
//如果entry為空，新new一個entry暖途，添加到linkedHashMap中
if (entry == null) {
entry = new Entry(key);
lruEntries.put(key, entry);
} else if (entry.currentEditor != null) {
return null; // Another edit is in progress.
}
//新建一個editor對象
Editor editor = new Editor(entry);
entry.currentEditor = editor;
// 寫入日志文件記錄
journalWriter.write(DIRTY + ' ' + key + '\n');
journalWriter.flush();
return editor;
}
我們發(fā)現(xiàn)卑惜，基本的寫入操作都是由Editor的newOutputStream的這個Steam完成的，我們?nèi)タ茨莻€方法
public OutputStream newOutputStream(int index) throws IOException {
//進行下標判斷驻售，是否合法
if (index < 0 || index >= valueCount) {
throw new IllegalArgumentException("Expected index " + index + " to "
+ "be greater than 0 and less than the maximum value count "
+ "of " + valueCount);
}
//為避免線程問題
synchronized (DiskLruCache.this) {
//看獲取的entry的editor和當前的是否一直
if (entry.currentEditor != this) {
throw new IllegalStateException();
}
//如果readable是fasle露久，written[]這個數(shù)組index改為true,這個是為了兼容一個key對應多個的問題
if (!entry.readable) {
written[index] = true;
}
//根據(jù)index和entry，獲取對應的緩存文件
File dirtyFile = entry.getDirtyFile(index);
FileOutputStream outputStream;
try {
//打開輸入管道
outputStream = new FileOutputStream(dirtyFile);
} catch (FileNotFoundException e) {
// Attempt to recreate the cache directory.
//遇見異常失敗的話嘗試重新創(chuàng)建緩存目錄欺栗。
directory.mkdirs();
try {
outputStream = new FileOutputStream(dirtyFile);
} catch (FileNotFoundException e2) {
// We are unable to recover. Silently eat the writes.
return NULL_OUTPUT_STREAM;
}
}
//返回輸出管道
return new FaultHidingOutputStream(outputStream);
}
}
這樣通過outputStream就寫入到文件里了FaultHidingOutputStream是一個繼承FilterOutputStream的包裝類毫痕，對一些錯誤進行了標記征峦，這個大概就是寫入的這個流程，其實DiskLruCache主要的是get方法消请，看如何計數(shù)操作
get方法
public synchronized Snapshot get(String key) throws IOException {
//檢查文件流是否關閉
checkNotClosed();
//檢查key的有效性
validateKey(key);
//通過LinkedHashMap中獲取Entry
Entry entry = lruEntries.get(key);
//判斷entry的合法性
if (entry == null) {
return null;
}
if (!entry.readable) {
return null;
}
// Open all streams eagerly to guarantee that we see a single published
// snapshot. If we opened streams lazily then the streams could come
// from different edits.
//積極地打開所有流栏笆，以保證我們看到一個已發(fā)布的snapshot。 如果我們懶加載的方式打開流臊泰，那么流可以來自不同的edits蛉加。
//
InputStream[] ins = new InputStream[valueCount];
try {
for (int i = 0; i < valueCount; i++) {
ins[i] = new FileInputStream(entry.getCleanFile(i));
}
} catch (FileNotFoundException e) {
// A file must have been deleted manually!
for (int i = 0; i < valueCount; i++) {
if (ins[i] != null) {
Util.closeQuietly(ins[i]);
} else {
break;
}
}
return null;
}
redundantOpCount++;
journalWriter.append(READ + ' ' + key + '\n');
//檢測是否到達清理標準
if (journalRebuildRequired()) {
//開啟線程進行清理
executorService.submit(cleanupCallable);
}
return new Snapshot(key, entry.sequenceNumber, ins, entry.lengths);
}
這里我們看到他是從LinkedHashMap中獲取Entry的，后面缸逃，然后進行計數(shù)和日志的寫入七婴，最后的這個
if (journalRebuildRequired()) {
//開啟線程進行清理
executorService.submit(cleanupCallable);
}
是重點，他負責打開清理線程察滑， 這是DiskLruCache的核心，為什么DiskLruCache會清理修肠，我們來看這個線程
private final Callable<Void> cleanupCallable = new Callable<Void>() {
public Void call() throws Exception {
synchronized (DiskLruCache.this) {
//如果日志寫入為空贺辰，說明現(xiàn)在的狀態(tài)是異常的
if (journalWriter == null) {
return null; // Closed.
}
//清理垃圾緩存
trimToSize();
if (journalRebuildRequired()) {
//我們只能重新建立這個日志的時候，它會縮小日志的大小嵌施，并且至少消除2000個記錄饲化。
rebuildJournal();
redundantOpCount = 0;
}
}
return null;
}
};
//垃圾清除,當size比最大的size大的時候，從不活躍的開始清除
private void trimToSize() throws IOException {
while (size > maxSize) {
Map.Entry<String, Entry> toEvict = lruEntries.entrySet().iterator().next();
remove(toEvict.getKey());
}
}
我們查看這個trimToSize（）的調(diào)用的地方有
- flush()
- close()
調(diào)用清理線程的地方有
- get()
- setMaxSize()
- completeEdit()
可以發(fā)現(xiàn)這幾個點 存數(shù)據(jù)吗伤，大小改變吃靠，獲取數(shù)據(jù)，關閉 這幾個地方都會去檢測是否去清理垃圾足淆。
大概主要的流程就是這樣巢块，DiskLruCache 其中比較細節(jié)的地方就需要自己去看了，這邊就不細講了巧号，有什么問題的話可以進群交流 群號 579508560
