java進階(29)–HashMap集合
一、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則不行
