HashMap 是基于哈希表的 Map 接口的非同步實現(xiàn)。此實現(xiàn)提供所有可選的映射操作，并允許使用 null 值和 null 鍵棘利。此類不保證映射的順序，特別是它不保證該順序恒久不變朽缴。
特性
- HashMap根據(jù)鍵的hashCode值存儲數(shù)據(jù)善玫，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度密强，但遍歷順序卻是不確定的茅郎。
- HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null或渤。
- HashMap非線程安全系冗，即任一時刻可以有多個線程同時寫HashMap，可能會導致數(shù)據(jù)的不一致薪鹦。如果需要滿足線程安全毕谴，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力养葵，或者使用ConcurrentHashMap民轴。
結(jié)構(gòu)
從結(jié)構(gòu)實現(xiàn)來講悔常，HashMap是數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現(xiàn)的，如下如所示框仔。
數(shù)組中的每個元素是內(nèi)部類Node，其實現(xiàn)如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用來定位數(shù)組索引位置
final K key;
V value;
Node<K,V> next; //鏈表的下一個node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
HashMap中根據(jù)key對象的hash值計算出在數(shù)組中的索引拄养，實現(xiàn)數(shù)組存儲更加均勻离斩，提高性能和效率。
我們上面可知瘪匿，object對象的hashcode與對象內(nèi)存地址一一對應跛梗，表示對象的唯一性。而通過hashcode計算出key對象的hash值也是唯一的棋弥，且對于同一個key對象核偿，任何時候重復計算都會得到同樣的hash值，從而定位出在數(shù)組中的位置顽染。
hashcode計算出hash值的公式：
在JDK8中漾岳，由于使用了紅黑樹來處理大的鏈表開銷轰绵，所以hash這邊可以更加省力了，只用計算hashCode并移動到低位就可以了尼荆。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里的Hash算法本質(zhì)上就是三步：取key的hashCode值左腔、高位運算、取模運算捅儒。
根據(jù)hash值計算在table[] 數(shù)組中的位置公式：
int index = (hash & 0x7FFFFFFF) % table.length;
因為某些對象的 hashCode 可能會為負值液样，與 0x7FFFFFFF 進行與運算可以確保 index 為一個正數(shù)。
插入
HashMap的put()方法源碼為：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//table為空則創(chuàng)建
if ((tab = table) == null || (n = tab.length) == 0){
n = (tab = resize()).length;
}
//計算index巧还，并對null做處理
if ((p = tab[i = (n - 1) & hash]) == null){
tab[i] = newNode(hash, key, value, null);
}else {
Node<K,V> e; K k;
//節(jié)點hash值同鞭莽，且key值與插入key相同，直接覆蓋value
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
} else if (p instanceof TreeNode){
//判斷該鏈為紅黑樹
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
//已經(jīng)產(chǎn)生碰撞狞悲，采用鏈地址法解決沖突
for (int binCount = 0; ; ++binCount) {
//p第一次指向鏈表頭,以后依次后移
if ((e = p.next) == null) {
//e為空撮抓，表示已到鏈表尾也沒有找到key值相同節(jié)點，則新建節(jié)點
p.next = newNode(hash, key, value, null);
//鏈表長度大于8轉(zhuǎn)換為紅黑樹進行處理
if (binCount >= TREEIFY_THRESHOLD - 1) {
// -1 for 1st
treeifyBin(tab, hash);
}
break;
}
//容許null==null
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
//更新p指向下一個節(jié)點
p = e;
}
}
//更新hash值和key值均相同的節(jié)點Value值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//超過最大容量 就擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
整體流程為：
- 對key的hashCode()做hash摇锋，然后再計算index;
- 如果沒碰撞直接放到哈希桶數(shù)組里丹拯；
- 如果碰撞了，以鏈表的形式存在哈希桶數(shù)組后荸恕；
- 如果碰撞導致鏈表過長(大于等于TREEIFY_THRESHOLD)乖酬，就把鏈表轉(zhuǎn)換成紅黑樹；
- 如果節(jié)點已經(jīng)存在就替換old value(保證key的唯一性)
- 如果哈希桶數(shù)組滿了(超過load factor*current capacity)融求，就要擴容咬像。
在上面HashMap的插入過程中，如果出現(xiàn)兩個key定位到同一個數(shù)組位置生宛，表示發(fā)生了Hash碰撞县昂。
哈希表為解決碰撞（沖突），可以采用開放地址法和鏈地址法等來解決問題陷舅，Java中HashMap采用了鏈地址法倒彰。
鏈地址法，簡單來說莱睁，就是數(shù)組加鏈表的結(jié)合待讳。
取值
HashMap的get()方法源碼為：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//hash & (length-1)得到對象key的存儲索引
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//hash碼相同且key與要get的key的相同則返回數(shù)組此處的Node，之后轉(zhuǎn)化為value
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果第一個節(jié)點是TreeNode,說明采用的是數(shù)組+紅黑樹結(jié)構(gòu)處理沖突
if (first instanceof TreeNode){
//遍歷紅黑樹仰剿，得到節(jié)點值
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
}
//鏈表結(jié)構(gòu)處理
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
整體流程為：
- 在哈希桶數(shù)組里的第一個節(jié)點创淡，直接命中；
- 如果有沖突（碰撞）南吮，則通過key.equals(k)去查找
- 若為樹琳彩，則在樹中通過key.equals(k)查找，O(logn)；
- 若為鏈表汁针，則在鏈表中通過key.equals(k)查找术辐，O(n)。
小結(jié)
- 擴容是一個特別耗性能的操作施无，所以當程序員在使用HashMap的時候辉词，估算map的大小，初始化的時候給一個大致的數(shù)值猾骡，避免map進行頻繁的擴容瑞躺。
- 負載因子是可以修改的，也可以大于1兴想，但是建議不要輕易修改幢哨，除非情況非常特殊。
- HashMap是線程不安全的嫂便，不要在并發(fā)的環(huán)境中同時操作HashMap捞镰，建議使用ConcurrentHashMap。
- JDK1.8引入紅黑樹大程度優(yōu)化了HashMap的性能毙替。
- 還沒升級JDK1.8的岸售，現(xiàn)在開始升級吧。HashMap的性能提升僅僅是JDK1.8的冰山一角厂画。
