「Java」HashMap底層實(shí)現(xiàn)、加載因子、容量值及死循環(huán)
HashMap 簡(jiǎn)介
HashMap是一個(gè)基于哈希表實(shí)現(xiàn)的無序的key-value容器，它鍵和值允許設(shè)置為 null，同時(shí)它是線程不安全的。
HashMap 底層實(shí)現(xiàn)
- 在jdk 1.7中HashMap是以數(shù)組+鏈表的實(shí)現(xiàn)的
- 在jdk1.8開始引入紅黑樹，HashMap底層變成了數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)
紅黑樹簡(jiǎn)介
紅黑樹是一種特殊的平衡二叉樹，它有如下的特征：
- 節(jié)點(diǎn)是紅色或黑色
- 根節(jié)點(diǎn)是黑色的
- 所有葉子都是黑色。（葉子是NULL節(jié)點(diǎn)）
- 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）
- 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
所以紅黑樹的時(shí)間復(fù)雜度為: O(lgn)。
jdk1.8：數(shù)組+鏈表+紅黑樹
HashMap的底層首先是一個(gè)數(shù)組，元素存放的數(shù)組索引值就是由該元素的哈希值（key-value中key的哈希值）確定的，這就可能產(chǎn)生一種特殊情況——不同的key哈希值相同。
在這樣的情況下，于是引入鏈表，如果key的哈希值相同，在數(shù)組的該索引中存放一個(gè)鏈表，這個(gè)鏈表就包含了所有key的哈希值相同的value值，這就解決了哈希沖突的問題。
但是如果發(fā)生大量哈希值相同的特殊情況，導(dǎo)致鏈表很長，就會(huì)嚴(yán)重影響HashMap的性能，因?yàn)殒湵淼牟樵冃市枰闅v所有節(jié)點(diǎn)。于是在jdk1.8引入了紅黑樹，當(dāng)鏈表的長度大于8，且HashMap的容量大于64的時(shí)候，就會(huì)將鏈表轉(zhuǎn)化為紅黑樹。
- // jdk1.8
- // HashMap#putVal
- // binCount 是該鏈表的長度計(jì)數(shù)器，當(dāng)鏈表長度大于等于8時(shí)，執(zhí)行樹化方法
- // TREEIFY_THRESHOLD = 8
- if (binCount >= TREEIFY_THRESHOLD - 1)
- treeifyBin(tab, hash);
- // HashMap#treeifyBin
- final void treeifyBin(Node<K,V>[] tab, int hash) {
- int n, index; Node<K,V> e;
- // MIN_TREEIFY_CAPACITY=64
- // 若 HashMap 的大小小于64，僅擴(kuò)容，不樹化
- 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 ((ee = e.next) != null);
- if ((tab[index] = hd) != null)
- hd.treeify(tab);
- }
- }
加載因子為什么是0.75
所謂的加載因子，也叫擴(kuò)容因子或者負(fù)載因子，它是用來進(jìn)行擴(kuò)容判斷的。
假設(shè)加載因子是0.5，HashMap初始化容量是16，當(dāng)HashMap中有16 * 0.5=8個(gè)元素時(shí)，HashMap就會(huì)進(jìn)行擴(kuò)容操作。
而HashMap中加載因子為0.75，是考慮到了性能和容量的平衡。
由加載因子的定義，可以知道它的取值范圍是(0, 1]。
- 如果加載因子過小，那么擴(kuò)容門檻低，擴(kuò)容頻繁，這雖然能使元素存儲(chǔ)得更稀疏，有效避免了哈希沖突發(fā)生，同時(shí)操作性能較高，但是會(huì)占用更多的空間。
- 如果加載因子過大，那么擴(kuò)容門檻高，擴(kuò)容不頻繁，雖然占用的空間降低了，但是這會(huì)導(dǎo)致元素存儲(chǔ)密集，發(fā)生哈希沖突的概率大大提高，從而導(dǎo)致存儲(chǔ)元素的數(shù)據(jù)結(jié)構(gòu)更加復(fù)雜（用于解決哈希沖突），最終導(dǎo)致操作性能降低。
- 還有一個(gè)因素是為了提升擴(kuò)容效率。因?yàn)镠ashMap的容量（size屬性，構(gòu)造函數(shù)中的initialCapacity變量）有一個(gè)要求：它一定是2的冪。所以加載因子選擇了0.75就可以保證它與容量的乘積為整數(shù)。
- // 構(gòu)造函數(shù)
- public HashMap(int initialCapacity, float loadFactor) {
- // ……
- this.loadFactor = loadFactor;// 加載因子
- this.threshold = tableSizeFor(initialCapacity);
- }
- /**
- * Returns a power of two size for the given target capacity.返回2的冪
- * MAXIMUM_CAPACITY = 1 << 30
- */
- 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;
- }
HashMap 的容量為什么是2的 n 次冪
HashMap的默認(rèn)初始容量是16，而每次擴(kuò)容是擴(kuò)容為原來的2倍。這里的16和2倍就保證了HashMap的容量是2的n次冪，那么這樣設(shè)計(jì)的原因是什么呢？
原因一：與運(yùn)算高效
與運(yùn)算&，基于二進(jìn)制數(shù)值，同時(shí)為1結(jié)果為1，否則就是0。如1&1=1,1&0=0,0&0=0。使用與運(yùn)算的原因就是對(duì)于計(jì)算機(jī)來說，與運(yùn)算十分高效。
原因二：有利于元素充分散列，減少 Hash 碰撞
在給HashMap添加元素的putVal函數(shù)中，有這樣一段代碼：
- // n為容量，hash為該元素的hash值
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
它會(huì)在添加元素時(shí)，通過i = (n - 1) & hash計(jì)算該元素在HashMap中的位置。
當(dāng) HashMap 的容量為 2 的 n 次冪時(shí)，他的二進(jìn)制值是100000……（n個(gè)0），所以n-1的值就是011111……（n個(gè)1），這樣的話(n - 1) & hash的值才能夠充分散列。
舉個(gè)例子，假設(shè)容量為16，現(xiàn)在有哈希值為1111，1110，1011，1001四種將被添加，它們與n-1(15的二進(jìn)制=01111)的哈希值分別為1111、1110、1110、1011，都不相同。
而假設(shè)容量不為2的n次冪，假設(shè)為10，那么它與上述四個(gè)哈希值進(jìn)行與運(yùn)算的結(jié)果分別是：0101、0100、0001、0001。
可以看到后兩個(gè)值發(fā)生了碰撞，從中可以看出，非2的n次冪會(huì)加大哈希碰撞的概率。所以 HashMap 的容量設(shè)置為2的n次冪有利于元素的充分散列。
參考：HashMap初始容量為什么是2的n次冪及擴(kuò)容為什么是2倍的形式
HashMap 是如何導(dǎo)致死循環(huán)的
HashMap會(huì)導(dǎo)致死循環(huán)是在jdk1.7中，由于擴(kuò)容時(shí)的操作是使用頭插法，在多線程的環(huán)境下可能產(chǎn)生循環(huán)鏈表，由此導(dǎo)致了死循環(huán)。在jdk1.8中改為使用尾插法，避免了該死循環(huán)的情況。
