基本構(gòu)造
內(nèi)部包含了一個(gè) Entry 類型的數(shù)組 Node，存放四個(gè)字段，hashCode, key, value, Entry next聊疲。每個(gè)位置當(dāng)做一個(gè)桶，存放了一個(gè)鏈表征绎，鏈表存放hash值相同的Entry。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
HashMap 允許插入鍵為 null 的鍵值對(duì)磨取。但是因?yàn)闊o(wú)法調(diào)用 null 的 hashCode() 方法人柿，也就無(wú)法確定該鍵值對(duì)的桶下標(biāo)，只能通過(guò)強(qiáng)制指定一個(gè)桶下標(biāo)來(lái)存放寝衫。HashMap 使用第 0 個(gè)桶存放鍵為 null 的鍵值對(duì)顷扩。
解決沖突方法
常用的是鏈地址法：hashmap默認(rèn)大小為16，通過(guò)除留余數(shù)法得到桶下標(biāo)慰毅，以頭插法方式進(jìn)行插入到鏈表中
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
開(kāi)放地址法：發(fā)生沖突時(shí)隘截，尋找下一個(gè)空的散列地址
再哈希法：用其他哈希函數(shù)計(jì)算地址
put操作
put操作，如果已經(jīng)存在鍵為key的鍵值對(duì)汹胃，則進(jìn)行更新并返回oldValue值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
取模
確定桶下標(biāo)的最后一步是將 key 的 hash 值對(duì)桶個(gè)數(shù)取模：hash%capacity婶芭，如果能保證 capacity 為 2 的 n 次方，那么就可以將這個(gè)操作轉(zhuǎn)換為位運(yùn)算着饥，即h & (length - 1)
擴(kuò)容
設(shè) HashMap 的 table 長(zhǎng)度為 M犀农，需要存儲(chǔ)的鍵值對(duì)數(shù)量為 N，如果哈希函數(shù)滿足均勻性的要求宰掉，那么每條鏈表的長(zhǎng)度大約為 N/M呵哨，因此平均查找次數(shù)的復(fù)雜度為 O(N/M)
hashmao擴(kuò)容的時(shí)候capacity也是按2的次方來(lái)擴(kuò)容;同時(shí)赁濒，擴(kuò)容含有臨界值threshold和裝載因子loadFactor(默認(rèn)0.75)，鍵值對(duì)數(shù)量size超過(guò)threshold則需要進(jìn)行擴(kuò)容（rehashing）孟害，擴(kuò)為原來(lái)的兩倍
擴(kuò)容時(shí)需要將oldTable所有鍵值對(duì)重新經(jīng)過(guò)哈希拒炎，放到newTable中，過(guò)程比較費(fèi)時(shí)
在線程安全方面挨务，多線程競(jìng)爭(zhēng)map的擴(kuò)容時(shí)击你，可能會(huì)導(dǎo)致ABA的死循環(huán)問(wèn)題
未擴(kuò)容前，鏈表太長(zhǎng)如何解決
從 JDK 1.8 開(kāi)始谎柄，一個(gè)桶存儲(chǔ)的鏈表長(zhǎng)度大于 8 時(shí)會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù),同時(shí)做刪除操作后鏈表長(zhǎng)度小于6則將紅黑樹(shù)轉(zhuǎn)換為鏈表
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
轉(zhuǎn)換過(guò)程
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
與HashTable對(duì)比
- hashTable用sy同步丁侄，保證線程安全
- 不允許null-key,null-value
- ConcurrentHashMap，它是HashTable的替代朝巫，比HashTable的擴(kuò)展性更好
- HashMap的迭代器(Iterator)是fail-fast迭代器鸿摇，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）捍歪，將會(huì)拋出ConcurrentModificationException户辱，但迭代器本身的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常
關(guān)于fail-fast迭代器
Fail-fast和iterator迭代器相關(guān)。如果某個(gè)集合對(duì)象創(chuàng)建了Iterator或者ListIterator糙臼，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對(duì)象，將會(huì)拋出ConcurrentModificationException異常恩商。但其它線程可以通過(guò)set()方法更改集合對(duì)象是允許的变逃，因?yàn)檫@并沒(méi)有從“結(jié)構(gòu)上”更改集合。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改怠堪，再調(diào)用set()方法揽乱，將會(huì)拋出IllegalArgumentException異常。
為什么使用String粟矿，Integer這樣的wrapper類適合作為鍵凰棉？
因?yàn)镾tring是不可變的，也重寫(xiě)了equals和hashcode方法陌粹，防止鍵的改變撒犀，Integer同理
