Java集合：HashMap源碼剖析(xi)
一、HashMap概述
二、HashMap的數據結構
三、HashMap源碼分析
1、關鍵屬性
2、構造方法
3、存儲數據
4、調整大小
一、HashMap概述
HashMap基于哈希表的 Map 接口的實現。此實現提供所有可選的映射操作，并允許使用 null 值和 null 鍵。（除了不同(tong)(tong)步和允許使用 null 之外，HashMap 類與(yu) Hashtable 大(da)致(zhi)相同(tong)(tong)。）此類不保證映射的順序，特別是它不保證該順序恒久不變。
值(zhi)得(de)(de)注意的是(shi)(shi)HashMap不是(shi)(shi)線(xian)程安全(quan)的，如果(guo)想(xiang)要線(xian)程安全(quan)的HashMap，可以通過Collections類(lei)的靜態(tai)方(fang)法synchronizedMap獲(huo)得(de)(de)線(xian)程安全(quan)的HashMap。
Map map = Collections.synchronizedMap(new HashMap());
二、HashMap的數據結構
HashMap的底層主要是基于數(shu)組和鏈表來實現的，它之所以有相當快的查詢速度主要是因為它是通過計(ji)算散列碼來(lai)決定存儲的位置。HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同，計算出來的hash值就一樣。如果存儲的對象對多了，就有可能不同的對象所算出來的hash值是相同的，這就出現了所謂的hash沖突。學過數據結構的同學都知道，解決hash沖突的方法有很多，HashMap底層是通過鏈表來解決hash沖突的。
圖中(zhong)(zhong)，0~15部分即代表哈(ha)(ha)希(xi)表，也(ye)稱為哈(ha)(ha)希(xi)數組，數組的(de)(de)(de)每個元(yuan)素都(dou)是一個單鏈表的(de)(de)(de)頭節點，鏈表是用來解決(jue)沖突的(de)(de)(de)，如(ru)果(guo)不(bu)同的(de)(de)(de)key映(ying)射到了數組的(de)(de)(de)同一位置(zhi)處，就將(jiang)其放入單鏈表中(zhong)(zhong)。
我們看看HashMap中(zhong)Entry類的代碼：
/** Entry是單向鏈表。
* 它是 “HashMap鏈式(shi)存儲(chu)法”對應的鏈表。
*它實現了Map.Entry 接口，即實現getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數
**/
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
// 指向(xiang)下(xia)一個節(jie)點(dian)
Entry<K,V> next;
final int hash;
// 構造函數。
// 輸入參數包括"哈希值(h)", "鍵(k)", "值(v)", "下(xia)一節點(n)"
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判斷兩個Entry是(shi)否相等(deng)
// 若兩(liang)個Entry的“key”和“value”都相等，則返回true。
// 否則，返回false
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
// 實現hashCode()
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
// 當向(xiang)HashMap中添加元(yuan)素時，繪調(diao)用recordAccess()。
// 這(zhe)里不做任(ren)何處理
void recordAccess(HashMap<K,V> m) {
}
// 當從(cong)HashMap中刪除元素時(shi)，繪調用recordRemoval()。
// 這里不做任何(he)處理
void recordRemoval(HashMap<K,V> m) {
}
}
HashMap其實就是(shi)一個(ge)Entry數組，Entry對(dui)象中(zhong)包含了(le)鍵和值，其中(zhong)next也是(shi)一個(ge)Entry對(dui)象，它就是(shi)用來處理hash沖突的(de)，形成一個(ge)鏈表。
三、HashMap源碼分析
1、關鍵屬性
先看看HashMap類(lei)中的一些關鍵屬性：
transient Entry[] table;//存儲(chu)元素(su)的實體(ti)數組
transient int size;//存(cun)放元素的個數
int threshold; //臨(lin)界值 當(dang)實際大小超過臨(lin)界值時，會進行(xing)擴容(rong)threshold = 加載因子(zi)*容(rong)量
final float loadFactor; //加載(zai)因子(zi)
transient int modCount;//被修改的次數
其中loadFactor加載因子是表示Hsah表中元素的填(tian)滿的程度.
若:加(jia)載因(yin)子(zi)越大,填滿的元素(su)越多(duo),好處(chu)是,空間利用(yong)率高(gao)了(le),但:沖突的機會加(jia)大了(le).鏈表長度會越來越長,查找效率降低。
反之,加(jia)載因子越小(xiao),填滿的元素(su)越少,好(hao)處是(shi):沖突(tu)的機會(hui)減小(xiao)了(le),但(dan):空間(jian)浪費多了(le).表(biao)中(zhong)的數據將過于稀疏（很多空間(jian)還沒用，就開始擴容了(le)）
沖突的機會越(yue)大(da),則查找的成本越(yue)高.
因(yin)此,必須在 "沖突的(de)機會(hui)"與"空(kong)間利用率"之間尋找一種平衡與折衷. 這種平衡與折衷本質(zhi)上是數(shu)據結構中有名的(de)"時-空(kong)"矛盾的(de)平衡與折衷.
如果機器內存足夠，并且想要提高查詢速度的話可以將加載因子設置小一點；相反如果機器內存緊張，并且對查詢速度沒有什么要求的話可以將加載因子設置大一點。不過一般我們都不用去設置它，讓它取默認(ren)值0.75就好了。
2、構造方法
下面看看HashMap的幾個構造方法：
public HashMap(int initialCapacity, float loadFactor) {
//確(que)保(bao)數字(zi)合法
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);
// Find a power of 2 >= initialCapacity
int capacity = 1; //初始(shi)容量
while (capacity < initialCapacity) //確保容(rong)量為(wei)2的(de)(de)(de)n次(ci)(ci)冪(mi)，使capacity為(wei)大于initialCapacity的(de)(de)(de)最(zui)小(xiao)的(de)(de)(de)2的(de)(de)(de)n次(ci)(ci)冪(mi)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
我(wo)們可以看到在構造(zao)HashMap的(de)時候(hou)如果我(wo)們指定了加載因子和初(chu)始容(rong)(rong)(rong)量(liang)(liang)的(de)話就(jiu)調(diao)用第一個(ge)構造(zao)方法(fa)，否則(ze)的(de)話就(jiu)是用默(mo)認的(de)。默(mo)認初(chu)始容(rong)(rong)(rong)量(liang)(liang)為(wei)16，默(mo)認加載因子為(wei)0.75。我(wo)們可以看到上面代碼(ma)中13-15行，這段代碼(ma)的(de)作用是確(que)保容(rong)(rong)(rong)量(liang)(liang)為(wei)2的(de)n次冪(mi)，使capacity為(wei)大于initialCapacity的(de)最小(xiao)的(de)2的(de)n次冪(mi)，至于為(wei)什么要把容(rong)(rong)(rong)量(liang)(liang)設置為(wei)2的(de)n次冪(mi)，我(wo)們等(deng)下(xia)再看。
重(zhong)點分析下HashMap中(zhong)用的(de)最多的(de)兩個方法(fa)put和get
3、存儲數據
下(xia)面看(kan)看(kan)HashMap存儲數(shu)據的(de)過(guo)程是怎(zen)樣(yang)的(de)，首先(xian)看(kan)看(kan)HashMap的(de)put方(fang)法(fa)：
public V put(K key, V value) {
// 若“key為null”，則(ze)將(jiang)該鍵值(zhi)對添加(jia)到table[0]中。
if (key == null)
return putForNullKey(value);
// 若“key不為(wei)null”，則(ze)計算(suan)該key的哈(ha)希值(zhi)，然后將其(qi)添加到該哈(ha)希值(zhi)對應(ying)的鏈表中。
int hash = hash(key.hashCode());
//搜(sou)索指定hash值在對應table中的(de)索引(yin)
int i = indexFor(hash, table.length);
// 循環遍(bian)歷Entry數(shu)組,若“該key”對(dui)應的鍵值(zhi)對(dui)已(yi)經存在，則用(yong)新(xin)的value取(qu)代舊的value。然后退出(chu)！
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))) { //如果key相同(tong)則覆蓋并返回舊值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//修改次數+1
modCount++;
//將key-value添加(jia)到table[i]處
addEntry(hash, key, value, i);
return null;
}
上面(mian)程(cheng)序(xu)中用到了(le)一個重要的(de)(de)內部(bu)接口：Map.Entry，每個 Map.Entry 其實就是一個 key-value 對(dui)(dui)。從上面(mian)程(cheng)序(xu)中可以(yi)看出：當(dang)系統決(jue)定(ding)存儲 HashMap 中的(de)(de) key-value 對(dui)(dui)時(shi)，完全沒有考(kao)慮 Entry 中的(de)(de) value，僅(jin)僅(jin)只是根據 key 來計算(suan)并決(jue)定(ding)每個 Entry 的(de)(de)存儲位(wei)置。這也說明了(le)前面(mian)的(de)(de)結(jie)論：我們完全可以(yi)把 Map 集合(he)中的(de)(de) value 當(dang)成 key 的(de)(de)附屬，當(dang)系統決(jue)定(ding)了(le) key 的(de)(de)存儲位(wei)置之后，value 隨之保(bao)存在那里即可。
我們慢慢的(de)(de)來分(fen)析這個(ge)函數，第2和3行(xing)的(de)(de)作(zuo)用就(jiu)是處理key值(zhi)為null的(de)(de)情況，我們看(kan)看(kan)putForNullKey(value)方法：
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) { //如果有key為null的對象存在，則覆蓋(gai)掉
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0); //如果鍵(jian)為null的話(hua)，則(ze)hash值為0
return null;
}
注意：如果key為null的話(hua)，hash值(zhi)為0，對象(xiang)存儲在數組(zu)中索(suo)引為0的位置。即(ji)table[0]
我(wo)們再回(hui)去看看put方(fang)法(fa)中第4行，它是通過key的hashCode值計算hash碼(ma)，下面(mian)是計算hash碼(ma)的函數：
//計算hash值的方法 通過(guo)鍵的hashCode來計算
static int hash(int h) {
// 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).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
得到(dao)hash碼之后就會通過hash碼去(qu)計(ji)(ji)算出(chu)應該存儲在數組中的索(suo)引(yin)(yin)，計(ji)(ji)算索(suo)引(yin)(yin)的函數如(ru)下(xia)：
static int indexFor(int h, int length) { //根據hash值(zhi)(zhi)和數組(zu)長度算出索引值(zhi)(zhi)
return h & (length-1); //這里不(bu)能(neng)隨(sui)便算(suan)取(qu)，用hash&(length-1)是(shi)有原因的，這樣(yang)可以確保算(suan)出來(lai)的索引(yin)是(shi)在數組大小范圍內，不(bu)會(hui)超出
}
這(zhe)個我(wo)們要(yao)重點說(shuo)下，我(wo)們一(yi)般(ban)對哈希(xi)表的(de)(de)散列(lie)很(hen)自然地會(hui)想到用hash值對length取(qu)模(mo)（即除(chu)法(fa)(fa)散列(lie)法(fa)(fa)），Hashtable中(zhong)也是這(zhe)樣(yang)實(shi)現的(de)(de)，這(zhe)種方(fang)法(fa)(fa)基本(ben)能保證元素在哈希(xi)表中(zhong)散列(lie)的(de)(de)比較均(jun)勻，但取(qu)模(mo)會(hui)用到除(chu)法(fa)(fa)運算，效率(lv)很(hen)低，HashMap中(zhong)則通過h&(length-1)的(de)(de)方(fang)法(fa)(fa)來(lai)代替取(qu)模(mo)，同樣(yang)實(shi)現了均(jun)勻的(de)(de)散列(lie)，但效率(lv)要(yao)高很(hen)多，這(zhe)也是HashMap對Hashtable的(de)(de)一(yi)個改進。
接下來，我們分析下為(wei)什么哈希表(biao)的(de)容(rong)量一定要是(shi)2的(de)整數(shu)(shu)(shu)(shu)次(ci)(ci)冪(mi)。首先，length為(wei)2的(de)整數(shu)(shu)(shu)(shu)次(ci)(ci)冪(mi)的(de)話，h&(length-1)就相當于對(dui)length取(qu)模，這(zhe)(zhe)(zhe)樣(yang)便(bian)(bian)保證了(le)散(san)列(lie)(lie)的(de)均(jun)(jun)勻，同時也提升(sheng)了(le)效率；其次(ci)(ci)，length為(wei)2的(de)整數(shu)(shu)(shu)(shu)次(ci)(ci)冪(mi)的(de)話，為(wei)偶(ou)數(shu)(shu)(shu)(shu)，這(zhe)(zhe)(zhe)樣(yang)length-1為(wei)奇(qi)數(shu)(shu)(shu)(shu)，奇(qi)數(shu)(shu)(shu)(shu)的(de)最(zui)后(hou)一位(wei)(wei)是(shi)1，這(zhe)(zhe)(zhe)樣(yang)便(bian)(bian)保證了(le)h&(length-1)的(de)最(zui)后(hou)一位(wei)(wei)可(ke)能(neng)(neng)為(wei)0，也可(ke)能(neng)(neng)為(wei)1（這(zhe)(zhe)(zhe)取(qu)決于h的(de)值(zhi)），即(ji)與(yu)后(hou)的(de)結果可(ke)能(neng)(neng)為(wei)偶(ou)數(shu)(shu)(shu)(shu)，也可(ke)能(neng)(neng)為(wei)奇(qi)數(shu)(shu)(shu)(shu)，這(zhe)(zhe)(zhe)樣(yang)便(bian)(bian)可(ke)以保證散(san)列(lie)(lie)的(de)均(jun)(jun)勻性，而如果length為(wei)奇(qi)數(shu)(shu)(shu)(shu)的(de)話，很明顯length-1為(wei)偶(ou)數(shu)(shu)(shu)(shu)，它的(de)最(zui)后(hou)一位(wei)(wei)是(shi)0，這(zhe)(zhe)(zhe)樣(yang)h&(length-1)的(de)最(zui)后(hou)一位(wei)(wei)肯定為(wei)0，即(ji)只(zhi)(zhi)能(neng)(neng)為(wei)偶(ou)數(shu)(shu)(shu)(shu)，這(zhe)(zhe)(zhe)樣(yang)任何hash值(zhi)都只(zhi)(zhi)會(hui)被散(san)列(lie)(lie)到數(shu)(shu)(shu)(shu)組的(de)偶(ou)數(shu)(shu)(shu)(shu)下標位(wei)(wei)置(zhi)上，這(zhe)(zhe)(zhe)便(bian)(bian)浪費了(le)近一半的(de)空間(jian)，因此，length取(qu)2的(de)整數(shu)(shu)(shu)(shu)次(ci)(ci)冪(mi)，是(shi)為(wei)了(le)使不(bu)同hash值(zhi)發生碰撞的(de)概率較(jiao)小，這(zhe)(zhe)(zhe)樣(yang)就能(neng)(neng)使元(yuan)素在哈希表(biao)中均(jun)(jun)勻地散(san)列(lie)(lie)。
這(zhe)看(kan)上(shang)去(qu)很簡單，其實比較有玄機(ji)的，我們舉個例子來說明：
假設數組長度分別為15和16，優化后的hash碼分別為8和9，那么&運算后的結果如下：
h & (table.length-1) hash table.length-1 8 & (15-1)： 1000 & 1110 = 1000 9 & (15-1)： 1001 & 1110 = 1000 ----------------------------------------------------------------------------------------------------------------------- 8 & (16-1)： 1000 & 1111 = 1000 9 & (16-1)： 1001 & 1111 = 1001
從(cong)上面的例子中可以看(kan)出：
當(dang)(dang)它們和(he)15-1（1110）“與(yu)”的(de)(de)(de)(de)時(shi)候(hou)(hou)，產(chan)生了(le)相(xiang)同(tong)的(de)(de)(de)(de)結果，也就是(shi)(shi)說它們會定位(wei)到(dao)數(shu)(shu)組(zu)中的(de)(de)(de)(de)同(tong)一(yi)(yi)(yi)(yi)個(ge)位(wei)置上去，這(zhe)就產(chan)生了(le)碰(peng)(peng)撞，8和(he)9會被放(fang)到(dao)數(shu)(shu)組(zu)中的(de)(de)(de)(de)同(tong)一(yi)(yi)(yi)(yi)個(ge)位(wei)置上形成(cheng)鏈(lian)表，那(nei)(nei)么查詢(xun)的(de)(de)(de)(de)時(shi)候(hou)(hou)就需(xu)要遍歷這(zhe)個(ge)鏈(lian)表，得到(dao)8或者9，這(zhe)樣就降低(di)了(le)查詢(xun)的(de)(de)(de)(de)效率。同(tong)時(shi)，我(wo)們也可以發現(xian)，當(dang)(dang)數(shu)(shu)組(zu)長度為(wei)15的(de)(de)(de)(de)時(shi)候(hou)(hou)，hash值會與(yu)15-1（1110）進行“與(yu)”，那(nei)(nei)么 最后一(yi)(yi)(yi)(yi)位(wei)永遠(yuan)是(shi)(shi)0，而0001，0011，0101，1001，1011，0111，1101這(zhe)幾個(ge)位(wei)置永遠(yuan)都不能(neng)存(cun)放(fang)元素了(le)，空間浪費相(xiang)當(dang)(dang)大，更糟的(de)(de)(de)(de)是(shi)(shi)這(zhe)種情況中，數(shu)(shu)組(zu)可以使用的(de)(de)(de)(de)位(wei)置比數(shu)(shu)組(zu)長度小了(le)很多，這(zhe)意(yi)味著(zhu)進一(yi)(yi)(yi)(yi)步增加了(le)碰(peng)(peng)撞的(de)(de)(de)(de)幾率，減慢了(le)查詢(xun)的(de)(de)(de)(de)效率！
而當(dang)數(shu)組長度為(wei)16時(shi)(shi)，即為(wei)2的(de)(de)n次(ci)方時(shi)(shi)，2n-1得到的(de)(de)二(er)進(jin)制數(shu)的(de)(de)每(mei)個位上的(de)(de)值都(dou)為(wei)1，這使得在低(di)位上&時(shi)(shi)，得到的(de)(de)和原hash的(de)(de)低(di)位相同，加之hash(int h)方法對key的(de)(de)hashCode的(de)(de)進(jin)一步(bu)優(you)化(hua)，加入了高位計算，就使得只有(you)相同的(de)(de)hash值的(de)(de)兩個值才會(hui)被放到數(shu)組中的(de)(de)同一個位置(zhi)上形成鏈(lian)表(biao)。
所以說，當數組(zu)長度(du)為2的(de)(de)n次冪的(de)(de)時候(hou)(hou)，不同的(de)(de)key算得得index相同的(de)(de)幾(ji)率(lv)(lv)較小，那(nei)么(me)數據在數組(zu)上分布就(jiu)比較均勻(yun)，也就(jiu)是說碰撞(zhuang)的(de)(de)幾(ji)率(lv)(lv)小，相對的(de)(de)，查詢(xun)的(de)(de)時候(hou)(hou)就(jiu)不用遍歷(li)某個(ge)位(wei)置(zhi)上的(de)(de)鏈表，這樣查詢(xun)效率(lv)(lv)也就(jiu)較高了。
; 根據上面(mian) put 方法的(de)(de)源代碼可以看出(chu)，當程序(xu)(xu)試圖(tu)將一(yi)個key-value對放(fang)入HashMap中時，程序(xu)(xu)首先根據該 key 的(de)(de) hashCode() 返(fan)回(hui)值決定該 Entry 的(de)(de)存儲位置：
- 如果兩個 Entry 的 key 的 hashCode() 返回(hui)值相(xiang)同，那它們的存儲位(wei)置(zhi)相(xiang)同。
- 如果(guo)這(zhe)兩個 Entry 的 key 通過 equals 比較返(fan)回 true，新添加 Entry 的 value 將覆(fu)蓋(gai)(gai)集合(he)中原有 Entry 的 value，但key不會(hui)覆(fu)蓋(gai)(gai)。
- 如果(guo)這兩個 Entry 的(de) key 通(tong)過 equals 比較返回 false，新添加的(de) Entry 將與集合中原有 Entry 形成(cheng) Entry 鏈，而且新添加的(de) Entry 位于 Entry 鏈的(de)頭部——
具(ju)體說(shuo)明繼續看 addEntry() 方法的說(shuo)明。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex]; //如果要加入(ru)的(de)位(wei)置(zhi)(zhi)有值(zhi)，將(jiang)該位(wei)置(zhi)(zhi)原先(xian)的(de)值(zhi)設置(zhi)(zhi)為新entry的(de)next,也就是新entry鏈(lian)表(biao)的(de)下一個節點
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold) //如果大于臨界值就擴容(rong)
resize(2 * table.length); //以(yi)2的(de)倍數擴容
}
參數(shu)bucketIndex就(jiu)是indexFor函(han)數(shu)計(ji)算出來的(de)索引值(zhi)，第(di)2行代碼是取得數(shu)組中索引為bucketIndex的(de)Entry對(dui)(dui)象，第(di)3行就(jiu)是用(yong)hash、key、value構(gou)建一(yi)個新(xin)的(de)Entry對(dui)(dui)象放到索引為bucketIndex的(de)位(wei)置，并且將該位(wei)置原先(xian)的(de)對(dui)(dui)象設置為新(xin)對(dui)(dui)象的(de)next構(gou)成鏈(lian)表。
第4行和第5行就(jiu)是(shi)(shi)判斷(duan)put后size是(shi)(shi)否達到了臨界值threshold，如果(guo)達到了臨界值就(jiu)要(yao)進行擴容，HashMap擴容是(shi)(shi)擴為原來的兩(liang)倍(bei)。
4、調整大小
resize()方法(fa)如下(xia)：
重新調(diao)整HashMap的(de)大小，newCapacity是調(diao)整后的(de)單位
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);//用來將原先table的元素全部移到(dao)newTable里面(mian)
table = newTable; //再將newTable賦值給table
threshold = (int)(newCapacity * loadFactor);//重(zhong)新計算臨界值(zhi)
}
新(xin)建了一個(ge)HashMap的(de)底層數組(zu)，上面代碼中第(di)10行為調用transfer方法，將HashMap的(de)全部元(yuan)素添加到(dao)新(xin)的(de)HashMap中,并重新(xin)計算元(yuan)素在新(xin)的(de)數組(zu)中的(de)索引位置(zhi)
當HashMap中的元素越來越多的時候，hash沖突的幾率也就越來越高，因為數組的長度是固定的。所以為了提高查詢的效率，就要對HashMap的數組進行擴容，數組擴容這個操作也會出現在ArrayList中，這是一個常用的操作，而在HashMap數組擴容之后，最消耗性能的點就出現了：原數(shu)(shu)組中(zhong)的數(shu)(shu)據必須(xu)重新(xin)計算其(qi)在新(xin)數(shu)(shu)組中(zhong)的位(wei)置(zhi)，并(bing)放(fang)進去，這就(jiu)是(shi)resize。
那(nei)么(me)HashMap什么(me)時(shi)(shi)候進(jin)(jin)行(xing)擴(kuo)(kuo)(kuo)容(rong)呢？當(dang)HashMap中的(de)(de)(de)元(yuan)素(su)(su)(su)個(ge)(ge)(ge)數(shu)(shu)超過(guo)數(shu)(shu)組(zu)(zu)(zu)大小*loadFactor時(shi)(shi)，就會進(jin)(jin)行(xing)數(shu)(shu)組(zu)(zu)(zu)擴(kuo)(kuo)(kuo)容(rong)，loadFactor的(de)(de)(de)默認值為0.75，這(zhe)是(shi)一個(ge)(ge)(ge)折中的(de)(de)(de)取值。也就是(shi)說，默認情況下，數(shu)(shu)組(zu)(zu)(zu)大小為16，那(nei)么(me)當(dang)HashMap中元(yuan)素(su)(su)(su)個(ge)(ge)(ge)數(shu)(shu)超過(guo)16*0.75=12的(de)(de)(de)時(shi)(shi)候，就把數(shu)(shu)組(zu)(zu)(zu)的(de)(de)(de)大小擴(kuo)(kuo)(kuo)展為 2*16=32，即擴(kuo)(kuo)(kuo)大一倍，然后重新計算每(mei)個(ge)(ge)(ge)元(yuan)素(su)(su)(su)在數(shu)(shu)組(zu)(zu)(zu)中的(de)(de)(de)位置，擴(kuo)(kuo)(kuo)容(rong)是(shi)需要(yao)進(jin)(jin)行(xing)數(shu)(shu)組(zu)(zu)(zu)復制的(de)(de)(de)，復制數(shu)(shu)組(zu)(zu)(zu)是(shi)非常消耗性能的(de)(de)(de)操作(zuo)，所(suo)以如果我們已(yi)經預知HashMap中元(yuan)素(su)(su)(su)的(de)(de)(de)個(ge)(ge)(ge)數(shu)(shu)，那(nei)么(me)預設元(yuan)素(su)(su)(su)的(de)(de)(de)個(ge)(ge)(ge)數(shu)(shu)能夠有效的(de)(de)(de)提高HashMap的(de)(de)(de)性能。
5、數據讀取
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
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.equals(k)))
return e.value;
}
return null;
}
有了(le)上面存(cun)儲(chu)時的(de)hash算法作(zuo)為基礎(chu)，理解起(qi)來這段代(dai)碼(ma)就很(hen)容(rong)易了(le)。從(cong)上面的(de)源代(dai)碼(ma)中可以(yi)看(kan)出：從(cong)HashMap中get元(yuan)素時，首先計算key的(de)hashCode，找(zhao)到(dao)(dao)數(shu)組中對應位(wei)置(zhi)的(de)某一元(yuan)素，然后通過key的(de)equals方法在對應位(wei)置(zhi)的(de)鏈(lian)表中找(zhao)到(dao)(dao)需要(yao)的(de)元(yuan)素。
6、HashMap的性能參數：
HashMap 包含如下幾個構造器：
HashMap()：構建一個初(chu)始容量(liang)為 16，負載因(yin)子為 0.75 的 HashMap。
HashMap(int initialCapacity)：構建一個初始容(rong)量為(wei)(wei) initialCapacity，負載因子為(wei)(wei) 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定(ding)初始容(rong)量、指定(ding)的(de)負載因子創建一(yi)個 HashMap。
HashMap的基(ji)礎(chu)構造器HashMap(int initialCapacity, float loadFactor)帶(dai)有兩個(ge)參數(shu)，它們是初始容量initialCapacity和加載因子loadFactor。
initialCapacity：HashMap的最大容量，即為底層(ceng)數組的長度(du)。
loadFactor：負(fu)載因子loadFactor定義為：散(san)列表的實際元素數目(n)/ 散(san)列表的容量(m)。
負(fu)(fu)載(zai)因(yin)子衡量的(de)(de)是一(yi)個(ge)散(san)列(lie)表(biao)(biao)的(de)(de)空間(jian)(jian)的(de)(de)使用程(cheng)度(du)，負(fu)(fu)載(zai)因(yin)子越大(da)表(biao)(biao)示散(san)列(lie)表(biao)(biao)的(de)(de)裝(zhuang)填程(cheng)度(du)越高，反之愈小。對(dui)(dui)于使用鏈表(biao)(biao)法的(de)(de)散(san)列(lie)表(biao)(biao)來(lai)說，查找(zhao)一(yi)個(ge)元素的(de)(de)平均時間(jian)(jian)是O(1+a)，因(yin)此如果(guo)負(fu)(fu)載(zai)因(yin)子越大(da)，對(dui)(dui)空間(jian)(jian)的(de)(de)利(li)用更充分(fen)，然而后果(guo)是查找(zhao)效率(lv)的(de)(de)降低(di)；如果(guo)負(fu)(fu)載(zai)因(yin)子太(tai)小，那(nei)么散(san)列(lie)表(biao)(biao)的(de)(de)數據將過于稀疏，對(dui)(dui)空間(jian)(jian)造成嚴重浪費(fei)。
HashMap的實(shi)現(xian)中，通過(guo)threshold字段來判斷HashMap的最大容量：
threshold = (int)(capacity * loadFactor);
結合負(fu)載因子的(de)定義公式(shi)可知，threshold就是(shi)(shi)在(zai)此loadFactor和(he)(he)capacity對應下允許(xu)的(de)最(zui)大(da)元素數目(mu)，超過這個(ge)數目(mu)就重新resize，以降低實際的(de)負(fu)載因子。默認的(de)的(de)負(fu)載因子0.75是(shi)(shi)對空間和(he)(he)時間效率(lv)的(de)一個(ge)平衡(heng)選擇。當容(rong)量(liang)超出此最(zui)大(da)容(rong)量(liang)時， resize后的(de)HashMap容(rong)量(liang)是(shi)(shi)容(rong)量(liang)的(de)兩(liang)倍：