本章所有源代碼基于JDK1.8版本
HashMap 和 HashSet 是 Java Collection Framework 的兩個(gè)重要成員，其中 HashMap 是 Map 接口的常用實(shí)現(xiàn)類，HashSet 是 Set 接口的常用實(shí)現(xiàn)類。雖然 HashMap 和 HashSet 實(shí)現(xiàn)的接口規(guī)范不同，但它們底層的 Hash 存儲(chǔ)機(jī)制完全一樣，甚至 HashSet 本身就采用 HashMap 來實(shí)現(xiàn)的，這一點(diǎn)我們通過查看HashSet的源代碼就能看得到。
通過閱讀源代碼分析存儲(chǔ)邏輯
HashMap
在日常的編程過程中，如果我們想要使用HashMap類，通常寫法如下：
HashMap<String, String> params = new HashMap<String, String>();
params.put("phone","1234567890");
params.put("dtype","json");
可以由此看出，HashMap中將一個(gè)key-value作為一個(gè)整體進(jìn)行處理，系統(tǒng)根據(jù)key的Hash值計(jì)算key-value的存儲(chǔ)位置，這樣可以保證快速存、取Map的key-value值。
下面我們查看一下HashMap中put方法的源碼實(shí)現(xiàn)：
//put方法的入口，直接調(diào)用putVal進(jìn)行處理
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**hash key計(jì)算得到的Hash值
* key key
* value key對應(yīng)的value
* onlyIfAbsent 如果該參數(shù)為true，則不能修改已經(jīng)存在的值
* 返回 key的hash值對應(yīng)的位置之前的value，如果沒有，直接返回空
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果長度為0，或者HashMap為空，則重新計(jì)算長度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果key為null，則hash值為0，i值為0，則獲取整個(gè)Node數(shù)組位置0處的值，是否為null
//為null代表當(dāng)前位置0處，用于存放hash值為0位置沒有任何元素，則將現(xiàn)有key-value放入這個(gè)位置，作為鏈表第一個(gè)對象
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果key不為空，且在隊(duì)列中這個(gè)key已經(jīng)存在，得到當(dāng)前位置node值。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果hash值對應(yīng)位置是一個(gè)鏈表數(shù)據(jù)，則將當(dāng)前數(shù)據(jù)放在鏈表的最前，則將現(xiàn)有值放入鏈表中，
//返回新增對象，此值如果已存在，則返回鏈表中這個(gè)值對應(yīng)的key-value
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//否則循環(huán)判斷，將node放入節(jié)點(diǎn)中
for (int binCount = 0; ; ++binCount) {
//如果當(dāng)前位置只有一個(gè)元素，則修改當(dāng)前位置為鏈表結(jié)構(gòu)，將key-value放到鏈表最前
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果hash值相同，且key值相同，不進(jìn)行處理，跳出處理程序
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//下移一位，繼續(xù)判斷
p = e;
}
}
//如果在上述的判斷中，一個(gè)是hash值找到的位置上已經(jīng)有元素，且key值相同，
//或者找到位置已經(jīng)是鏈表數(shù)據(jù)，獲取到key對應(yīng)的key-value節(jié)點(diǎn)，則進(jìn)行如下判斷
if (e != null) { // existing mapping for key
V oldValue = e.value;//獲取當(dāng)前位置原有值
//如果允許覆蓋修改，或者當(dāng)前位置原有的值為null，則直接修改當(dāng)前位置的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;//返回原有值
}
}
++modCount;
if (++size > threshold)//如果HashMap大小已經(jīng)超過長度*加載因子，則重新計(jì)算長度
resize();
afterNodeInsertion(evict);
return null;
}
我們 用一張圖片來演示一下存儲(chǔ)過程
- 當(dāng)put鍵值對
[null, V]時(shí)，計(jì)算null的hash值得知在數(shù)組中位置為0- 如果位置0處沒有任何對象，則直接將
[null, V]存放在位置0處 - 如果位置0處已有對象，則直接使用新的值
V修改原有對象的值
- 如果位置0處沒有任何對象，則直接將
- 當(dāng)put鍵值對
[S, V]時(shí)，我們假設(shè)key值S和s的hash值相同，則在數(shù)組中對應(yīng)的位置相同
我們比較已有值的key同新put的key進(jìn)行比較，不相等，則將新的值插入到原有數(shù)據(jù)之前，形成鏈表結(jié)構(gòu) - 當(dāng)put鍵值對
[m, V]時(shí)，如果計(jì)算key的hash值，得到數(shù)組中對應(yīng)位置上沒有元素，則直接將[m, V]放到位置上。 - 當(dāng)put鍵值對
[K, V]時(shí)，原有位置已有元素，且key值相同，則直接使用新的值V覆蓋原有值
上述代碼中有兩個(gè)變量很重要，分別為size和threshold - size 已有對象數(shù)量
- threshold 當(dāng)前HashMap所能容納對象的極限數(shù)量，值為當(dāng)前HashMap容量*負(fù)載因子，如果容量就回觸發(fā)重新設(shè)置HashMap大小的算法
HashMap提供三個(gè)構(gòu)造方法，分別為
- public HashMap() 生成長度默認(rèn)16，負(fù)載因子默認(rèn)為0.75的HashMap
- public HashMap(int initialCapacity) 生成長度為initialCapacity，負(fù)載因子默認(rèn)為0.75的HashMap
- public HashMap(int initialCapacity, float loadFactor) 生成長度為initialCapacity，負(fù)載因子為loadFactor的HashMap
構(gòu)造方法源碼為
public HashMap(int initialCapacity, float loadFactor) {
//如果設(shè)置的長度小于0，拋出異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果長度大于可設(shè)置的最大長度`2的30次方，1073741824`，則長度為最大長度
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果負(fù)載因子小于等于0，或者無法轉(zhuǎn)換為float類型，拋出異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
HashMap中的每一個(gè)key-value都是一個(gè)對象，包含四個(gè)屬性，hash值，key，value，下一個(gè)元素
HashMap元素的獲取
程序中，獲取元素，可以調(diào)用HashMap的get(Object key)方法，邏輯為根據(jù)給定的key，得到key的hash值，然后使用hash值計(jì)算得到在數(shù)組中的位置。
- 如果當(dāng)前位置沒有元素，直接返回null
- 如果當(dāng)前位置有元素，且key值相同，直接返回當(dāng)前位置元素
- 如果當(dāng)前位置為鏈表結(jié)構(gòu)，則使用順序循環(huán)遍歷鏈表的方法從中查詢出key值相同的對象返回
HashMap總結(jié)
HashMap底層將key-value作為一個(gè)整體來進(jìn)行處理，起整體就是一個(gè)Node對象。本質(zhì)上就是Node的數(shù)組，存儲(chǔ)值時(shí)使用key的hash值尋址存儲(chǔ)，讀取時(shí)根據(jù)key的hash值尋址讀取。因此，HashMap可以快速存取key-value，其實(shí)就是因?yàn)椴捎昧薻ey的hash值定位尋址的方式。
初始化HashMap時(shí)，需要指定負(fù)載因子，負(fù)載因子值得就是HashMap中數(shù)值存儲(chǔ)的密度，密度越大，占用內(nèi)存越大，根據(jù)hash值進(jìn)行尋址花費(fèi)的時(shí)間也就越多，而存儲(chǔ)和讀取都需要使用尋址，因此會(huì)降低運(yùn)行效率。如果負(fù)載因子設(shè)置過小，會(huì)使得密度降低，造成內(nèi)存空間浪費(fèi)。一般來說，我們無需修改HashMap的負(fù)載因子。
從源代碼中我們也可以看出，如果數(shù)組中已有對象個(gè)數(shù)超過最大承受極限，也就是數(shù)組長度*負(fù)載因子，則需要重新計(jì)算數(shù)組長度，這個(gè)過程會(huì)進(jìn)行數(shù)組內(nèi)已有所有元素的重新計(jì)算位置和拷貝，造成不必要的系統(tǒng)開銷。因此如果我們可以提前知道HashMap中元素的最大數(shù)量，可以根據(jù)需要設(shè)置到合適大小，避免重新計(jì)算。
HashSet
通過閱讀HashSet的源代碼，發(fā)現(xiàn)HashSet類的內(nèi)部就是使用HashMap。HashSet的構(gòu)造函數(shù)為：
public HashSet() {
map = new HashMap<>();
}
因此在HashSet內(nèi)部也是使用Hash值計(jì)算的方式?jīng)Q定集合元素的存放位置
這點(diǎn)可以從HashSet 和 HashMap 之間有很多相似之處，對于 HashSet 而言，系統(tǒng)采用 Hash決定集合元素的存儲(chǔ)位置，這樣可以保證能快速存、取集合元素；
