作為Java開發，知道HashMap底層存儲原理總不會害你
概念
- HasnMap是基于map接口實現，元素以鍵值對的方式存儲，并且鍵和值都可以使用null，因為 key不允許重復，因此只能有一個鍵為null
- HaasnMap是 無序不重復的，而且HashMap是線程不安全 的
- JDK7HashMap的數據結構為：數組+鏈表
- JDK8HashMap的數據結構為：數組 + 鏈表 + 紅黑樹
存儲的優點
- 數組的特點：查詢效率高，插入和刪除效率低
- 鏈表的特點：查詢效率 低，插入和刪除效率高
- 在HasnMap底層使用數組加 (鏈表或紅黑樹) 的結構完美的解決了數組和鏈表的問題，使的查詢和插入，刪除的效率都 很高
- HashMap的散列表是懶加載機制，在第一次put的時候才會創建
HashMap存儲元素的過程
首先將k、v封裝到Node對象當中(節點)
調用k的hasnCode()方法取出hash值;通過hashcode值和數組長度取模得到元素存儲的下標
此時分為兩種情況
- 下標位置上沒有元素，直接把元素方進入
- 該所以已有元素，判斷該位置的元素和當前元素是否相等，使用equals來比較(默認是比較兩個對象的地址)。如果兩只相等則直接覆蓋，如果不等則(Hash碰撞)在原元素下面使用鏈表的結構存儲該元素(如果已存在鏈表，則插在鏈表尾部)，每個元素節點都有一個next屬性指向下一個節點，這就由數組結構變成了數組+鏈表;因為鏈表中元素太多的時候回影響查找效率，所以當鏈表的元素個數達到 8 的時候使用鏈表存儲就轉變成了使用紅黑樹存儲(當紅黑樹上的節點數量小于 6 個，會重新把紅黑樹變成單向鏈表數據結構)，原因就是紅黑樹是平衡二叉樹，在查找性能方面比聊表要高
HashMap取值的實現
- 先調用k的hashCode()方法得出哈希值，并通過hash算法轉換成數組的下標
- 通過hash值轉換成數組下標后，通過數組定位到下標位置，如果改位置上什么都沒有，范圍null;如果該位置上有單向鏈表，那么就拿參數K和單向鏈表上的每一個節點的K進行equals比較，如果所有equals都返回false，則返回null，如果有一個節點的K和參數K通過equals返回true，那么此時該節點的value就是要獲取的value值
擴容
- HashMap中有兩個重要參數，初始容量大小和負載因子，在HashMap剛開始初始化的時候，使用默認的構造方法，會返回一個空的table，并且 thershold(擴容閾值)為 0 ，因此第一次擴容的時候默認值就會是 16 ，負載因子默認為 0.75 ，用數組容量乘以負載因子得到一個值，一旦數組中存儲的元素個數超過這個值就會調用rehash方法將數組容量增加到原來的兩倍，threshold也會變為原來的兩倍
- 在做擴容的時候會生成一個新的數組，原來的所有數據需要重新計算哈希碼值重新分配到新的數組，所以擴容的操作非常消耗性能。所以，如果知道要存入的數據量比較大的話，可以在創建的時候先指定一個比較大的數據容量
- 也可以引申到一個問題HashMap是先插入還是先擴容：HashMap初始化后首次插入數據時，先發生resize擴容再插入數據，之后每當插入的數據個數達到threshold時就會發生resize，此時是先插入數據再resize
HashMap中的擴容是在元素插入之前進行的擴容還是元素插入之后進行的擴容
在 JDK1.7中是在元素插入 前 進行的擴容，在JDK1.8 中是先加入元素 后 再判斷是否進行擴容
存儲元素超過閾值一定會進行擴容嗎
在 JDK1.7 中不一定，只有存儲元素超過閾值并且當前存儲位置不為null，才會進行擴容，在 JDK1.8 中會進行擴容
HashMap和HashTable區別
線程方面
- HashMap是非線程安全的，HashTable是線程安全的。 Hashtable的實現方法里面都添加了synchronized關鍵字來確保線程同步，因此相對而言HashMap性能會高一些，我們平時使用時若無特殊需求建議使用HashMap，在多線程環境下若使用HashMap需要使用Collections.synchronizedMap()方法來獲取一個線程安全的集合
- HashMap的key可以為null，HashTable的key不可為null
- HashMap是對Map接口的實現，HashTable實現了Map接口和Dictionary抽象類
- HashMap的初始容量為 16 ，Hashtable初始容量為 11 ，兩者的填充因子默認都是 0.75 ，HashMap擴容時是當前容量翻倍即：capacity * 2，- Hashtable擴容時是容量翻倍+1即：capacity * 2+1
HashMap中的hashcode怎么生成
調用對象key的hashCode方法，再對這個hashcode方法進行一些右移以及異或運算(使的hashCode的高位和低位都參與到運算中);通過右移和異或運算可以使hashMap的散列化更強，提高hashMap的get方法的效率
為什么使用HashCode
HashCode的存在主要是為了查找的快捷性, HashCode是用來在散列存儲結構中確定對象的存儲地址的 ( 用hashcode來代表對象在hash表中的位置 ) , hashCode存在的重要的原因之一就是在HashMap(HashSet其實就是HashMap)中使用(其實Object類的hashCode方法注釋已經說明了)，HashMap之所以速度 快 ，因為他使用的是 散列表 ，根據key的hashcode值生成數組下標(通過內存地址直接查找，不需要判斷，但是需要多出很多內存，相當于以空間換時間)
equals方法和hashcode的關系
歸納總結：
- 若重寫了equals(Object obj)方法，則有必要重寫hashCode()方法
- 若兩個對象equals(Object obj)返回true，則hashCode()有必要也返回相同的int數
- 若兩個對象equals(Object obj)返回false，則hashCode()不一定返回不同的int數
- 若兩個對象hashCode()返回相同int數，則equals(Object obj)不一定返回true
- 若兩個對象hashCode()返回不同int數，則equals(Object obj)一定返回false
- 同一對象在執行期間若已經存儲在集合中，則不能修改影響hashCode值的相關信息，否則會導致內存泄露問題
key為null怎么辦
key為null的時候，只會放在hashMap的0位置(即key的hashCode為0，對數組長度取余后的下標也是0)，不會有鏈表 在HashMap源碼中對put方法對null做了處理，key為null的判斷后進入putForNullKey(V value)這個方法，李里面for循環是在talbe[0]鏈表 中查找key為null的元素，如果找到，則將value重新賦值給這個元素的value，并返回原來的value。如果沒找到則將這個元素添加到talbe[0]鏈表的表頭
- /**
- * HashMap的put方法
- */
- public V put(K key, V value) {
- if (table == EMPTY_TABLE) {
- inflateTable(threshold);
- }
- // key為null調用putForNullKey(value)
- if (key == null) return putForNullKey(value);
- int hash = hash(key);
- int i = indexFor(hash, table.length);
- 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))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount++;
- addEntry(hash, key, value, i);
- return null;
- }
- /**
- * Offloaded version of put for null keys
- */
- private V putForNullKey(V value) {
- // for循環處理key為空的情況
- for (Entry<K,V> e = table[0]; e != null; e = e.next) {
- if (e.key == null) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount++;
- addEntry(0, null, value, 0);
- return null;
- }
【編輯推薦】
