java.util.HashMap
public class HashMap<K, V> extends AbstractMap implements Map<K, V>, Cloneable, Serializable
本質(zhì)是一個(gè)Entry[]數(shù)組（哈希桶數(shù)組），用Key的哈希值對(duì)桶數(shù)組size取?？傻玫綌?shù)組下標(biāo)。若數(shù)組下標(biāo)碰撞，進(jìn)化為鏈表或紅黑樹。
使用
構(gòu)造函數(shù)
HashMap map = new HashMap();
常用方法
HashMap<String, Integer> map = new HashMap();
map.put("ary", 1);
map.get("ary");
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
Lambda用法
map.merge("ary", 1, (oldValue, newValue) -> oldValue + newValue);
map.compute("ary", (k, v) -> v + 1);
摘要
- HashMap 是一個(gè)關(guān)聯(lián)數(shù)組、哈希表，線程不安全的，遍歷時(shí)無(wú)序。
- 其底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組稱之為哈希桶，每個(gè)桶里面放的是鏈表，鏈表中的每個(gè)節(jié)點(diǎn)，就是哈希表中的每個(gè)元素。
- 在JDK8中，當(dāng)鏈表長(zhǎng)度達(dá)到8，會(huì)轉(zhuǎn)化成紅黑樹，以提升它的查詢、插入效率，它實(shí)現(xiàn)了Map<K,V>, Cloneable, Serializable接口。
因其底層哈希桶的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，所以也會(huì)涉及到擴(kuò)容的問(wèn)題。
當(dāng)HashMap的容量達(dá)到threshold域值時(shí)，就會(huì)觸發(fā)擴(kuò)容。擴(kuò)容前后，哈希桶的長(zhǎng)度一定會(huì)是2的次方。
這樣在根據(jù)key的hash值尋找對(duì)應(yīng)的哈希桶時(shí)，可以用位運(yùn)算替代取余操作，更加高效。
在擴(kuò)容中只用判斷原來(lái)的 hash 值與左移動(dòng)的一位（newtable 的值）按位與操作是 0 或 1 就行，0 的話索引就不變，1 的話索引變成原索引加上擴(kuò)容前數(shù)組
而key的hash值，并不僅僅只是key對(duì)象的hashCode()方法的返回值，還會(huì)經(jīng)過(guò)擾動(dòng)函數(shù)的擾動(dòng)，以使hash值更加均衡。
因?yàn)閔ashCode()是int類型，取值范圍是40多億，只要哈希函數(shù)映射的比較均勻松散，碰撞幾率是很小的。
但就算原本的hashCode()取得很好，每個(gè)key的hashCode()不同，但是由于HashMap的哈希桶的長(zhǎng)度遠(yuǎn)比hash取值范圍小，默認(rèn)是16，所以當(dāng)對(duì)hash值以桶的長(zhǎng)度取余，以找到存放該key的桶的下標(biāo)時(shí)，由于取余是通過(guò)與操作完成的，會(huì)忽略hash值的高位。因此只有hashCode()的低位參加運(yùn)算，發(fā)生不同的hash值，但是得到的index相同的情況的幾率會(huì)大大增加，這種情況稱之為hash碰撞。 即，碰撞率會(huì)增大。
哈希表的容量一定要是2的整數(shù)次冪。
首先，length為2的整數(shù)次冪的話，h&(length-1)就相當(dāng)于對(duì)length取模，這樣便保證了散列的均勻，同時(shí)也提升了效率；
其次，length為2的整數(shù)次冪為偶數(shù)，這樣length-1為奇數(shù)，奇數(shù)的最后一位是1，這樣便保證了h&(length-1)的最后一位可能為0，也可能為1(這取決于h的值)，即與后的結(jié)果可能為偶數(shù)，也可能為奇數(shù)，這樣便可以保證散列的均勻性。
而如果length為奇數(shù)的話，很明顯length-1為偶數(shù)，它的最后一位是0，這樣h&(length-1)的最后一位肯定為0，即只能為偶數(shù)，這樣任何hash值都只會(huì)被散列到數(shù)組的偶數(shù)下標(biāo)位置上，這便浪費(fèi)了一半的空間。
因此，length取2的整數(shù)次冪，是為了使不同hash值發(fā)生碰撞的概率較小，這樣就能使元素在哈希表中均勻地散列
由于存在鏈表和紅黑樹互換機(jī)制，搜索時(shí)間呈對(duì)數(shù) O(log(n))級(jí)增長(zhǎng)，而非線性O(shè)(n)增長(zhǎng)
擾動(dòng)函數(shù)
擾動(dòng)函數(shù)就是為了解決hash碰撞的。它會(huì)綜合hash值高位和低位的特征，并存放在低位，因此在與運(yùn)算時(shí)，相當(dāng)于高低位一起參與了運(yùn)算，以減少hash碰撞的概率。（在JDK8之前，擾動(dòng)函數(shù)會(huì)擾動(dòng)四次，JDK8簡(jiǎn)化了這個(gè)操作）
擴(kuò)容操作時(shí)，會(huì)new一個(gè)新的Node數(shù)組作為哈希桶，然后將原哈希表中的所有數(shù)據(jù)(Node節(jié)點(diǎn))移動(dòng)到新的哈希桶中，相當(dāng)于對(duì)原哈希表中所有的數(shù)據(jù)重新做了一個(gè)put操作。所以性能消耗很大，可想而知，在哈希表的容量越大時(shí)，性能消耗越明顯。
擴(kuò)容時(shí)，如果發(fā)生過(guò)哈希碰撞，節(jié)點(diǎn)數(shù)小于8個(gè)。則要根據(jù)鏈表上每個(gè)節(jié)點(diǎn)的哈希值，依次放入新哈希桶對(duì)應(yīng)下標(biāo)位置。
因?yàn)閿U(kuò)容是容量翻倍，所以原鏈表上的每個(gè)節(jié)點(diǎn)，現(xiàn)在可能存放在原來(lái)的下標(biāo)，即low位， 或者擴(kuò)容后的下標(biāo)，即high位。 high位= low位+原哈希桶容量
運(yùn)算
- 與運(yùn)算替代模運(yùn)算
static int indexFor(int h, int length) { //根據(jù)hash值和數(shù)組長(zhǎng)度算出索引值
return h & (length-1); //這里不能隨便算取，用 hash&(length-1) 是有原因的，這樣可以確保算出來(lái)的索引是在數(shù)組大小范圍內(nèi)，不會(huì)超出
}
除法效率低，與運(yùn)算效率高
hash & (table.length-1)
hash % (table.length)
- 判斷擴(kuò)容后，節(jié)點(diǎn)e處于低區(qū)還是高區(qū)
if ((e.hash & oldCap) == 0)
根據(jù)該 key 的 hashCode() 返回值決定該 Entry 的存儲(chǔ)位置：
如果這兩個(gè) Entry 的 key 的 hashCode() 相同，那它們的存儲(chǔ)位置相同。
- 如果這兩個(gè) Entry 的 key 通過(guò) equals 比較返回 true，新添加 Entry 的 value 將覆蓋集合中原有 Entry 的 value
- 如果這兩個(gè) Entry 的 key 通過(guò) equals 比較返回 false，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部
loadFactor的默認(rèn)值為0.75
fail-fast 策略
HashMap 不是線程安全的，因此如果在使用迭代器的過(guò)程中有其他線程修改了 map，那么將拋出 ConcurrentModificationException。
這一策略在源碼中是通過(guò) modCount 域?qū)崿F(xiàn)的，modCount 就是修改次數(shù)，對(duì) HashMap 內(nèi)容的修改都將增加這個(gè)值，那么在迭代器初始化過(guò)程中會(huì)將這個(gè)值賦給迭代器的 expectedModCount
issues
HashMap特性？
HashMap存儲(chǔ)鍵值對(duì)，實(shí)現(xiàn)快速存取數(shù)據(jù)；允許null鍵/值；非同步；不保證有序(比如插入的順序)，實(shí)現(xiàn)map接口。
HashMap的原理，內(nèi)部數(shù)據(jù)結(jié)構(gòu)？
- HashMap是基于hashing的原理，底層使用
哈希表(數(shù)組 + 鏈表)實(shí)現(xiàn) - 里邊最重要的兩個(gè)方法put、get，使用
put(key, value)存儲(chǔ)對(duì)象到HashMap中，使用get(key)從HashMap中獲取對(duì)象。 - 存儲(chǔ)對(duì)象時(shí)，我們將
K/V傳給put方法時(shí)，它調(diào)用key的hashCode計(jì)算hash從而得到bucket位置，進(jìn)一步存儲(chǔ) - HashMap會(huì)根據(jù)當(dāng)前bucket的占用情況自動(dòng)調(diào)整容量(超過(guò)Load Facotr則resize為原來(lái)的
2倍) - 獲取對(duì)象時(shí)，我們將K傳給get，它調(diào)用hashCode計(jì)算hash從而得到bucket位置，
并進(jìn)一步調(diào)用equals()方法確定鍵值對(duì) - 如果發(fā)生碰撞的時(shí)候，Hashmap通過(guò)
鏈表將產(chǎn)生碰撞沖突的元素組織起來(lái)，在Java 8中，如果一個(gè)bucket中碰撞沖突的元素超過(guò)某個(gè)限制(默認(rèn)是8)，則使用紅黑樹來(lái)替換鏈表，從而提高速度。
講一下 HashMap 中 put 方法過(guò)程？
- 對(duì)key的hashCode做hash操作，然后再計(jì)算在bucket中的index(1.5 HashMap的哈希函數(shù))
- 如果沒(méi)碰撞直接放到bucket里；
- 如果碰撞了，以鏈表的形式存在buckets后；
- 如果節(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)
- 如果bucket滿了(超過(guò)閾值，閾值=
loadfactor*current capacity，load factor默認(rèn)0.75)，就要resize。
get()方法的工作原理？
- 通過(guò)對(duì)key的hashCode()進(jìn)行hashing，并計(jì)算下標(biāo)( n-1 & hash)，從而
獲得buckets的位置。 - 如果產(chǎn)生碰撞，則利用
key.equals()方法去鏈表中查找對(duì)應(yīng)的節(jié)點(diǎn)。
HashMap中hash函數(shù)怎么是是實(shí)現(xiàn)的？
- 對(duì)key的hashCode做hash操作：高16bit不變，低16bit和高16bit做了一個(gè)異或
- 通過(guò)位操作得到下標(biāo)index：
h & (length-1)
還有哪些 hash 的實(shí)現(xiàn)方式？
還有數(shù)字分析法、平方取中法、分段疊加法、 除留余數(shù)法、 偽隨機(jī)數(shù)法。
HashMap 怎樣解決沖突？
HashMap中處理沖突的方法實(shí)際就是鏈地址法，內(nèi)部數(shù)據(jù)結(jié)構(gòu)是數(shù)組+單鏈表。
當(dāng)兩個(gè)鍵的hashcode相同會(huì)發(fā)生什么？
- 因?yàn)閮蓚€(gè)鍵的Hashcode相同，所以它們的bucket位置相同，會(huì)發(fā)生“碰撞”。
- HashMap使用鏈表存儲(chǔ)對(duì)象，這個(gè)Entry(包含有鍵值對(duì)的Map.Entry對(duì)象)會(huì)存儲(chǔ)在鏈表中。
拋開 HashMap，hash 沖突有那些解決辦法？
開放定址法、鏈地址法、再哈希法。
如果兩個(gè)鍵的hashcode相同，你如何獲取值對(duì)象？
- 重點(diǎn)在于理解hashCode()與equals()。
- 通過(guò)對(duì)key的hashCode()進(jìn)行hashing，并計(jì)算下標(biāo)( n-1 & hash)，從而獲得buckets的位置。
- 兩個(gè)鍵的hashcode相同會(huì)產(chǎn)生碰撞，則利用
key.equals()方法去鏈表或樹（java1.8）中去查找對(duì)應(yīng)的節(jié)點(diǎn)。
針對(duì) HashMap 中某個(gè) Entry 鏈太長(zhǎng)，查找的時(shí)間復(fù)雜度可能達(dá)到 O(n)，怎么優(yōu)化？
- 將鏈表轉(zhuǎn)為
紅黑樹，實(shí)現(xiàn)O(logn)時(shí)間復(fù)雜度內(nèi)查找。 - JDK1.8 已經(jīng)實(shí)現(xiàn)了。
如果HashMap的大小超過(guò)了負(fù)載因子(load factor)定義的容量，怎么辦？
擴(kuò)容。這個(gè)過(guò)程也叫作rehashing，大致分兩步：
- 擴(kuò)容：容量擴(kuò)充為原來(lái)的兩倍（2 * table.length）；
- 移動(dòng)：對(duì)每個(gè)節(jié)點(diǎn)
重新計(jì)算哈希值，重新計(jì)算每個(gè)元素在數(shù)組中的位置，將原來(lái)的元素移動(dòng)到新的哈希表中。
補(bǔ)充：
- loadFactor：加載因子。默認(rèn)值DEFAULT_LOAD_FACTOR = 0.75f；
- capacity：容量；
- threshold：閾值=
capacity*loadFactor。當(dāng)HashMap中存儲(chǔ)數(shù)據(jù)的數(shù)量達(dá)到threshold時(shí)，就需要將HashMap的容量加倍； - size：HashMap的大小，它是HashMap保存的鍵值對(duì)的數(shù)量。
為什么String, Interger這樣的類適合作為鍵？
- String, Interger這樣的類作為HashMap的鍵是再適合不過(guò)了，而且String最為常用。
- 因?yàn)镾tring對(duì)象是
不可變的，而且已經(jīng)重寫了equals()和hashCode()方法了。 - 不可變性是必要的，因?yàn)闉榱艘?jì)算hashCode()，就要
防止鍵值改變，如果鍵值在放入時(shí)和獲取時(shí)返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對(duì)象。 - 不可變性還有其他的優(yōu)點(diǎn)，如線程安全。
- 因?yàn)楂@取對(duì)象的時(shí)候要用到equals()和hashCode()方法，那么鍵對(duì)象正確的重寫這兩個(gè)方法是非常重要的。如果兩個(gè)不相等的對(duì)象返回不同的hashcode的話，那么碰撞的幾率就會(huì)小些，這樣就能提高HashMap的性能。
HashMap與HashTable區(qū)別
Hashtable可以看做是線程安全版的HashMap，兩者幾乎“等價(jià)”（當(dāng)然還是有很多不同）。
Hashtable幾乎在每個(gè)方法上都加上synchronized（同步鎖），實(shí)現(xiàn)線程安全。
HashMap可以通過(guò) Collections.synchronizeMap(hashMap) 進(jìn)行同步。
區(qū)別
- HashMap繼承于AbstractMap，而Hashtable繼承于Dictionary；
- 線程安全不同。Hashtable的幾乎所有函數(shù)都是同步的，即它是線程安全的，支持多線程。而HashMap的函數(shù)則是非同步的，它不是線程安全的。若要在多線程中使用HashMap，需要我們額外的進(jìn)行同步處理；
- null值。HashMap的key、value都可以為null。Hashtable的key、value都不可以為null；
- 迭代器(Iterator)。HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素），將會(huì)拋出ConcurrentModificationException。
- 容量的初始值和增加方式都不一樣：HashMap默認(rèn)的容量大小是16；增加容量時(shí)，每次將容量變?yōu)椤霸既萘縳2”。Hashtable默認(rèn)的容量大小是11；增加容量時(shí)，每次將容量變?yōu)椤霸既萘縳2 + 1”；
- 添加key-value時(shí)的hash值算法不同：HashMap添加元素時(shí)，是使用自定義的哈希算法。Hashtable沒(méi)有自定義哈希算法，而直接采用的key的hashCode()。
- 速度。由于Hashtable是線程安全的也是synchronized，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過(guò)Hashtable。
閾值為８
TreeNodes占用空間是普通Nodes的兩倍
理想情況下使用隨機(jī)的哈希碼，容器中節(jié)點(diǎn)分布在hash桶中的頻率遵循泊松分布，按照泊松分布的計(jì)算公式計(jì)算出了桶中元素個(gè)數(shù)和頻率的對(duì)照表，可以看到鏈表中元素個(gè)數(shù)為8時(shí)的概率已經(jīng)非常非常小，所以根據(jù)概率統(tǒng)計(jì)選擇了8。
理想情況下隨機(jī)hashCode算法下所有bin中節(jié)點(diǎn)的分布頻率會(huì)遵循泊松分布，我們可以看到，一個(gè)bin中鏈表長(zhǎng)度達(dá)到8個(gè)元素的概率為0.00000006
元素個(gè)數(shù)小于8，查詢成本高，新增成本低。
元素個(gè)數(shù)大于8，查詢成本低，新增成本高。
線程不安全
https://blog.csdn.net/mydreamongo/article/details/8960667
- put操作，在hashmap做put操作的時(shí)候會(huì)調(diào)用到以上的方法。現(xiàn)在假如A線程和B線程同時(shí)對(duì)同一個(gè)數(shù)組位置調(diào)用addEntry，兩個(gè)線程會(huì)同時(shí)得到現(xiàn)在的頭結(jié)點(diǎn)，然后A寫入新的頭結(jié)點(diǎn)之后，B也寫入新的頭結(jié)點(diǎn)，那B的寫入操作就會(huì)覆蓋A的寫入操作造成A的寫入操作丟失
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
- delete, 當(dāng)多個(gè)線程同時(shí)操作同一個(gè)數(shù)組位置的時(shí)候，也都會(huì)先取得現(xiàn)在狀態(tài)下該位置存儲(chǔ)的頭結(jié)點(diǎn)，然后各自去進(jìn)行計(jì)算操作，之后再把結(jié)果寫會(huì)到該數(shù)組位置去，其實(shí)寫回的時(shí)候可能其他的線程已經(jīng)就把這個(gè)位置給修改過(guò)了，就會(huì)覆蓋其他線程的修改
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
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--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
- resize, 當(dāng)多個(gè)線程同時(shí)檢測(cè)到總數(shù)量超過(guò)門限值的時(shí)候就會(huì)同時(shí)調(diào)用resize操作，各自生成新的數(shù)組并rehash后賦給該map底層的數(shù)組table，結(jié)果最終只有最后一個(gè)線程生成的新數(shù)組被賦給table變量，其他線程的均會(huì)丟失。而且當(dāng)某些線程已經(jīng)完成賦值而其他線程剛開始的時(shí)候，就會(huì)用已經(jīng)被賦值的table作為原始數(shù)組，這樣也會(huì)有問(wèn)題
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 = newTable;
threshold = (int)(newCapacity * loadFactor);
}
