-
hashmap的hashcode計算
1.7 9次擾動處理=4次位運算+5次異或
1.8 2次擾動處理=1次位運算+1次異或
-
擴(kuò)容時的hashcode有什么變化?
1.7 hashcode--->>擾動處理--->>重新和(新容量-1)相&
1.8直接利用了這個特性,元素的位置等于原位置或者原位置+舊容量,這種方法只需要判斷新參與&運算的位計算結(jié)果是0還是1就可以解決,
-
hashmap底層結(jié)構(gòu)
1.7數(shù)組+單鏈表
1.8數(shù)組+單鏈表+紅黑樹
-
為什么數(shù)組大小一定是2的冪次?
- HashMap的長度為2的冪次方的原因是為了減少Hash碰撞，盡量使Hash算法的結(jié)果均勻分布,計算公式是hashcode%(n-1),當(dāng)n是2的冪次時,n-1的二進(jìn)制所有位均為1,這樣計算出來的位置只和傳入數(shù)據(jù)的hashcode有關(guān)聯(lián),如果非2的冪次,比如10,那么n-1等于9,10001,必然會存在概率不平均的問題
-
如果hashmap構(gòu)造參數(shù)傳入17,他的容量是怎么計算成32的?
先將值-1(避免傳進(jìn)來的值就是2的冪次,比如如果是4,會算出來8),然后不斷移位并與自身或
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;</pre>return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
最后返回計算出來的n+1
-
為什么引入紅黑樹?
- 在數(shù)據(jù)為8的時候折疊成紅黑樹,時間復(fù)雜度為(logn)級別,顯然優(yōu)于鏈表的O(n)
-
為什么用rb,不用bst,avl?
首先bst極端條件會鏈化
avl解決了鏈化的問題,但是頻繁的插入刪除會讓他不斷地左旋右旋,性能大打折扣
紅黑樹不是嚴(yán)格的avl,他的查找性能低于avl,但是查找插入會優(yōu)于avl
-
那談?wù)劶t黑樹吧?
-
既然紅黑樹那么好,為什么不直接使用紅黑樹,還要用鏈表呢?
- "因為樹節(jié)點的大小是鏈表節(jié)點大小的兩倍，所以只有在容器中包含足夠的節(jié)點保證使用才用它”，顯然盡管轉(zhuǎn)為樹使得查找的速度更快，但是在節(jié)點數(shù)比較小的時候，此時對于紅黑樹來說內(nèi)存上的劣勢會高于查找的操作
-
為什么HashMap樹化的臨界值為什么是8，鏈化的鏈接值為6,為什么不是9,10?那為什么不取7,不取6呢?
根據(jù)泊松分布,桶的長度超過8的概率為億分之六,小于千萬分之一,極低,再往后調(diào)整就沒多大意義了
7作為中間的過度點,這個時候鏈表和紅黑樹綜合比較差別不大,避免頻繁的鏈表和紅黑樹
-
hashmap元素插入方式
1.7頭插法
1.8尾插法
-
為什么改為尾插?
- 尾插可以解決并發(fā)擴(kuò)容的時候出現(xiàn)逆序和環(huán)路的問題,但是之前的頭插也很方便,比如:頭插就不用像尾插一樣,需要一路遍歷鏈表到最后找到最后一個節(jié)點再插入,并且剛剛插入的數(shù)據(jù),有很大的可能又被作為頭部快速的拿出來.
-
hashmap擴(kuò)容方式
1.7 擴(kuò)容后插入元素
1.8 擴(kuò)容前插入元素
-
為什么1.7擴(kuò)容前插入,1.8擴(kuò)容后插入?不明白
-
為什么hashmap的key和value都允許為null?
hashmap key為null的hashcode為0,全部放入數(shù)組0序號中,只能有一個key為null
hashmap是非線程安全的,不適用于并發(fā),所以他有containsKey()這個方法,來判斷key是否存在,如果是線程安全的類比如hashtable他就不支持key為null,為了保證并發(fā)安全就沒有containsKey()這個方法,只能通過getKey()來判斷key是否為null,但是如果允許key為null,那當(dāng)getKey()返回null,我無法判斷是key的值為null,還是key不存在所以返回null
-
為什么hashmap是線程不安全的?
沒有同步鎖保護(hù)
1.7中頭插法的存在會出現(xiàn)環(huán)形鏈表,在遍歷數(shù)據(jù)的時候形成死循環(huán)
hashmap迭代器的fail-fast策略,并發(fā)修改時,出現(xiàn)modcount和expectedModCount出現(xiàn)不一致拋出
ConcurrentHashModificationException異常
-
那如果多線程操作hashmap會遇到什么問題?
1.7版本由于是頭插法,不斷put(),出現(xiàn)環(huán)形鏈表,導(dǎo)致get()陷入死循環(huán)
put()如果操作同一個數(shù)組下標(biāo)可能出現(xiàn)數(shù)據(jù)丟失和覆蓋
-
為什么hashmap不保證有序?
- 插入順序和存儲順序不同,插入順序是用戶操作的順序,存儲順序是根據(jù)hash算法計算的數(shù)組下標(biāo)
-
為什么hashmap存儲位置隨時間變化?
- 其實是隨著擴(kuò)容操作而變化,擴(kuò)容會使存儲位置重新計算
-
為什么hashmap中String,Integer這種包裝類更適合作為key?
因為這種包裝類,保證了hash值的不可變性--->>包裝類被final修飾
有效減少了hash碰撞--->>內(nèi)部重寫了hashcode和equals不易出現(xiàn)hash的計算錯誤
-
hashmap的key若為Object,則需要實現(xiàn)哪些方法?
- hashcode()和equals()
后續(xù)問題:
hashmap既然線程不安全的,那你怎么解決這個問題?(HashTable,Collections.synchronizedMap(),ConcurrentHashMap)
-
HashMap內(nèi)部既然是無序的,那有沒有有序的map?
(LinkedHashMap,TreeMap)
