一、hashmap 數(shù)據(jù)結(jié)構(gòu)
HashMap 主要的操作一般包括：
- V put(K key, V value)
- V get(Object key)
- V remove(Object key)
- Boolean containsKey(Object key)
jdk7 之前的hashmap
HashMap內(nèi)部存儲數(shù)據(jù)的方式是通過內(nèi)部類Entry 來實現(xiàn)的混槐，其中Entry 類的結(jié)構(gòu)如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;//key 的hash 值
Entry<K,V> next;//指向該entry下一個元素
int hash;
}
HashMap put操作
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)//key 為null,
return putForNullKey(value);
int hash = hash(key);//獲取key 的hash 值
int i = indexFor(hash, table.length);//將hash 值映射到數(shù)組中對應(yīng)的索引位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//如果該元素在hashmap 中已存在赛糟，則替換原有的值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);//添加新的entry 元素到hashmap 中
return null;
}
hashmap內(nèi)部存儲的結(jié)構(gòu)尘执，其實就是一個entry 的數(shù)組礼搁，然后數(shù)組的每個位置(也稱之為bucket)存儲的是一個entry 的單鏈表瀑构，如下圖所示葫掉。
- hash(key)相同的元素些举，存放在同一個entry 單鏈表中，
- 不同的元素俭厚，存放在entry 數(shù)組中不同的bucket中
當(dāng)進(jìn)行g(shù)et (key) 操作時户魏，首先會計算key對應(yīng)在數(shù)組的位置，然后根據(jù)key 的equal() 方法挪挤，遍歷entry 單鏈表 叼丑，找到對應(yīng)key 的值，反之 put(key,value)操作時類似扛门，不同之處在于鸠信，是將該元素插入到entry 鏈表的頭部。
整個bucket 鏈表的形成過程可以分為如下幾步:
- 獲取key 的hashcode 值
- 為了減少hash 沖突论寨，需要對hashcode 值進(jìn)行rehash 操作 （java8中hashcode右移16位 與hashcode 做異或運(yùn)算星立，即高位與低位）
- 為了讓元素存放到數(shù)組中對應(yīng)的索引位置，需要對rehash 后的值與（數(shù)組長度-1）進(jìn)行位運(yùn)算葬凳。
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
//讓hashcode 的每一位都參與到了運(yùn)算中來绰垂，減少了hash 沖突的發(fā)生
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
hashmap 什么情況下出現(xiàn)單鏈表
在createEntry方法中，主要有兩步操作：
-
Entry<K,V> e = table[bucketIndex]獲取數(shù)組中原來索引index位置的entry對象火焰。 - 創(chuàng)建一個新的entry 對象 放入到數(shù)組中索引index位置處劲装，
table[bucketIndex] = new Entry<>(hash, key, value, e);，從Entry 的構(gòu)造函數(shù)就可以知道荐健，如果原來的索引index位置的數(shù)據(jù)對象e 不為null酱畅，則此時新entry對象next->e琳袄。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
hashmap 擴(kuò)容操作
hashmap 的一系列操作（get，put纺酸，remove）都會涉及到map中單鏈表的key遍歷查找操作窖逗，假使忽略修改操作，這也是一個非常消耗性能的issue餐蔬，例如碎紊，hashmap 的數(shù)組大小為16，存放20w的數(shù)據(jù)樊诺，在這種場景下仗考，每一個entry 鏈表的平均大小為20w/16，這種情況之下一個key 的遍歷查找次數(shù)和一個很可怕的數(shù)字词爬，在這種情況之下秃嗜，為了避免這種長度巨大的單鏈表的產(chǎn)生，hashmap有了一個自動擴(kuò)容的操作顿膨，即resize锅锨。下面兩個圖，分別展示了擴(kuò)容前后map 中數(shù)據(jù)分布情況恋沃。
hashmap 的默認(rèn)初始大小為16
DEFAULT_INITIAL_CAPACITY = 1 << 4必搞，負(fù)載因子為DEFAULT_LOAD_FACTOR = 0.75f
為什么hashmap 不是線程安全的？
因為囊咏，在hashmap 自動擴(kuò)容的過程中恕洲，get和put 操作時，有可能獲得是擴(kuò)容前的數(shù)據(jù)梅割，更糟糕的情況是霜第，并發(fā)情況下，多個線程同時進(jìn)行put 操作炮捧，此時可能會引起resize 操作庶诡，導(dǎo)致entry 鏈表中形成一個循環(huán)鏈表。
jdk8 hashmap
java8 中hashmap 有了很大的改進(jìn)咆课，java8 中hashmap 內(nèi)部還是通過數(shù)組的存儲方式，只不過扯俱，數(shù)組中存儲的單元由java7 中的Entry 換成了Node,但是類結(jié)構(gòu)和包含的信息是一樣的书蚪，與java7 最大的不同之處在于Node 可以擴(kuò)展成TreeNode，其中TreeNode 可以擴(kuò)展成紅黑樹的數(shù)據(jù)結(jié)構(gòu)迅栅，如下圖所示殊校。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
什么情況下擴(kuò)展成紅黑樹呢?
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//當(dāng)前hashmap 為空，觸發(fā)map 的自動擴(kuò)容resize 操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//i = (n - 1) & hash 就是java7 中的indexFor 的操作读存，判斷數(shù)組當(dāng)前位置是否已經(jīng)為空为流，如果為空呕屎，就實例化一個node，將該node放入數(shù)組中這個索引位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//key 存在敬察，就替換掉原有的value,與java 7 類似
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);
//當(dāng)單鏈表的長度大于等于TREEIFY_THRESHOLD - 1時秀睛，鏈表就轉(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;
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
為什么HashMap 數(shù)組大小是2的冪次方
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
假如數(shù)組的長度為17，參與位運(yùn)算值為length-1=16莲祸，對應(yīng)的二進(jìn)制為0000,....,0001,0000,此時任意一個數(shù)h與16 進(jìn)行位運(yùn)算蹂安，結(jié)果只有16,0兩種結(jié)果，這意味著數(shù)組只有兩個bucket锐帜，再有元素存放hashmap 時田盈，必然會發(fā)生hash 沖突，導(dǎo)致hashmap 變成了兩個單鏈表缴阎。
而假如數(shù)組長度為16允瞧，參與位運(yùn)算的值為15，對應(yīng)的二進(jìn)制為0000,....,0000,1111蛮拔，瓷式，此時任意一個數(shù)與15 位運(yùn)算后，結(jié)果必然在[0,15]之間语泽，這剛好對應(yīng)著數(shù)組的下標(biāo)索引贸典。
這就是為什么hashmap 中數(shù)組的大小必須為2 的冪次方。
為什么 hashmap 會出現(xiàn)死循環(huán)
參考
疫苗：JAVA HASHMAP的死循環(huán)
JDK7與JDK8中HashMap的實現(xiàn)
How does a HashMap work in JAVA
(譯)Java7/Java8中HashMap解析
