HashMap源碼: 載入因數:loadFactory -- 預設 0.75f 初始容量大小: capacity 預設 16, 最大限制 1<<30 擴容: 當數組元素的數量 > 初始容量大小 * 載入因數,就會擴容. 會調用rehash方法將數組長度擴容到之前的兩倍.擴容的時候,會生成一個新的數組 ...
HashMap源碼:
- 載入因數:loadFactory -- 預設 0.75f
- 初始容量大小: capacity 預設 16, 最大限制 1<<30
- 擴容: 當數組元素的數量 > 初始容量大小 * 載入因數,就會擴容. 會調用rehash方法將數組長度擴容到之前的兩倍.擴容的時候,會生成一個新的數組,原來的所有數據需要重新計算哈希碼值重新分配到新的數組，所以擴容的操作非常消耗性能.
Jdk1.7和jdk1.8區別
- jdk1.7之前 採用的是 數組 + 鏈表的方式, 採用的是頭插法,擴容時會改變鏈表中元素原本的順序,以至於在併發場景下導致鏈表成環的問題
- jdk1.8之後 採用的是 數組 + 鏈表/紅黑樹的方式 當某個位置出現哈希衝突時,會將元素放到該位置的鏈表後面,當鏈表長度超過8時, 會嘗試採用紅黑樹來存儲, 若數組長度 若大於 64,鏈表長度 大於8會 將鏈表的所有節點都轉換成紅黑樹,若數組長度 小於64,會擴容
Map get() 和 put()原理
- 1.8中put: put中調用putVal()方法
- 1)首先判斷map中是否有數據,沒有就執行resize方法(擴容也是通過這個方法)
- 2)如果要插入的鍵值對要存放的這個位置剛好沒有元素,那麼就把他封裝成Node對象,放在這個位置上
- 3)如果這個元素的key和與要插入的一樣,就替換一下
- 4)如果當前節點是TreeNode類型的數據,執行putTreeVal方法
-
get:
-
1)調用k的hashCode()計算出哈希值,並通過哈希演算法轉換成數組的下標.
-
2)通過上一步哈希演算法轉換成數組的下標後,通過數組快速定位到某個位置.如果這個位置上什麼都沒有,返回null如果有,則拿著K和單向鏈表上的每一個節點K進行equals,如果所有equals都返回false,則返回null若true,則返回該value.
-
resize方法: 兩個職責,創建初始存儲表格,或者在容量不滿足需求的時候,進行擴容.
具體鍵值對在哈希表中的位置取決於該位運算: i = (n-1) & hash
-
熱點問題:
為什麼HashMap要樹化?
本質上是因為安全問題.因為,在元素的存放過程中,如果一個對象哈希衝突,都被放到一個桶里,則會形成一個鏈表,而鏈表的查詢是線性的會嚴重影響存取的性能.而現實情況中,構造哈希衝突的數據並不是非常複雜的事情,惡意代碼就會利用這些數據與伺服器大量交互,導致伺服器端cpu大量占用,這就構成了哈希碰撞拒絕服務攻擊.
ps:用哈希碰撞發起拒絕服務攻擊(DOS，Denial-Of-Service attack),常見的場景是攻擊者可以事先構造大量相同哈希值的數據，然後以JSON數據的形式發送給伺服器，伺服器端在將其構建成為Java對象過程中，通常以Hashtable或HashMap等形式存儲，哈希碰撞將導致哈希表發生嚴重退化，演算法複雜度可能上升一個數據級，進而耗費大量CPU資源。
HashMap,HashTable,TreeMap,LinkedHashMap的區別
-
HashMap繼承自AbstractMap類,而HashTable繼承自Dictionary類,不過它們都同時實現了map,cloneable,serializable介面.存儲的內容是基於 key-value的鍵值對映射,key不能重覆,一個key只能映射一個value.HashSet的底層就是基於HashMap實現的.
-
HashTable的key,value都不能為null
HashMap key 和 value 都可以為null,但只能有一個key為null,可以有多個null的value
TreeMap 鍵值都不能為null -
一般情況下,選用HashMap,因為HashMap的鍵值對在取出時是隨機的,依據key的hashCode和鍵的equals方法來存取數據,具有很快的訪問速度,所以在map中插入,刪除及索引元素時效率較高.而TreeMap的鍵值對在取出時是排過序的,所以效率低一點.
-
TreeMap是基於紅黑樹的一種提供順序訪問的map,與HashMap不同的是它的get,put,remove之類的操作都是o(log(n))的時間複雜度,具體順序可以由指定的Comparator來決定,或者根據鍵的自然順序來判斷.
-
LinkedHashMap適合需要輸出的順序和輸入的順序相同的情況
-
HashMap是線程不安全的,HashTable是線程安全的.所以HashTable的效率比不上HashMap
前者預設初始化數組大小為16,後者為11,擴容時,擴大兩倍,後者擴大兩倍+1
-
HashMap需要重新計算hash值,而hashTable直接使用對象的hashCode
HashMap在1.7和1.8之間的變化
- 1.7中採用數組+鏈表,1.8採用數組+鏈表/紅黑樹
- 1.7擴容時需要重新計算哈希值和索引位置,1.8並不重新計算哈希值,巧妙地採用和擴容後容量進行&操作來計算新的索引位置.
- 1.7採用頭插法: 擴容時會改變鏈表中元素的原本順序,以至於在併發場景下導致鏈表成環的問
- 1.8採用尾插法: 擴容時會保持鏈表原本的順序,避免了鏈表成環的問題.
當兩個對象的hashCode相同時會發生什麼?
- hashCode相同,equals不一定為true,所以兩個對象所在數組的下標相同,"碰撞"就此發生.會存儲在數組該位置的鏈表(紅黑樹)中.
你知道hash的實現嗎?為什麼要這樣實現?
-
1.8中,通過hashCode()的高16位異或低16位實現的
(h = k.hashCode()) ^ (h >>> 16)主要是從速度,功效和質量來考慮的,減少系統的開銷,也不會因為高位沒有參與下標的計算,從而引起碰撞
-
用異或運算符,保證了對象的hashCode的32位值只要有一位發生改變,整個hash()返回值就會改變,儘可能的減少碰撞
拉鏈法導致的鏈表過深問題為什麼不用二叉樹代替,而選擇紅黑樹?為什麼不一直使用紅黑樹?
- 紅黑樹是為瞭解決二叉查找樹的缺陷,二叉查找樹在特殊情況下會變成一條線性結構(這就跟原來使用鏈表結構一樣了,同樣會造成很深的問題),遍歷查找會非常慢.
- 紅黑樹在插入新數據後會通過左旋,右旋或者變色操作來保持平衡,引入紅黑樹是為了查找數據快,解決鏈表查詢深度的問題,紅黑樹屬於平衡二叉樹,儘管為了保持平衡會付出代價,但該代價損耗的資源相比遍歷線性鏈表來說要少.所以,當長度大於8的時候,會使用紅黑樹.而為什麼是8,是因為符合泊松分佈,為8時資源損耗相對來說較少.
HashMap和CuncurrentHashMap的區別?
- ConcurrentHashMap類是java併發包java.util.concurrent中提供的一個線程安全且高效的HashMap實現.
- 1.7中ConcurrentHashMap採用分段鎖(ReentrantLock + segment +hashEntry),相當於把一個HashMap分成多個段,每段分配一把鎖,這樣支持多線程訪問.鎖粒度:基於segment,包含多個HashEntry
- 1.8中採用CAS + synchronized + Node + 紅黑樹.鎖粒度: Node.鎖粒度降低了
- HashTable則使用synchronized關鍵字加鎖
- 區別: ConcurrentHashMap鍵值對都不允許為null
ConcurrentHashMap簡單介紹一下?
-
java.util.concurrent.ConcurrentHashMap屬於JUC包下的一個集合類,可以實現線程安全.
-
1.8之前:
- 由多個Segment組合而成,Segment本身就相當於一個HashMap對象.同HashMap一樣,Segment包含一個HashEntry數組,數組中的每一個HashEntry既是一個鍵值對,也是一個鏈表的頭節點.
-
Put: 首先,會嘗試獲取鎖,若獲取失敗,則利用scanAndLockForPut()自旋獲取鎖.如果重試的次數達到了MAX_SCAN_RETRIES則改為阻塞鎖獲取,保證能獲取成功.接著,遍歷該HashEntry,如果不為空則判斷傳入的key和當前遍歷的key是否相等,相等則覆蓋舊的value.為空,則需要新建一個HashEntry並加入到Segment中,同時會先判斷是否需要擴容.
-
Get: key通過hash之後定位到具體的segment,再通過一次hash定位到具體元素上.
由於HashEntry中的value屬性是用volatile關鍵字修飾的,保證了記憶體可見性,所以每次獲取時都是最新值. 整個過程非常搞笑,不需要加鎖.
- 由多個Segment組合而成,Segment本身就相當於一個HashMap對象.同HashMap一樣,Segment包含一個HashEntry數組,數組中的每一個HashEntry既是一個鍵值對,也是一個鏈表的頭節點.
- 1.8之後:
- 數組+鏈表 改為 數組+鏈表/紅黑樹,HashEntry改為Node
ConcurrentHashMap的key,value是否可以為null,為什麼?
-
都不可以為null,為null時會拋出空指針異常.
ConcurrentHashMap是一個用於多線程併發場景下的併發容器(map),在多線程環境下執行增刪改查方法要保證線程安全性.
-
不能為null,因為會產生二義性問題: 當我們用get方法去獲取一個value為null的時候,可能會沒有這個key,也可能會有這個key,只不過value為null.
-
HashMap如何解決二義性問題
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}- 如果存在key為null的元素(key = null對應的hash值為0),getNode獲取到值不為null
- 如果不存在key為null的元素,此時hash值=0對應的下標元素為null,即getNode獲取到的值為null
-
ConcurrentHashMap為什麼不能解決二義性問題
- 因為ConcurrentHashMap是一個用在多線程併發的map容器,不能put null 是因為無法分辨是key沒找到null,還是有key的值為null.這在多線程里沒法保證會不會有其他線程修改為null鍵和null值的情況,所以不讓put null.
