資訊專(zhuān)欄INFORMATION COLUMN
摘要：哈希碰撞的概率取決于計(jì)算方式和空間容量的大小。超過(guò)后執(zhí)行擴(kuò)容操作。當(dāng)一個(gè)哈希桶存儲(chǔ)的鏈表長(zhǎng)度大于會(huì)將鏈表轉(zhuǎn)換成紅黑樹(shù)，小于時(shí)則從紅黑樹(shù)轉(zhuǎn)換成鏈表。換句話(huà)來(lái)說(shuō)，就是為了減少哈希碰撞。紅黑樹(shù)相關(guān)的操作雖然代碼不同，但是實(shí)際上要干的事情是一樣的。
前言
學(xué)習(xí)情況記錄
學(xué)習(xí)情況記錄
時(shí)間：week 3
SMART子目標(biāo) ：Java 容器
記錄在學(xué)習(xí)Java容器 知識(shí)點(diǎn)中，關(guān)于HashMap的需要重點(diǎn)記錄的知識(shí)點(diǎn)。
知識(shí)點(diǎn)概覽：
一、hashCode()
二、HashMap 底層實(shí)現(xiàn)
簡(jiǎn)介
存儲(chǔ)結(jié)構(gòu)
重要屬性
增加元素操作
Q: HashMap 的長(zhǎng)度為什么默認(rèn)初始長(zhǎng)度是16，并且每次resize()的時(shí)候，長(zhǎng)度必須是2的冪次方？
HashMap 擴(kuò)容
Q: HashMap 死鏈問(wèn)題
Java 8 與 Java 7對(duì)比
為什么要使用紅黑樹(shù)？
三、結(jié)語(yǔ)
一、hashCode()在Object 類(lèi)中，hashCode()方法是一個(gè)被native修飾的類(lèi)，JavaDoc中描述的是返回該對(duì)象的哈希值。
那么哈希值這個(gè)返回值是有什么作用呢？
主要是保證基于散列的集合，如HashSet、HashMap以及HashTable等，在插入元素時(shí)保證元素不可重復(fù)，同時(shí)為了提高元素的插入刪除便利效率而設(shè)計(jì)；主要是為了查找的便捷性而存在。
拿Set進(jìn)行舉例，
眾所周知，Set集合是不能重復(fù)，如果每次添加數(shù)據(jù)都拿新元素去和集合內(nèi)部元素進(jìn)行逐一地equal()比較，那么插入十萬(wàn)條數(shù)據(jù)的效率可以說(shuō)是非常低的。
所以在添加數(shù)據(jù)的時(shí)候就出現(xiàn)了哈希表的應(yīng)用，哈希算法也稱(chēng)之為散列算法，當(dāng)添加一個(gè)值的時(shí)候，先去計(jì)算出它的哈希值，根據(jù)算出的哈希值將數(shù)據(jù)插入指定位置。這樣的話(huà)就避免了一直去使用equal()比較的效率問(wèn)題。
具體表現(xiàn)在：
如果指定位置為空，則直接添加
如果指定位置不為空，調(diào)用equal() 判斷兩個(gè)元素是否相同，如果相同則不存儲(chǔ)
上述第二種情況中，如果兩個(gè)元素不相同，但是hashCode()相同，那就是發(fā)生了我們所謂的哈希碰撞。
哈希碰撞的概率取決于hashCode()計(jì)算方式和空間容量的大小。
這種情況下，會(huì)在相同的位置，創(chuàng)建一個(gè)鏈表，把key值相同的元素存放到鏈表中。
在HashMap中就是使用拉鏈法來(lái)解決hashCode沖突。
總結(jié)hashCode是一個(gè)對(duì)象的標(biāo)識(shí)，Java中對(duì)象的hashCode是一個(gè)int類(lèi)型值。通過(guò)hashCode來(lái)指定數(shù)組的索引可以快速定位到要找的對(duì)象在數(shù)組中的位置，之后再遍歷鏈表找到對(duì)應(yīng)值，理想情況下時(shí)間復(fù)雜度為O(1)，并且不同對(duì)象可以擁有相同的hashCode。
二、HashMap 底層實(shí)現(xiàn) 0. 簡(jiǎn)介HashMap 基于哈希表的Map接口實(shí)現(xiàn)的，是以Key-Value存儲(chǔ)形式存在；
非線(xiàn)程安全；
key value都可以為null；
HashMap中的映射不是有序的；
在 JDK1.8 中，HashMap 是由 數(shù)組+鏈表+紅黑樹(shù)構(gòu)成，新增了紅黑樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)；
當(dāng)一個(gè)哈希桶存儲(chǔ)的鏈表長(zhǎng)度大于8 會(huì)將鏈表轉(zhuǎn)換成紅黑樹(shù)，小于6時(shí)則從紅黑樹(shù)轉(zhuǎn)換成鏈表；
1.8之前和1.8及以后的源碼，差別較大
1. 存儲(chǔ)結(jié)構(gòu)在 JDK1.8 中，HashMap 是由 數(shù)組+鏈表+紅黑樹(shù)構(gòu)成，新增了紅黑樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)。
通過(guò)哈希來(lái)確認(rèn)到數(shù)組的位置，如果發(fā)生哈希碰撞就以鏈表的形式存儲(chǔ) ，但是這樣如果鏈表過(guò)長(zhǎng)來(lái)的話(huà)，HashMap會(huì)把這個(gè)鏈表轉(zhuǎn)換成紅黑樹(shù)來(lái)存儲(chǔ)，閾值為8。
下面是HashMap的結(jié)構(gòu)圖：
2. 重要屬性 2.1 table /**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node[] table;
在JDK1.8中我們了解到HashMap是由數(shù)組加鏈表加紅黑樹(shù)來(lái)組成的結(jié)構(gòu)其中table就是HashMap中的數(shù)組。
2.2 size /**
* The number of key-value mappings contained in this map.
*/
transient int size;
HashMap中 鍵值對(duì)存儲(chǔ)數(shù)量。
2.3 loadFactor /**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
負(fù)載因子。負(fù)載因子是權(quán)衡資源利用率與分配空間的系數(shù)。當(dāng)元素總量 > 數(shù)組長(zhǎng)度 * 負(fù)載因子 時(shí)會(huì)進(jìn)行擴(kuò)容操作。
2.4 threshold /**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
擴(kuò)容閾值。threshold = 數(shù)組長(zhǎng)度 * 負(fù)載因子。超過(guò)后執(zhí)行擴(kuò)容操作。
2.5 TREEIFY_THRESHOLD/UNTREEIFY_THRESHOLD /**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
樹(shù)形化閾值。當(dāng)一個(gè)哈希桶存儲(chǔ)的鏈表長(zhǎng)度大于8 會(huì)將鏈表轉(zhuǎn)換成紅黑樹(shù)，小于6時(shí)則從紅黑樹(shù)轉(zhuǎn)換成鏈表。
3. 增加元素 public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
3.1 hash()
可以看到實(shí)際執(zhí)行添加元素的是putVal()操作，在執(zhí)行putVal()之前，先是對(duì)key執(zhí)行了hash()方法，讓我們看下里面做了什么
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位異或
// >>>:無(wú)符號(hào)右移，忽略符號(hào)位，空位都以0補(bǔ)齊
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key==null說(shuō)明，HashMap中是支持key為null的情況的。
同樣的方法在Hashstable中是直接用key來(lái)獲取hashCode，沒(méi)有key==null的判斷，所以Hashstable是不支持key為null的。
再回來(lái)說(shuō)這個(gè)hash()方法。這個(gè)方法用專(zhuān)業(yè)術(shù)語(yǔ)來(lái)稱(chēng)呼就叫做擾動(dòng)函數(shù)。
使用hash()也就是擾動(dòng)函數(shù)，是為了防止一些實(shí)現(xiàn)比較差的hashCode()方法。換句話(huà)來(lái)說(shuō)，就是為了減少哈希碰撞。
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡(jiǎn)化，但是原理不變。我們?cè)倏聪翵DK1.7中是怎么做的。
// code in JDK1.7
static int hash(int h) {
// 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).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能會(huì)稍差一點(diǎn)點(diǎn)，因?yàn)楫吘箶_動(dòng)了 4 次。
3.2 putVal()再來(lái)看真正執(zhí)行增加元素操作的putVal()方法，
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// 當(dāng)數(shù)組為空或長(zhǎng)度為0，初始化數(shù)組容量（resize() 方法是初始化或者擴(kuò)容用的）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計(jì)算數(shù)組下標(biāo) i = (n-1) & hash
// 如果這個(gè)位置沒(méi)有元素，則直接創(chuàng)建Node并存值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 這個(gè)位置已有元素
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// hash值、key值相等，用e變量獲取到當(dāng)前位置這個(gè)元素的引用，后面用于替換已有的值
e = p;
else if (p instanceof TreeNode)
// 當(dāng)前是以紅黑樹(shù)方式存儲(chǔ)，執(zhí)行其特有的putVal方法 -- putTreeVal
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// 當(dāng)前是以鏈表方式存儲(chǔ)，開(kāi)始遍歷鏈表
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
// 超過(guò)閾值，存儲(chǔ)方式轉(zhuǎn)化成紅黑樹(shù)
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)
// onlyIfAbsent 如果為true - 不覆蓋已存在的值
// 把新值賦值進(jìn)去
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 記錄修改次數(shù)
++modCount;
// 判斷元素?cái)?shù)量是否超過(guò)閾值 超過(guò)則擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3.3 HashMap 的長(zhǎng)度為什么默認(rèn)初始長(zhǎng)度是16，并且每次resize()的時(shí)候，長(zhǎng)度必須是2的冪次方？
這是一個(gè)常見(jiàn)的面試題。這個(gè)問(wèn)題描述的設(shè)計(jì)，實(shí)際上為了服務(wù)于從Key映射到數(shù)組下標(biāo)index的Hash算法。
前面提到了，我們?yōu)榱俗孒ashMap存儲(chǔ)高效，應(yīng)該盡量減少哈希碰撞，也就是說(shuō)，應(yīng)該讓元素分配得盡可能均勻。
Hash 值的范圍值-2147483648到2147483647，前后加起來(lái)大概40億的映射空間，只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的。但問(wèn)題是一個(gè)40億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的。所以這個(gè)散列值是不能直接拿來(lái)用的。
所以才需要一個(gè)映射的算法。這個(gè)計(jì)算方式就是3.2中有出現(xiàn)的(n - 1) & hash。
我們來(lái)進(jìn)一步演示一下這個(gè)算法：
假設(shè)有一個(gè)key="book"
計(jì)算book的hashCode值，結(jié)果為十進(jìn)制的3029737，二進(jìn)制的101110001110101110 1001。
假定HashMap長(zhǎng)度是默認(rèn)的16，計(jì)算Length-1的結(jié)果為十進(jìn)制的15，二進(jìn)制的1111。
把以上兩個(gè)結(jié)果做與運(yùn)算，101110001110101110 1001 & 1111 = 1001，十進(jìn)制是9，所以 index=9。
通過(guò)這種與運(yùn)算的方式，能夠和取模運(yùn)算一樣的效果hashCode % length，在上述例子中就是3029737 % 16=9。
并且通過(guò)位運(yùn)算的方式大大提高了性能。
可能到這里，你還是不知道為什么長(zhǎng)度必須是2的冪次方，也是因?yàn)檫@種位運(yùn)算的方法。
長(zhǎng)度16或者其他2的冪，Length-1的值是所有二進(jìn)制位全為1，這種情況下，index的結(jié)果等同于HashCode后幾位的值。只要輸入的HashCode本身分布均勻，Hash算法的結(jié)果就是均勻的。如果HashMap的長(zhǎng)度不是2的冪次方，會(huì)出現(xiàn)某些index永遠(yuǎn)不會(huì)出現(xiàn)的情況，這個(gè)顯然不符合均勻分布的原則和期望。所以在源碼里面一直都在強(qiáng)調(diào)power-of-two expansion和size must be power of two。
另外，HashMap 構(gòu)造函數(shù)允許用戶(hù)傳入的容量不是 2 的 n 次方，因?yàn)樗梢宰詣?dòng)地將傳入的容量轉(zhuǎn)換為 2 的 n 次方。
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
4. HashMap 擴(kuò)容
接下來(lái)我們來(lái)講講HashMap擴(kuò)容相關(guān)的知識(shí)。
4.1 擴(kuò)容HashMap的初始長(zhǎng)度是16，假設(shè)HashMap中的鍵值對(duì)一直在增加，但是table數(shù)組容量一直不變，那么就會(huì)發(fā)生哈希碰撞，查找的效率肯定會(huì)越來(lái)越低。所以當(dāng)鍵值對(duì)數(shù)量超過(guò)某個(gè)閾值的時(shí)候，HashMap就會(huì)執(zhí)行擴(kuò)容操作。
那么擴(kuò)容的閾值是怎么計(jì)算的呢？
閾值 = 數(shù)組長(zhǎng)度 * 負(fù)載因子threshold = capacity * loadFactor
每次擴(kuò)容后，threshold 加倍
上述計(jì)算就出現(xiàn)在resize()方法中。下面會(huì)詳細(xì)解析這個(gè)方法。我們先繼續(xù)往下講。
loadFactor這個(gè)參數(shù)，我們之前提到過(guò)，負(fù)載因子是權(quán)衡資源利用率與分配空間的系數(shù)。至于為什么是0.75呢？這個(gè)實(shí)際上就是一個(gè)作者認(rèn)為比較好的權(quán)衡，當(dāng)然你也可以通過(guò)構(gòu)造方法手動(dòng)設(shè)置負(fù)載因子 。public HashMap(int initialCapacity, float loadFactor) {...)。
接下去再來(lái)到這里的主角resize()方法
