首先我們來談談HashMap，從字面上來看，HashMap的名字中帶有hash，我們就可以聯想到HashMap的存盤方式可能與hash有關，
下面我們來談談HashMap的存盤機制：
HashMap是以鍵值對的形式存盤資料的，其底層存盤是以陣列+鏈表的方式實作的（jdk1.8之后又引入了紅黑樹），
首先我們可想象一個陣列，這個陣列的默認大小是16（因為在創建一個HashMap物件時，如果不指定其長度，那么底層將會默認創建一個有16個大小的陣列），
HashMap在存入一個資料時，會先去呼叫物件的hashCode方法計算出該物件應該放在之前創建的陣列的哪個位置（即陣列的索引值），若該位置為空，則直接將該物件存進去，若該位置有值，在去呼叫物件的equals方法比較兩個key的值是否相等，如果相等則覆寫掉value的值，如果不相等，則在陣列該索引處將舊值后移并將新值插入，形成一個鏈表（這是jdk1.7及以前的方式），
上述方式存在一個問題，即如果多次添加資料的位置相同的話，那么這個鏈表就會一直增長，而且每次在鏈表中添加資料時都要移動鏈表中的資料，這樣情況稱之為碰撞，我們需要盡量減少這種碰撞的發生，發生碰撞，可能會增長鏈表，鏈表增長越長，碰撞的所需的時間就越多，可想是多么影響效率，
所以HashMap就引入了加載因子避免碰撞，默認為0.75，即當元素達到現有hash表的75%時擴容，一旦擴容將會重新排序hash表，減少碰撞的概率，
jdk1.8之后：
上述情況依舊不能避免形成一長串鏈表的可能，所以在jdk1.8之后引入了紅黑樹，開始的存盤方式與之前相同，通過key確定存放位置，通過value判斷是否覆寫或添加鏈表，超過閾值0.75自動擴容，但是改變的是如果鏈表的長度大于8，那么就會將鏈表轉化為紅黑樹，但是在轉變成樹之前還會有一個判斷，只有鍵值對的數量大于64才會發生轉換，這是為了避免在哈希表創建初期，多個鍵值對恰好被放入了同一個鏈表中而導致的不必要的轉化，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/154283.html
標籤：Java
下一篇：Redisson分布式鎖