1 概述
HashMap 是 Java Collection Framework的重要成員撩荣，也是Map接口最常用的實(shí)現(xiàn)類铣揉，其存儲結(jié)構(gòu)對應(yīng)為數(shù)據(jù)結(jié)構(gòu)-散列表饶深，也被稱為哈希表存儲。
2 散列表
散列表的英文叫“Hash Table”逛拱，我們平時(shí)也叫它“哈希表”或者“Hash 表”敌厘，散列表用的就是數(shù)組支持按照下標(biāo)隨機(jī)訪問的時(shí)候，時(shí)間復(fù)雜度是 O(1) 的特性橘券。我們通過散列函數(shù)把元素的鍵值映射為下標(biāo)额湘，然后將數(shù)據(jù)存儲在數(shù)組中對應(yīng)下標(biāo)的位置
2.1 散列沖突（Hash沖突）
再好的散列函數(shù)也無法避免散列沖突。那究竟該如何解決散列沖突問題呢旁舰？我們常用的散列沖突解決方法有兩類锋华，開放尋址法（open addressing）和鏈表法（chaining）
2.1.1 開放尋址法
開放尋址法的核心思想是，如果出現(xiàn)了散列沖突箭窜，我們就重新探測一個(gè)空閑位置毯焕，將其插入
從圖中可以看出，散列表的大小為 10磺樱，在元素 x 插入散列表之前纳猫，已經(jīng) 6 個(gè)元素插入到散列表中。x 經(jīng)過 Hash 算法之后竹捉，被散列到位置下標(biāo)為 7 的位置芜辕，但是這個(gè)位置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突块差。于是我們就順序地往后一個(gè)一個(gè)找侵续，看有沒有空閑的位置，遍歷到尾部都沒有找到空閑的位置憨闰，于是我們再從表頭開始找状蜗，直到找到空閑位置 2，于是將其插入到這個(gè)位置鹉动。
2.1.2 鏈表法
在散列表中轧坎，每個(gè)“桶（bucket）”或者“槽（slot）”會(huì)對應(yīng)一條鏈表，所有散列值相同的元素我們都放到相同槽位對應(yīng)的鏈表中泽示。
當(dāng)插入的時(shí)候蝶溶，我們只需要通過散列函數(shù)計(jì)算出對應(yīng)的散列槽位欧募，將其插入到對應(yīng)鏈表中即可，所以插入的時(shí)間復(fù)雜度是 O(1)。當(dāng)查找奶稠、刪除一個(gè)元素時(shí)睡陪，我們同樣通過散列函數(shù)計(jì)算出對應(yīng)的槽盖矫，然后遍歷鏈表查找或者刪除种柑。
3 HashMap存儲結(jié)構(gòu)
HashMap鏈表法使用鏈表法來存儲數(shù)據(jù)
HashMap使用Entry<K,V>[]來表示哈希表。
/**
* 哈希表，存儲數(shù)據(jù)類型為Entry渔呵，長度必須始終是2的冪怒竿。
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry類定義
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 鍵值對的鍵
V value; // 鍵值對的值
Entry<K,V> next; // 下一個(gè)節(jié)點(diǎn)
final int hash; // hash(key.hashCode())方法的返回值
Entry(int h, K k, V v, Entry<K,V> n) { // Entry 的構(gòu)造函數(shù)
value = v;
next = n;
key = k;
hash = h;
}
/**
* 添加時(shí)調(diào)用，作為子類模板方法
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* 刪除時(shí)調(diào)用扩氢，作為子類模板方法
*/
void recordRemoval(HashMap<K,V> m) {
}
...省略代碼
}
5 HashMap內(nèi)部核心屬性
/**
* 默認(rèn)的初始容量為16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大的容量為2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)的裝載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 空的哈希表
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* 哈希表（桶）耕驰，存儲數(shù)據(jù)類型為Entry，長度必須始終是2的冪录豺。
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* Map中存儲Entry數(shù)量
*/
transient int size;
/**
* 進(jìn)行下一次擴(kuò)容Entry結(jié)構(gòu)數(shù)組元素的數(shù)量的閥值 計(jì)算公式=(capacity * loadFactor).
* 擴(kuò)容閥值
*/
int threshold;
/**
* 裝載因子
*/
final float loadFactor;
/**
* 數(shù)據(jù)修改次數(shù)
*/
transient int modCount;
4 HashMap構(gòu)造函數(shù)
在JDK1.7中HashMap構(gòu)造函數(shù)中并不會(huì)構(gòu)建哈希表朦肘，其動(dòng)作會(huì)放在第一次put動(dòng)作時(shí)創(chuàng)建。
/**
* 用指定的初始容量和默認(rèn)裝載因子實(shí)例化一個(gè)空的哈希表
* @param initialCapacity 初始值
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 用默認(rèn)初始容量,默認(rèn)裝載因子實(shí)例化一個(gè)空的哈希表
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 用指定的初始容量,裝載因子實(shí)例化一個(gè)空的哈希表
* @param initialCapacity 初始值
* @param loadFactor 裝載因子
*/
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);
/** 設(shè)置裝載因子（默認(rèn)0.75f） **/
this.loadFactor = loadFactor;
/** 設(shè)置擴(kuò)容閥值 **/
threshold = initialCapacity;
/** jdk1.7中hashMap的init方法是空實(shí)現(xiàn)双饥，并沒有創(chuàng)建存儲Entry結(jié)構(gòu)數(shù)組**/
init();
}
/**
* 子類實(shí)現(xiàn)模板方法
*/
void init() {
}
5 向Map添加一個(gè)key-value
向Map添加一個(gè)key-value,如果key存在返回于Map中媒抠，則會(huì)覆蓋value并返回原始值。
1 第一次put時(shí)哈希表并為創(chuàng)建,調(diào)用inflateTable(threshold)構(gòu)建哈希表
2 如果添加key為null咏花，調(diào)用putForNullKey處理趴生，放入哈希表數(shù)組table[0]位置
3 計(jì)算key hash值，并計(jì)算hash對應(yīng)哈希表桶位置i昏翰。
4 判斷table[i]是否存在元素Entry苍匆，如果存在則從Entry開始，作為鏈表的頭部元素棚菊，向后遍歷查找key&hash相同元素Entry(用來表示插入的key-value以存在于Map中）如果找到則覆蓋Entry.value浸踩，并調(diào)用Entry對象recordAccess，返回原始值
5 創(chuàng)建一個(gè)Entry统求，next指向的原始table[bucketIndex]民轴，存儲到哈希表table[bucketIndex]指定下標(biāo)位置,作為鏈表的新頭部元素
/**
* 向Map添加一個(gè)key-value結(jié)構(gòu),如果key存在返回于Map中，會(huì)覆蓋value返回原始值
*/
public V put(K key, V value) {
/** 1 第一次put時(shí)哈希表并為創(chuàng)建,調(diào)用inflateTable(threshold)構(gòu)建哈希表 **/
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
/** 2 如果添加key為null球订，調(diào)用putForNullKey處理，放入哈希表數(shù)組table[0]位置 **/
if (key == null)
return putForNullKey(value);
/** 3 計(jì)算key hash值瑰钮，并計(jì)算hash值映射哈希表下標(biāo)位置冒滩。 **/
int hash = hash(key);
int i = indexFor(hash, table.length);
/**
* 4 判斷table[i]是否存在元素Entry，如果存在則從Entry開始浪谴，作為鏈表的頭部元素开睡，
* 向后遍歷查找key&hash相同元素Entry(用來表示插入的key-value以存在于Map中）
* 如果找到則覆蓋Entry.value，并調(diào)用recordAccess苟耻，返回原始值
*/
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;
e.recordAccess(this);
return oldValue;
}
}
/** 修改次數(shù)+1 **/
modCount++;
/**
* 5 創(chuàng)建一個(gè)Entry篇恒，next指向的原始table[bucketIndex]，存儲到哈希表table[bucketIndex]指定下標(biāo)位置,作為鏈表的新頭部元素
* 該方法支持?jǐn)U容 **/
addEntry(hash, key, value, i);
return null;
}
static class Entry<K,V> implements Map.Entry<K,V> {
/**
* 添加時(shí)調(diào)用凶杖，作為子類模板方法
*/
void recordAccess(HashMap<K,V> m) {
}
5.1 構(gòu)建哈希表
private void inflateTable(int toSize) {
/** 用來返回大于等于最接近toSize的2的冪數(shù) **/
int capacity = roundUpToPowerOf2(toSize);
/** 設(shè)置擴(kuò)容閥值 **/
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
/** 構(gòu)建哈希表 **/
table = new Entry[capacity];
/** 初始化哈希掩碼值胁艰。我們推遲初始化，直到真正需要它。**/
initHashSeedAsNeeded(capacity);
}
/**
* 用來返回大于等于最接近number的2的冪數(shù)
*/
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
/**
* 初始化哈希掩碼值腾么。我們推遲初始化奈梳，直到真正需要它。
*/
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
5.2 向Map添加一個(gè)key-value(key為Null)
將key為null鍵值放入放入哈希表數(shù)組table[0]位置
/**
* 將key為null鍵值放入放入哈希表數(shù)組table[0]位置
*/
private V putForNullKey(V value) {
/**
* 判斷table[0]是否存在元素Entry解虱，
* 如果存在則從Entry開始攘须，作為鏈表的頭部元素，向后遍歷查找key=null元素Entry(用來表示插入的key-value以存在于Map中).
* 如果找到則覆蓋Entry.value,并返回原始value
*/
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;
}
}
/** 修改次數(shù)+1 **/
modCount++;
/** 創(chuàng)建一個(gè)Entry殴泰，next指向的原始table[bucketIndex]于宙，存儲到哈希表table[bucketIndex]指定下標(biāo)位置,作為鏈表的新頭部元素
* 該方法支持?jǐn)U容 **/
addEntry(0, null, value, 0);
return null;
}
4.3 addEntry
addEntry可以清楚地了解到 鏈的產(chǎn)生時(shí)機(jī)。HashMap 總是將新的Entry對象添加到bucketIndex處悍汛，若bucketIndex處已經(jīng)有了Entry對象捞魁，那么新添加的Entry對象將指向原有的Entry對象，并形成一條新的以它為鏈頭的Entry鏈员凝；但是署驻，若bucketIndex處原先沒有Entry對象，那么新添加的Entry對象將指向 null健霹，也就生成了一條長度為 1 的全新的Entry鏈了旺上。HashMap 永遠(yuǎn)都是在鏈表的表頭添加新元素。此外糖埋，若HashMap中元素的個(gè)數(shù)超過極限值 threshold宣吱，其將進(jìn)行擴(kuò)容操作，一般情況下瞳别，容量將擴(kuò)大至原來的兩倍
/**
* 創(chuàng)建一個(gè)Entry征候，next指向的原始table[bucketIndex]，存儲到哈希表table[bucketIndex]指定下標(biāo)位置,作為鏈表的新頭部元素
* 該方法支持?jǐn)U容
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
/** 判斷是否進(jìn)行擴(kuò)容 **/
if ((size >= threshold) && (null != table[bucketIndex])) {
/** 擴(kuò)容處理 **/
resize(2 * table.length);
/** 重新計(jì)算key hash值 **/
hash = (null != key) ? hash(key) : 0;
/** 計(jì)算hash值映射哈希表下標(biāo)位置**/
bucketIndex = indexFor(hash, table.length);
}
/** 創(chuàng)建一個(gè)Entry祟敛，next指向的原始table[bucketIndex]疤坝，存儲到table[bucketIndex]位置，作為鏈表的新頭部元素**/
createEntry(hash, key, value, bucketIndex);
}
/**
* 創(chuàng)建一個(gè)Entry馆铁，next指向的原始table[bucketIndex]跑揉，存儲到table[bucketIndex]位置，作為鏈表的新頭部元素
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
/** 獲取原始table[bucketIndex]**/
Entry<K,V> e = table[bucketIndex];
/** 創(chuàng)建一個(gè)Entry埠巨，next指向的原始table[bucketIndex]历谍，存儲到table[bucketIndex]位置，作為鏈表的新頭部元素**/
table[bucketIndex] = new Entry<>(hash, key, value, e);
/** 數(shù)量+1 **/
size++;
}
4.4 擴(kuò)容
隨著HashMap中元素的數(shù)量越來越多辣垒，發(fā)生碰撞的概率將越來越大望侈，所產(chǎn)生的子鏈長度就會(huì)越來越長，這樣勢必會(huì)影響HashMap的存取速度勋桶。為了保證HashMap的效率脱衙，系統(tǒng)必須要在某個(gè)臨界點(diǎn)進(jìn)行擴(kuò)容處理侥猬，該臨界點(diǎn)就是HashMap中元素的數(shù)量在數(shù)值上等于threshold（table數(shù)組長度*加載因子）。但是岂丘，不得不說陵究，擴(kuò)容是一個(gè)非常耗時(shí)的過程，因?yàn)樗枰匦掠?jì)算這些元素在新table數(shù)組中的位置并進(jìn)行復(fù)制處理奥帘。所以铜邮，如果我們能夠提前預(yù)知HashMap 中元素的個(gè)數(shù)，那么在構(gòu)造HashMap時(shí)預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能寨蹋。
/**
* 擴(kuò)容
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
/** 創(chuàng)建2倍大小的新數(shù)組 **/
Entry[] newTable = new Entry[newCapacity];
/** 將舊數(shù)組的鏈表轉(zhuǎn)移到新數(shù)組松蒜，就是這個(gè)方法導(dǎo)致的hashMap不安全 **/
transfer(newTable, initHashSeedAsNeeded(newCapacity));
/** 設(shè)置新的Entry數(shù)組**/
table = newTable;
/** 重新計(jì)算擴(kuò)容閥值**/
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 將舊數(shù)組的鏈表轉(zhuǎn)移到新數(shù)組，就是這個(gè)方法導(dǎo)致的hashMap不安全
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
/** 遍歷原始table中所有Entry **/
for (Entry<K,V> e : table) {
/** 遍歷table數(shù)組中每一個(gè)Entry對應(yīng)的鏈表中所有Entry **/
while(null != e) {
Entry<K,V> next = e.next;
/** 是否重新計(jì)算hash **/
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
/** 計(jì)算hash值映射哈希表下標(biāo)位置 **/
int i = indexFor(e.hash, newCapacity);
/** 將當(dāng)前Entry.next指向的原始table[i]已旧，存儲到table[i]位置,作為鏈表的新頭部元素**/
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
小結(jié)
6 向Map刪除指定的key
1 從Map獲取刪除指定的key對應(yīng)Entry秸苗，并將Entry從哈希表中剔除
2 調(diào)用Entry.recordRemoval,這里是空實(shí)現(xiàn)，可以給子類擴(kuò)展
/**
* 從Map刪除指定的key
*/
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
* 從Map獲取刪除指定的key對應(yīng)Entry运褪，并將Entry從存儲結(jié)構(gòu)中剔除
*/
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
/** 計(jì)算key hash值 **/
int hash = (key == null) ? 0 : hash(key);
/** 計(jì)算hash值映射哈希表下標(biāo)位置 **/
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
/** 從Map獲取刪除指定的key對應(yīng)Entry惊楼，并將Entry從哈希表中剔除,并調(diào)用e.recordRemoval **/
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--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
static class Entry<K,V> implements Map.Entry<K,V> {
/**
* 刪除時(shí)調(diào)用，作為子類模板方法
*/
void recordRemoval(HashMap<K,V> m) {
}
7 獲取Map中key對應(yīng)值value
HashMa讀取就顯得比較秸讹。只需通過key的hash值定位到哈希表下標(biāo)位置檀咙，然后查找并返回該key對應(yīng)的value即可
針對鍵為NULL的鍵值對，HashMap 提供了專門的處理：getForNullKey()
/**
* 獲取key對應(yīng)值value
*/
public V get(Object key) {
/** 獲取key為null璃诀，調(diào)用getForNullKey獲取value **/
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
/**
* 獲取key為null對應(yīng)值value弧可，key為NULL對應(yīng)Entry，存儲在哈希表數(shù)組第一個(gè)下標(biāo)位置
*/
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;
}
/**
* 判斷指定key是否存儲在Map
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
* 獲取key存儲在哈希表中對象Entry
*/
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
/** 獲取key對應(yīng)的hash **/
int hash = (key == null) ? 0 : hash(key);
/** 計(jì)算hash值映射哈希表下標(biāo)位置Entry劣欢，如果存在則從Entry開始棕诵，作為鏈表的頭部元素，向后遍歷查找key相同Entry凿将，并返回**/
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;
}
