HashMap是java中的一個(gè)容器類，實(shí)現(xiàn)了Map接口爪喘，可以存放鍵值對(duì)纠拔，鍵和值都可以為null（鍵僅可以有一個(gè)null，而值可以有多個(gè)null）侦鹏，在聲明時(shí)傳入的泛型必須是對(duì)象類型，諸如int价卤、double等的基本類型是不行的慎璧，要轉(zhuǎn)成包裝類跨释。它是非同步的，與之相反的是concurrentHashMap岁疼。
HashMap的實(shí)現(xiàn)是基于散列表算法的蚯姆，每個(gè)對(duì)象都有自己的哈希值龄恋，根據(jù)哈希值可以快速定位到元素的位置凶伙。Hashmap結(jié)合了數(shù)組和鏈表以及平衡樹（紅黑樹）的方式對(duì)元素進(jìn)行存儲(chǔ)。它定義了一個(gè)Node類显押，用來存儲(chǔ)鍵和值傻挂，同時(shí)Node有一個(gè)Node屬性的next字段金拒，所以可以生成鏈表。HashMap的存儲(chǔ)過程是這樣的资铡，內(nèi)部默認(rèn)初始化一個(gè)容量大小為16的Node數(shù)組幢码，稱為哈希桶，插入元素時(shí)計(jì)算元素的哈希值在根據(jù)數(shù)組容量大小定位到數(shù)組的某個(gè)位置店雅。
從上的操作中可以看出有幾個(gè)問題：
- 為什么默認(rèn)哈希桶默認(rèn)初始值為16
- 如何處理傳入的鍵的哈希值并給出一個(gè)數(shù)組定位
- 數(shù)組長度總是有限的闹啦，存儲(chǔ)元素多了無可避免會(huì)發(fā)生沖突，
HashMap是如何解決沖突的 - 當(dāng)存儲(chǔ)元素多到一定時(shí)候珊擂，怎么擴(kuò)展空間
- 既然是非同步的费变，在多線程環(huán)境下可能發(fā)生什么情況
下圖是HashMap的成員變量（沒特別說明，源碼都基于java 8）
這是幾個(gè)比較重要的字段：
-
DEFAULT_INITIAL_CAPACITY初始容量，大小為16 -
MAXIMUM_CAPACITY允許存儲(chǔ)的最大容量 -
DEFAULT_LOAD_FACTOR裝載因子滑负，和空間重分配有關(guān) -
TREEIFY_THRESHOLD鏈表轉(zhuǎn)化為紅黑樹的閾值 -
table哈希桶矮慕，是Node類型的數(shù)組
通過HashMap的構(gòu)造函數(shù)可以設(shè)定哈希桶的初始大小以及裝載因子，但最終的大小并不一定是這個(gè)值瘟斜，HashMap會(huì)根據(jù)傳入的數(shù)進(jìn)行合理運(yùn)算痪寻，保證大小是2的冪次方橡类。這涉及到根據(jù)hash值分配位置的原因，好的做法是根據(jù)哈希值做相應(yīng)的操作得到均勻分散的位置取劫，HashMap采用位運(yùn)算求余亲雪，然后再經(jīng)過擾動(dòng)操作得出最終結(jié)果。
結(jié)合源碼分析虾标，通過HashMap(int)的構(gòu)造函數(shù)可以看到和tableSizeFor方法有關(guān)璧函。
public HashMap(int initialCapacity, float loadFactor) {
// 初始化大小是負(fù)數(shù)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 超出最大容量則設(shè)為最大容量值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 裝載因子是否合理
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 設(shè)置閾值
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
tableSizeFor方法執(zhí)行完后會(huì)得到第一個(gè)不比傳入整數(shù)小的符合2的冪次方大小的整數(shù)蘸吓，比如傳入3會(huì)得到4，傳入7會(huì)得到8等箩艺。方法中一開始n = cap - 1是由于如果傳入 數(shù)本身就是2的冪次方宪萄，得出的結(jié)果會(huì)不正確，所以要先減一静汤。當(dāng)進(jìn)行第一次插入操作時(shí)虫给，如果哈希桶是空的會(huì)進(jìn)行resize操作侠碧，在resize方法中會(huì)設(shè)置容量大小為2的冪次方。
HashMap的鍵可能不是整數(shù)類型棋蚌，定位數(shù)組坐標(biāo)需要整數(shù)類型，在計(jì)算哈希值時(shí)利用Object的hashCode得到這個(gè)整數(shù)盛垦。HashMap在定位元素哈希桶位置時(shí)做了(n - 1) & hash的操作瓤漏，其目的是求余，通過位運(yùn)算可以提高效率蝶俱，而n是2的冪次方可以讓hash值分配得更均勻饥漫。比如A的hash值為10101010庸队，B的哈希值為01011110闯割，那么n-1的值是類似于11111全1的竿拆，它和hash值相與時(shí)能保證低位和原來的一樣丙笋，若不是2的冪次方，則n-1可能會(huì)導(dǎo)致hash值低位會(huì)改變澳化，本來差異挺大的hash值也可能碰撞稳吮，導(dǎo)致分配不均灶似。此外，官方也利用了擾動(dòng)函數(shù)對(duì)碰撞進(jìn)行了優(yōu)化希痴。由上春感，HashMap在實(shí)現(xiàn)上要求哈希桶的容量大小為2的冪次方鲫懒。同時(shí)，官方也建議在知道HashMap需要存儲(chǔ)多少元素的情況下最后在構(gòu)造方法中傳入初始化大小甲献。
插入元素根據(jù)位置插入到哈希桶颂翼，如果此時(shí)該位置上為null在放進(jìn)去，如果有則判斷是不是鍵一樣球及，一樣則覆蓋原來的值吃引，否則生成一個(gè)鏈表，在JAVA 8 中惶翻，如果鏈表長度超過了8鹅心，則會(huì)構(gòu)造為紅黑樹。（在最差的情況下颅筋，數(shù)組查找為O(1),鏈表為O(n),而平衡樹可達(dá)到O(log n)议泵，將鏈表轉(zhuǎn)化為紅黑樹可以提高速率）桃熄。
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，則重新分配大小
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根據(jù)哈希定位元素位置碉京，當(dāng)前位置為null則插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 插入元素的key和存在元素的一樣谐宙，覆蓋原值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果存在對(duì)象是紅黑樹
// TreeNode繼承自LinkedHashMapEntry繼承自Node
else if (p instanceof TreeNode)
// 紅黑樹操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍歷鏈表
for (int binCount = 0; ; ++binCount) {
// 已經(jīng)是鏈表尾部凡蜻，將新元素插入當(dāng)前元素的后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 當(dāng)鏈表大小超過紅黑樹閾值時(shí)將鏈表轉(zhuǎn)為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 鏈表中找到一樣的元素垢箕，覆蓋之
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 鏈表的下一個(gè)元素
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// afterNodeAccess是空方法舰讹，此外還有afterNodeInsertion、afterNodeRemoval也一樣
// 分別意為節(jié)點(diǎn)訪問后、節(jié)點(diǎn)插入后锄开、節(jié)點(diǎn)移除称诗，重寫方法實(shí)現(xiàn)相應(yīng)的功能
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果此時(shí)哈希桶大小超過閾值，進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
當(dāng)哈希桶元素個(gè)數(shù)超過閾值時(shí)會(huì)進(jìn)行擴(kuò)容计维，threshold就是閾值撕予，閾值=裝載因子 * 容量大小，默認(rèn)初始閾值為DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY欠母，即值為6赏淌。HashMap并不是等哈希桶被裝滿后才進(jìn)行擴(kuò)容啄清，所以設(shè)置了一個(gè)閾值辣卒，若低于這個(gè)閾值說明空間利用還充足，若超過則表明插入元素發(fā)生碰撞的幾率很大了胯盯。擴(kuò)容在HashMap的resize方法執(zhí)行计露。
final Node<K,V>[] resize() {
// 記錄原來的哈希桶票罐、容量大小、閾值
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 原容量大小 > 0
if (oldCap > 0) {
// 已經(jīng)是最大容量了疗杉，閾值設(shè)為和容量大小一樣
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 將容量和閾值擴(kuò)為原來的1倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 空表有閾值烟具，將新容量設(shè)為原閾值大小
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 空表空閾值奠蹬，設(shè)置默認(rèn)初始值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新閾值為0囤躁，利用新容量大小*裝載因子得到新閾值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 設(shè)置當(dāng)前閾值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 聲明一個(gè)擴(kuò)容之后的新哈希桶荔睹，將原來元素裝入
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 原表有值
if (oldTab != null) {
// 遍歷哈希桶數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 數(shù)組j只有一個(gè)元素僻他，計(jì)算新位置后直接放入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果數(shù)組j是一個(gè)紅黑樹
else if (e instanceof TreeNode)
// 進(jìn)行紅黑樹高度降低或直接解散紅黑樹 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 將鏈表重分配腊尚，定義低位和高位跟伏。低位指原來的位置，高位為擴(kuò)展后的位置（它為舊位置+原來容量大行辍）勘高。
// 比如原來容量大小為4华望，存儲(chǔ)著0->4->8，1->5,2,3這幾個(gè)元素
// 未擴(kuò)容時(shí)0蓬戚、4和8根據(jù)哈希定位都在第0個(gè)（0 ^ 11 = 0宾抓，100 ^ 11 = 0,1000 ^ 11 = 0）
// 但擴(kuò)容后4在新表的第5個(gè)，即hi = oldCap + j（j表示原來在第幾個(gè),100 ^ 111 = 4 > 0石洗，4 + 0 = 4幢泼，在新表的tab[4]上，故為第5個(gè)）讲衫。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 利用位運(yùn)算得出如果等于零則給元素處于低位缕棵，否則為高位
// 表示擴(kuò)容后處在低位，即例子說的0涉兽，8
if ((e.hash & oldCap) == 0) {
// 如果還是有碰撞招驴，建立新的鏈
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 表示擴(kuò)容后在高位
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
// 直至鏈表重新分完
} while ((e = next) != null);
// 這里的操作就是上面所說的，低位鏈表還是在低位枷畏，高位的則放置在newTab[j + oldCap]位置上
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap不是同步的，在高并發(fā)的情況下會(huì)導(dǎo)致這樣的情況發(fā)生：在JDK1.7時(shí)矿辽，由于擴(kuò)容后的新數(shù)組與原數(shù)組的指針引用關(guān)系會(huì)導(dǎo)致鏈表出現(xiàn)死循環(huán)丹允，在JDK1.8則沒有死鎖問題，但是會(huì)在put操作時(shí)由于覆蓋導(dǎo)致出現(xiàn)數(shù)據(jù)丟失的情況袋倔。
static HashMap<Integer, Integer> sHashMap = new HashMap<>();
public static void main(String[] args) throws InterruptedException {
new Thread(() -> {
for (int j = 0; j < 100000; j++) {
int finalJ = j;
new Thread(() -> {
sHashMap.put(finalJ, finalJ);
}).start();
}
}).start();
Thread.sleep(5000);
for (int i = 0; i < 100000; i++) {
if (sHashMap.get(i) == null)
System.out.println("value is null");
}
}
// output:
// value is null
// ……
HashMap與Hashtable雕蔽、ConcurrentHashMap相比缺乏同步操作，Hashtable繼承自Dictionary宾娜，在重要方法前加上了synchronized前綴批狐，key和value不能為null，在定位數(shù)組位置時(shí)采用除模取余法前塔，插入是先判斷之前是否有記錄嚣艇，有則覆蓋，否則數(shù)組HashtableEntry數(shù)量加一华弓，此時(shí)如果超過閾值會(huì)進(jìn)行擴(kuò)容食零。從擴(kuò)容方法rehash中int newCapacity = (oldCapacity << 1) + 1可知哈希桶的數(shù)量大小為奇數(shù)個(gè)，默認(rèn)構(gòu)造函數(shù)設(shè)置初始大小為11寂屏，Hashtable擴(kuò)容時(shí)沒有涉及紅黑樹贰谣，只是將鏈表拆分重新分配位置,采用的是頭插法。
// 從高位開始
for (int i = oldCapacity ; i-- > 0 ;) {
for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
HashtableEntry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
// 從這可知是頭插法
e.next = (HashtableEntry<K,V>)newMap[index];
newMap[index] = e;
}
}
ConcurrentHashMap也是同步的迁霎，不過沒有直接采用synchronized吱抚，而是使用了CAS，相比于Hashtable在性能上更快考廉。多個(gè)線程對(duì)Hashtable哈希桶競爭寫操作時(shí)會(huì)發(fā)生阻塞秘豹，而ConcurrentHashMap則將同步的粒度減小了，在JDK1.7通過對(duì)segments數(shù)組（每一個(gè)segment相當(dāng)于一個(gè)HashMap）中的單個(gè)segment上鎖可以讓多個(gè)segment可以并發(fā)執(zhí)行昌粤。
