- HashMap概述：
HashMap是基于哈希表的Map接口的非同步實現(xiàn)蜗巧。此實現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵扔罪。此類不保證映射的順序娇掏，特別是它不保證該順序恒久不變。 -
HashMap的數(shù)據(jù)結(jié)構(gòu)：
在java編程語言中空执，最基本的結(jié)構(gòu)就是兩種浪箭，一個是數(shù)組，另外一個是模擬指針（引用）辨绊，所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的奶栖，HashMap也不例外。HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體宣鄙。
042032ea-6f15-3428-bfb4-b3b1460769a7.jpg
從上圖中可以看出袍镀，HashMap底層就是一個數(shù)組結(jié)構(gòu)，數(shù)組中的每一項又是一個鏈表冻晤。當新建一個HashMap的時候苇羡，就會初始化一個數(shù)組。
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
可以看出鼻弧，Entry就是數(shù)組中的元素设江，每個 Map.Entry 其實就是一個key-value對，它持有一個指向下一個元素的引用攘轩，這就構(gòu)成了鏈表叉存。
兩個重要的參數(shù)
在HashMap中有兩個很重要的參數(shù)，容量(Capacity)和負載因子(Load factor)
簡單的說度帮，Capacity就是buckets的數(shù)目歼捏，Load factor就是buckets填滿程度的最大比例。如果對迭代性能要求很高的話不要把capacity設(shè)置過大够傍，也不要把load factor設(shè)置過小甫菠。當bucket填充的數(shù)目（即hashmap中元素的個數(shù)）大于capacity*load factor時就需要調(diào)整buckets的數(shù)目為當前的2倍挠铲。put函數(shù)的實現(xiàn)
put函數(shù)大致的思路為：
（1）對key的hashCode()做hash冕屯，然后再計算index;
（2）如果沒碰撞直接放到bucket里；
（3）如果碰撞了拂苹，以鏈表的形式存在buckets后安聘；
（4）如果碰撞導致鏈表過長(大于等于TREEIFY_THRESHOLD)，就把鏈表轉(zhuǎn)換成紅黑樹瓢棒；
（5）如果節(jié)點已經(jīng)存在就替換old value(保證key的唯一性)
（6）如果bucket滿了(超過load factor*current capacity)浴韭，就要resize。
具體代碼的實現(xiàn)如下：
public V put(K key, V value) {
// 對key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// tab為空則創(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é)點存在
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 {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
p = e;
}
}
// 寫入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超過load factor*current capacity念颈，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- get函數(shù)的實現(xiàn)
在理解了put之后，get就很簡單了连霉。大致思路如下：
（1）先對key的hashCode()做hash榴芳，然后計算出index；
（2）根據(jù)index找到table位置跺撼，如果bucket里的只有一個節(jié)點窟感，直接命中；
（3）如果bucket里有多個節(jié)點歉井，則通過key.equals(k)去查找對應的entry
（4）若bucket結(jié)構(gòu)為樹柿祈，則在樹中通過key.equals(k)查找，O(logn)；
（5）若bucket結(jié)構(gòu)為鏈表躏嚎，則在鏈表中通過key.equals(k)查找蜜自，O(n)。
具體代碼的實現(xiàn)如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未命中
if ((e = first.next) != null) {
// 在樹中g(shù)et
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在鏈表中g(shù)et
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
-
hash函數(shù)的實現(xiàn)
在get和put的過程中紧索，計算下標時袁辈，先對hashCode進行hash操作，然后再通過hash值進一步計算下標珠漂，如下圖所示：
293b52fc-d932-11e4-854d-cb47be67949a.png
在對hashCode()計算hash時具體實現(xiàn)是這樣的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到這個函數(shù)大概的作用就是：高16bit不變晚缩，低16bit和高16bit做了一個異或。其中代碼注釋是這樣寫的：
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.
在設(shè)計hash函數(shù)時媳危，因為目前的table長度n為2的冪荞彼，而計算下標的時候，是這樣實現(xiàn)的(使用&位操作待笑，而非%求余)：
(n - 1) & hash
設(shè)計者認為這方法很容易發(fā)生碰撞鸣皂。為什么這么說呢？不妨思考一下暮蹂，在n - 1為15(0x1111)時寞缝，其實散列真正生效的只是低4bit的有效位，當然容易碰撞了仰泻。
因此荆陆，設(shè)計者想了一個顧全大局的方法(綜合考慮了速度、作用集侯、質(zhì)量)被啼，就是把高16bit和低16bit異或了一下。設(shè)計者還解釋到因為現(xiàn)在大多數(shù)的hashCode的分布已經(jīng)很不錯了棠枉，就算是發(fā)生了碰撞也用O(logn)的tree去做了浓体。僅僅異或一下，既減少了系統(tǒng)的開銷辈讶，也不會造成的因為高位沒有參與下標的計算(table長度比較小時)命浴，從而引起的碰撞。
如果還是產(chǎn)生了頻繁的碰撞贱除，會發(fā)生什么問題呢生闲？作者注釋說，他們使用樹來處理頻繁的碰撞(we use trees to handle large sets of collisions in bins)勘伺，在JEP-180中跪腹，描述了這個問題：
Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.
之前已經(jīng)提過，在獲取HashMap的元素時飞醉，基本分兩步：
（1） 首先根據(jù)hashCode()做hash冲茸，然后確定bucket的index屯阀；
（2） 如果bucket的節(jié)點的key不是我們需要的，則通過keys.equals()在鏈中找轴术。
在Java 8之前的實現(xiàn)中是用鏈表解決沖突的难衰，在產(chǎn)生碰撞的情況下，進行g(shù)et時逗栽，兩步的時間復雜度是O(1)+O(n)盖袭。因此，當碰撞很厲害的時候n很大彼宠，O(n)的速度顯然是影響速度的鳄虱。
因此在Java 8中，利用紅黑樹替換鏈表凭峡，這樣復雜度就變成了O(1)+O(logn)了拙已，這樣在n很大的時候，能夠比較理想的解決這個問題摧冀，在Java 8：HashMap的性能提升一文中有性能測試的結(jié)果倍踪。
- RESIZE的實現(xiàn)
當put時，如果發(fā)現(xiàn)目前的bucket占用程度已經(jīng)超過了Load Factor所希望的比例索昂，那么就會發(fā)生resize建车。在resize的過程，簡單的說就是把bucket擴充為2倍椒惨，之后重新計算index缤至，把節(jié)點再放到新的bucket中。resize的注釋是這樣描述的：
Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
大致意思就是說框产，當超過限制的時候會resize凄杯，然而又因為我們使用的是2次冪的擴展(指長度擴為原來2倍)错洁，所以秉宿，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置屯碴。
怎么理解呢描睦？例如我們從16擴展為32時，具體的變化如下所示：
因此元素在重新計算hash之后导而，因為n變?yōu)?倍忱叭，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：
因此今艺，我們在擴充HashMap的時候韵丑，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了虚缎，是0的話索引沒變撵彻，是1的話索引變成“原索引+oldCap”。可以看看下圖為16擴充為32的resize示意圖：
這個設(shè)計確實非常的巧妙陌僵，既省去了重新計算hash值的時間轴合，而且同時，由于新增的1bit是0還是1可以認為是隨機的碗短，因此resize的過程受葛，均勻的把之前的沖突的節(jié)點分散到新的bucket了。
下面是代碼的具體實現(xiàn)：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超過最大值就不再擴充了偎谁，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值总滩，就擴充為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
- 總結(jié)
（1） 什么時候會使用HashMap？他有什么特點巡雨？
是基于Map接口的實現(xiàn)咳秉，存儲鍵值對時，它可以接收null的鍵值鸯隅，是非同步的澜建，HashMap存儲著Entry(hash, key, value, next)對象。
（2）你知道HashMap的工作原理嗎蝌以？
通過hash的方法炕舵，通過put和get存儲和獲取對象。存儲對象時跟畅，我們將K/V傳給put方法時咽筋，它調(diào)用hashCode計算hash從而得到bucket位置，進一步存儲徊件，HashMap會根據(jù)當前bucket的占用情況自動調(diào)整容量(超過Load Facotr則resize為原來的2倍)奸攻。獲取對象時，我們將K傳給get虱痕，它調(diào)用hashCode計算hash從而得到bucket位置睹耐，并進一步調(diào)用equals()方法確定鍵值對。如果發(fā)生碰撞的時候部翘，Hashmap通過鏈表將產(chǎn)生碰撞沖突的元素組織起來硝训，在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(默認是8)新思，則使用紅黑樹來替換鏈表窖梁，從而提高速度。
（3）你知道get和put的原理嗎夹囚？equals()和hashCode()的都有什么作用纵刘？
通過對key的hashCode()進行hashing，并計算下標( n-1 & hash)荸哟，從而獲得buckets的位置假哎。如果產(chǎn)生碰撞蛔翅，則利用key.equals()方法去鏈表或樹中去查找對應的節(jié)點
（4）你知道hash的實現(xiàn)嗎？為什么要這樣實現(xiàn)位谋？
在Java 1.8的實現(xiàn)中山析，是通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度掏父、功效笋轨、質(zhì)量來考慮的，這么做可以在bucket的n比較小的時候赊淑，也能保證考慮到高低bit都參與到hash的計算中爵政，同時不會有太大的開銷。
（5） 如果HashMap的大小超過了負載因子(load factor)定義的容量陶缺，怎么辦钾挟？
如果超過了負載因子(默認0.75)，則會重新resize一個原來長度兩倍的HashMap饱岸，并且重新調(diào)用hash方法掺出。
