此文已由作者趙計剛授權網易雲社群釋出。
歡迎通路網易雲社群，了解更多網易技術産品營運經驗。
5.1、對于HashMap需要掌握以下幾點
- Map的建立：HashMap()
- 往Map中添加鍵值對：即put(Object key, Object value)方法
- 擷取Map中的單個對象：即get(Object key)方法
- 删除Map中的對象：即remove(Object key)方法
- 判斷對象是否存在于Map中：containsKey(Object key)
- 周遊Map中的對象：即keySet()，在實際中更常用的是增強型的for循環去做周遊
- Map中對象的排序：主要取決于所采取的排序算法
5.2、建構HashMap
源代碼：
一些屬性：
static final int DEFAULT_INITIAL_CAPACITY = 16; // 預設的初始化容量（必須是2的多少次方）
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大指定容量為2的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 預設的加載因子（用于resize）
transient Entry[] table;// Entry數組（數組容量必須是2的多少次方，若有必要會擴容resize）--這就是HashMap的底層資料結構
transient int size; // 該map中存放的key-value對個數，該個數決定了數組的擴容（而非table中的所占用的桶的個數來決定是否擴容）
// 擴容resize的條件:eg.capacity=16,load_factor=0.75,threshold=capacity*load_factor=12,即當該map中存放的key-value對個數size>=12時，就resize）
int threshold;
final float loadFactor; // 負載因子（用于resize）
transient volatile int modCount;// 标志位，用于辨別并發問題，主要用于疊代的快速失敗（在疊代過程中，如果發生了put（添加而不是更新的時候）、remove操作，該值發生變化，快速失敗） 注意：
- map中存放的key-value對個數size，該個數決定了數組的擴容（size>=threshold時，擴容），而非table中的所占用的桶的個數來決定是否擴容
- 标志位modCount采用volatile實作該變量的線程可見性（之後會在"Java并發"章節中去講）
- 數組中的桶，指的就是table[i]
- threshold預設為0.75，這是綜合時間和空間的使用率來考慮的，通常不要變，如果該值過大，可能會造成連結清單太長，導緻get、put等操作緩慢；如果太小，空間使用率不足。
無參構造器（也是當下最常用的構造器）
/**
* 初始化一個負載因子、resize條件和Entry數組
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;// 負載因子：0.75
threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//當該map中存放的key-value對個數size>=12時，就resize
table = new Entry[DEFAULT_INITIAL_CAPACITY];// 設定Entry數組容量為16
init();
} - init()為空方法
對于hashmap而言，還有兩個比較常用的構造器，一個雙參，一個單參。
/**
* 指定初始容量和負載因子
*/
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))//loadFactor<0或者不是一個值
throw new IllegalArgumentException("Illegal load factor:"+loadFactor);
/*
* 下邊的邏輯是找一個2的幾次方的數，該數剛剛大于initialCapacity
* eg.當指定initialCapacity為17，capacity就是32（2的五次方），而2的四次方（16）正好小于17
*/
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;// capacity = capacity<<1
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
/**
* 指定初始容量
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//調用上邊的雙參構造器
} - 利用上述兩個構造器構造出的數組容量不一定是指定的初始化容量，而是一個剛剛大于指定初始化容量的2的幾次方的一個值。
- 在實際使用中，若我們能預判所要存儲的元素的多少，最好使用上述的單參構造器來指定初始容量，這樣的話，就可以避免就來擴容時帶來的消耗（這一點與ArrayList一樣）
HashMap的底層資料結構是一個Entry[]，Entry是HashMap的一個内部類，源代碼如下：
static class Entry<K, V> implements Map.Entry<K, V> {
final K key; // 該Entry的key
V value; // 該Entry的value
Entry<K, V> next; // 該Entry的下一個Entry（hash沖突時，形成連結清單）
final int hash; // 該Entry的hash值
/**
* Creates new entry.
*/
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;
}
//為Entry設定新的value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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();
//在hashmap中可以存放null鍵和null值
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;
}
public final int hashCode() {
return (key == null ? 0 : key.hashCode())^(value == null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
} 注：這裡我去掉了兩個空方法。
- Entry是一個節點，在其中還儲存了下一個Entry的引用（用來解決put時的hash沖突問題），這樣的話，我們可以把hashmap看作是"一個連結清單數組"
- Entry類中的equals()方法會在get(Object key)中使用
5.3、put(Object key, Object value)
源代碼：
put(Object key, Object value)
/**
* 向map中添加新Entry
* 步驟：
* 1）HashMap可以添加null的key，key==null的Entry隻會放在table[0]中，但是table[0]不僅僅可以存放key==null的Entry
* 1.1、周遊table[0]中的Entry鍊，若有key==null的值就用新值覆寫舊值，并傳回舊值value，
* 1.2、若無，執行addEntry方法，用新的Entry替換掉原來舊的Entry指派給table[0]，而舊的Entry作為新的Entry的next，執行結束後，傳回null
* 2）添加key!=null的Entry時，
* 2.1、先計算key.hashCode()的hash值，
* 2.2、然後計算出将要放入的table的下标i，
* 2.3、之後周遊table[i]中的Entry鍊，若有相同key的值就用新值覆寫舊值，并傳回舊值value，
* 2.4、若無，執行addEntry方法，用新的Entry替換掉原來舊的Entry指派給table[i]，而舊的Entry作為新的Entry的next，執行結束後，傳回null
*/
public V put(K key, V value) {
/******************key==null******************/
if (key == null)
return putForNullKey(value); //将空key的Entry加入到table[0]中
/******************key!=null******************/
int hash = hash(key.hashCode()); //計算key.hashcode()的hash值，hash函數由hashmap自己實作
int i = indexFor(hash, table.length);//擷取将要存放的數組下标
/*
* for中的代碼用于：當hash值相同且key相同的情況下，使用新值覆寫舊值（其實就是修改功能）
*/
for (Entry<K, V> e = table[i]; e != null; e = e.next) {//注意：for循環在第一次執行時就會先判斷條件
Object k;
//hash值相同且key相同的情況下，使用新值覆寫舊值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
//e.recordAccess(this);
return oldValue;//傳回舊值
}
}
modCount++;
addEntry(hash, key, value, i);//增加一個新的Entry到table[i]
return null;//如果沒有與傳入的key相等的Entry，就傳回null
} 注意：該方法頭部的注釋寫明了整個put(Object key, Object value)的流程，非常重要
putForNullKey(V value)
/**
* 增加null的key到table[0]
*/
private V putForNullKey(V value) {
//周遊第一個數組元素table[0]中的所有Entry節點
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {//用新值覆寫舊值
V oldValue = e.value;
e.value = value;
//e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);//将新節點Entry加入到Entry[]中
return null;
} addEntry(int hash, K key, V value, int bucketIndex)
/**
* 添加新的Entry到table[bucketIndex]
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
/*
* 這裡可以看出，
* 1）新加入的Entry會放傳入連結頭，也就是說将來周遊的時候，最先加入map的反而是最後被周遊到的
* 2）采用的是Entry替換的方式
* 2.1、當添加第一個Entry1時，table[bucketIndex]==null，也就是說Entry1的下一個Entry為null（鍊尾），之後把table[bucketIndex] = Entry1
* 2.2、當添加第二個Entry2時，table[bucketIndex]==Entry1，也就是說Entry2的下一個Entry為Entry1，之後把table[bucketIndex] = Entry2
* 2.3、當添加第三個Entry3時，table[bucketIndex]==Entry2，也就是說Entry3的下一個Entry為Entry2，之後把table[bucketIndex] = Entry3
*/
Entry<K, V> e = table[bucketIndex];//新節點的下一個節點(當第一次在相應的數組位置放置元素時，table[bucketIndex]==null)
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
if (size++ >= threshold)//key-value對個數大于等于threshold
resize(2 * table.length);//擴容
} 注意：該方法頭部的注釋寫明了該方法的流程示例，可以自己畫個圖對比着了解
hash(int h)
/**
* hash函數，用于計算key.hashCode()的hash值
* Note: null的key的hash為0，放在table[0].
*/
static int hash(int h) {
//這樣的hash函數應該可以盡量将hash值打散
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
} 注意：在我們實際使用hashmap時，最好的情況是将key的hash值打散，使插入的這些Entry盡量落在不同的桶上（這樣做的主要目的是提高查詢效率），以上這個hash函數應該就是實作了這樣的功能，但是為什麼這樣的hash函數可以将hash值打散，求大神指點！！！
indexFor(int h, int length)
/**
* "按位與"來擷取數組下标
*/
static int indexFor(int h, int length) {
return h & (length - 1);
} 注意：hashmap始終将自己的桶保持在2的n次方，這是為什麼？indexFor這個方法解釋了這個問題。“這個方法非常巧妙，它通過h & (table.length -1)來得到該對象的儲存位，而HashMap底層數組的長度總是2的n次方，這是HashMap在速度上的優化。當length總是2的n次方時，h& (length-1)運算等價于對length取模，也就是h%length，但是&比%具有更高的效率”--http://tech.meituan.com/java-hashmap.html
說明：在上述的addEntry(int hash, K key, V value, int bucketIndex)方法中，我們可以看到，當為把新的Entry指派給table[i]後，會判斷map中的key-value對是不是已經大于等于擴容條件值threshold了，若是，則需要調用resize函數，對Entry數組進行擴容，擴為原來二倍。
resize(int newCapacity)
/**
* 擴容步驟：
* 1）數組擴容為原來容量（eg.16）的二倍
* 2）将舊數組中的所有Entry重新計算索引，加入新數組
* 3）将新數組的引用賦給舊數組
* 4）重新計算擴容臨界值threshold
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果舊的數組的容量為2的30次方（這種情況，不考慮了，如果真達到這樣的情況，性能下降的就不像話了）
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];//newCapacity==2*oldCapacity
transfer(newTable);//将舊數組中的所有Entry重新計算索引，加入新數組
table = newTable;//将新數組賦給就數組
threshold = (int) (newCapacity * loadFactor);//重新計算threshold
} transfer(Entry[] newTable)
jdk中的實作：
/**
* 将所有舊的數組中的所有Entry移動到新數組中去
*/
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {//周遊舊數組
Entry<K, V> e = src[j];//獲得頭節點
if (e != null) {
/*
* 這樣寫，若同時有其他線程還在通路這個元素，則通路不到了，這裡這樣寫，是考慮到多線程情況下，我們一般不會會用HashMap
* （檢視ConcurrentHashMap并未将舊數組的值置為null）
* 這裡将其置為null就友善gc回收
* 當然為了減小以上所說的影響，建議将src[j] = null;放在while循環結束後
*/
src[j] = null;
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];//把之前已經存在的newTable[i]的元素賦給目前節點的下一個節點
newTable[i] = e;//把目前節點賦給newTable[i]
e = next;
} while (e != null);//周遊連結清單
}
}
} 我的修改：（注意：這是一個錯誤的修改，錯誤的根源在下邊我會給出）
/**
* 将所有舊的數組中的所有Entry移動到新數組中去
*/
void transfer(Entry[] newTable) {
Entry[] src = table; //舊數組
int newCapacity = newTable.length; //新數組容量
for (int j = 0; j < src.length; j++) {
Entry<K, V> e = src[j];//擷取舊數組中的頭節點Entry
if (e != null) {
src[j] = null;//将舊數組置空，讓gc回收注意：這個時候table的桶并沒有置空
/*
* 根據舊的hash值與新的容量值進行重新定位（注意：并沒有重新計算hash值）
* 1、那麼假設之前table[1]中存放的是Entry3，Entry3.next是Entry2，Entry2.next是Entry1，Entry1.next是null
* 那麼假設重新計算後的i=3，那麼Entry3-->Entry2-->Entry1依舊會在一起，都放入newTable[3],這樣的話，我們隻需要将鍊頭的Entry3指派給newTable[3]即可
* 2、既然通過indexFor(e.hash, newCapacity)不能把同一個桶下的Entry打散，為什麼還要用呢？
* 主要是擴容後，若不用newCapacity去計算下标的話，那麼擴容後，map中的Entry就都集中在了新數組的前半部分，這樣就不夠散了
*/
int i = indexFor(e.hash, newCapacity);
newTable[i] = e;//将Entry3指派給newTable[3]
}
}
} - 在這個方法中，并沒有重新計算hash值，隻是重新計算了下标索引。
-
錯誤根源在于認為同一個桶下的所有Entry的hash值相同，事實上不相同，隻是hash&(table.length-1)的結果相同，
是以當table.length發生變化時，同一個桶下各個Entry算出來的index會不同（即Entry3、Entry2、Entry1可能會落在新數組的不同的桶上）
5.4、get(Object key)
get(Object key)
/**
* 查找指定key的value值
* 1、若key==null
* 周遊table[0]，找出key==null的value，若沒找到，傳回null
* 2、若key!=null
* 1）計算key.hashCode()的hash值
* 2）根據計算出的hash值和數組容量，調用indexFor方法，獲得table的下标i，進而獲得桶table[i]
* 3）周遊該桶中的每一個Entry，找出key相等（==或equals）的Entry，擷取此Entry的value即可
* 4）最後，若沒有找到，傳回null即可
*/
public V get(Object key) {
/****************查找key==null的value****************/
if (key == null)
return getForNullKey();
/****************查找key!=null的value****************/
int hash = hash(key.hashCode());//擷取key.hashCode()的hash值
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;//若沒有指定key的Entry，則直接傳回null
} 注意：檢視代碼頭部的注釋，表明了get的整個步驟
getForNullKey()
/**
* 在table[0]中查詢key==null
*/
private V getForNullKey() {
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;//找不到的話就傳回null
} 5.5、remove(Object key)
/**
* 删除指定key的Entry
*/
public V remove(Object key) {
Entry<K, V> e = removeEntryForKey(key);
return (e == null ? null : e.value);//傳回删除的節點（e為null的話，表示所給出的key不存在）
}
/**
* 删除指定key的Entry
* 1）若删除的是頭節點，例如Entry3，隻需将Entry2指派給table[i]即可
* 2）若删除的是中間節點，例如Entry2，隻需将Entry3.next指向Entry2.next（即Entry1）即可
* 3）若删除的是尾節點，例如Entry1，隻需将Entry2.next指向Entry1.next（即null）即可
*/
final Entry<K, V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());//計算hash值
int i = indexFor(hash, table.length);//按位與計算下标
Entry<K, V> prev = table[i];//擷取桶
Entry<K, V> e = prev;
while (e != null) {
Entry<K, V> next = e.next;
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;//size-1
if (prev == e)//删除頭節點，即示例中的Entry3
table[i] = next;
else//删除除了頭節點外的其他節點
prev.next = next;
//e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;//傳回删除的節點（e為null的話，表示所給出的key不存在）
} 注：看注釋即可，最好用示例去套一下代碼。
- 若删除的key不存在于map中，傳回null，不會抛異常。
5.6、containsKey(Object key)
/**
* 判斷map是否包含指定可以的Entry
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
* 判斷map是否包含指定可以的Entry，與get(Object key)基本相同（隻是這裡将key==null與key!=null的情況寫在了一起，get(Object key)也可以這樣去做）
* 1）計算key.hashCode()的hash值
* 2）根據計算出的hash值和數組容量，調用indexFor方法，獲得table的下标i，進而獲得桶table[i]
* 3）周遊該桶中的每一個Entry，找出key相等（==或equals）的Entry，擷取此Entry，并傳回此Entry
* 4）最後，若沒有找到，傳回null即可
*/
final Entry<K, V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());//計算hash值
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;
} 注意：此方法與get(Object key)基本相同，隻是隻是這裡将key==null與key!=null的情況寫在了一起，get(Object key)也可以這樣去做來減少代碼
5.7、keySet()
周遊所有Entry連結清單，擷取每一個Entry的key，在整個過程中，如果發生了增删操作，抛出ConcurrentModificationException。
final Entry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K, V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
} 總結：
- HashMap底層就是一個Entry數組，Entry又包含next，事實上，可以看成是一個"連結清單數組"
- 擴容：map中存放的key-value對個數size，該個數決定了數組的擴容（size>=threshold時，擴容），而非table中的所占用的桶的個數來決定是否擴容
- 擴容過程，不會重新計算hash值，隻會重新按位與
- 在實際使用中，若我們能預判所要存儲的元素的多少，最好使用上述的單參構造器來指定初始容量
- HashMap可以插入null的key和value
- remove(Object key)：若删除的key不存在于map中，傳回null，不會抛異常。
- HashMap線程不安全，若想要線程安全，最好使用ConcurrentHashMap
疑問：
在我們實際使用hashmap時，最好的情況是将key的hash值打散，使插入的這些Entry盡量落在不同的桶上（這樣做的主要目的是提高查詢效率），以下這個hash函數應該就是實作了這樣的功能，但是為什麼這樣的hash函數可以将hash值打散，求大神指點！！！
static int hash(int h) {
//這樣的hash函數應該可以盡量将hash值打散
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
} jdk1.8對hashmap進行了改造，1.7中的hashmap最大的問題就是當連結清單比較長時，查詢效率急劇下降；是以在1.8中，當連結清單長度>=8是，連結清單轉為紅黑樹，提高查詢效率。
免費領取驗證碼、内容安全、短信發送、直播點播體驗包及雲伺服器等套餐
更多網易技術、産品、營運經驗分享請點選。
相關文章：
【推薦】 如何學習、了解Kubernetes？
【推薦】 Android TV Overscan
![java HashMap 與HashTable的差別[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)