java進階(29)--HashMap集合
2021-01-14 00:30:23 軟體

一、HashMap簡介

1、HashMap底層是雜湊表結構,類似字典,初始化如下:

 

2、雜湊表結構:

是一個陣列+單向連結串列的結構體

陣列:查詢效率較高,隨機增刪效率很低

單向連結串列:在隨機增刪方面效率較高,查詢方面效率很低

雜湊表將以上兩種資料結構融合在一起,充分發揮它們各自的優點。

 

3、HashMap集合底層是陣列,Node<k,v>[]tables;

hash為雜湊值,是HashCode方法執行的結果,通過雜湊演演算法可以轉換為陣列的下標;

key,value為Map的key與value,next為下一個記憶體地址

 

4、map.put(k,v)的實現原理

k,v封裝到Node物件內,底層呼叫hashCode()方法得出hash值,通過雜湊演演算法/雜湊函數,將hash值轉換成陣列下標。

如果下標對應的位置上面沒有元素,Node新增到位置上;

如果下標對應的位置上有連結串列,拿k與連結串列每個節點k進行equals,如所有equals方法都false,新節點將新增到尾部;

如果有一個euals返回true,那麼這個節點的value值將會覆蓋

 

5、map.get(k)的實現原理

呼叫k的hashCode()方法得出雜湊值,通過雜湊演演算法轉換成陣列下標,通過陣列下標快速定位到某個位置,位置上什麼都沒有話,返回null;

如果這個位置上有單向連結串列,那麼會拿著引數k和單向連結串列上每個節點的k進行equals,如果所有的equals返回false,囊二get方法返回null。

主要其中某一個節點的k和引數k equals返回true,那麼此時這個節點的value就是我們要找的value,既為get方法的最終返回value

 

6、HashMap的key部分元素需要重寫equals方法hashCode方法。也就是hashSet集合中的元素需要重寫equals方法hashCode方法。

 

7、HashMap使用不當時會發生效能問題:

假設所有的hashCode方法返回值都相等,那麼底層會變成單向連結串列,即雜湊分佈不均勻。

什麼是雜湊分佈均勻:100個元素,10個單向連結串列,每個單向連結串列中包含10個節點。

假設所有的hashCode方法返回均不一樣,那麼底層會變成陣列,即雜湊分佈不均勻。

雜湊分佈均勻需要重寫hashCode方法有一定的技巧

 

8、HashMap集合底層陣列達到75%容量時,陣列是開始擴容,預設陣列容量為16,初始化容量必須是2的倍數,為達到雜湊分佈均勻,且可以提高hashMap集合存取效率。

 

9、HashMap元素存取什麼時候不需要執行equals方法:k.hashCode方法返回的雜湊值的陣列下標位置為null的時候,equals不再需要執行。

 

10、HashMap JDK8改進:

如果雜湊表的單向連結串列中元素>8,單向連結串列會變成紅黑樹,當紅黑樹上節點數量<6,會重新把紅黑數變成單向連結串列

 

11、雜湊表資料結構注意事項:

如果o1與o2的hash值相同,一定在同一個單向連結串列上,

如果o1與o2的hash值不同,但由於雜湊演演算法執行結束後轉換的陣列下標可能相同,此時會發生「雜湊碰撞」

 

二、範例說明:

1、測試HashMap元素特點:key為integer,它的hashCode與equals均已經被重寫

 

2、遍歷Map集合-元素將被無須取出

 

3、重寫quals與hashCode方法

未重寫hashCode與equals

 重寫hashCode與equals後

 4、HashMap的key與value可以為空嗎,

HashMap可以,Hashtable則不行