為什麼要有HashMap數據結構
為了高效的執行數據插入和數據查找功能，在此之前就要提到鏈表和數組這兩種數據結構。
數組：查找輕鬆，但是插入和刪除複雜在最壞情況下時間複雜度為O(n)。
鏈表：插入刪除輕鬆，，但是查找麻煩，需要從頭結點逐個遍歷時間複雜度為O(n)
而hashmap實現了兩者的結合，查找輕鬆並且插入刪除也輕鬆的數據結構
HashMap的數據結構是什麼樣子的
java1.8之後數據結構為數組+鏈表+紅黑樹
HashMap的特點
屬於Map下的集合，用KV鍵值對存儲元素，元素是無序的，key不允許重複，value允許重複，允許存儲null，線程不安全
HashMap如何查找數據
map.get("張三")會將“張三”字符通過hash算法和位運算得到一個值，這個值就是數組的下標，定位到
table[index]後，分情況處理：情況 A：桶為空
- 直接返回
null。情況 B：桶中只有一個節點
- 比較：
- 哈希值是否相等（先快速判斷）
- key 是否相等（
==或equals()）
- 匹配則返回 value，否則返回
null。情況 C：桶中是鏈表（長度 < 8）
- 從頭開始遍歷鏈表：
- 先比
hash（快速失敗）- 再比
key（引用相等或equals相等）
- 找到則返回 value，遍歷完未找到則返回
null。情況 D：桶中是紅黑樹（長度 ≥ 8 且 table.length ≥ 64）
- 調用樹的查找方法（
TreeNode.getTreeNode()）。- 利用紅黑樹的有序性（基於 hash 和 key 的 compareTo 或 hashCode）快速定位。
- 時間複雜度從 O(n) 降為 O(log n)。
HashMap位運算獲取Index細節
hash算法和位運算的細節舉個例子：
公式： hash值&（數組長度-1）
當hashmap數組長度為16，張三的hash過後的計算值為123
我們先展開兩個值為16位的2進制16-1 = 0000 0000 0000 0111
123 = 0000 0000 0111 101115和123的位運算的結果為0000 0000 0000 0011 = 3
則將張三放在數組index為3中
HashMap如何插入
map.put("張三")
- 計算
"張三"的 hash- 定位桶
- 如果桶空 → 插入
- 桶中已有節點 → 遍歷查找是否已存在相同 key
- 存在 → 更新 value
- 不存在 → 尾插到鏈表 or 插入紅黑樹
HashMap如何擴容
什麼時候觸發擴容
當size> capacity * loadFactor
size 為當前存儲鍵值對數量
capacity 為當前大小
loadFactor 為負載因子怎麼擴容的
1.創建一個當前大兩倍的數組
2.將原map中數據，計算高低位，低位的元素放在新數組的原位置，高位的元素放在新數組的原位置+原容量的位置中
HashMap中什麼時候會變成紅黑樹
1.鏈表長度 ≥ TREEIFY_THRESHOLD
TREEIFY_THRESHOLD的默認值是 8。- 當某個桶中的鏈表節點數量達到 8 時，並不立即轉為紅黑樹，還需滿足第二個條件。
2. 數組長度 ≥ MIN_TREEIFY_CAPACITY
MIN_TREEIFY_CAPACITY的默認值是 64。- 這是為了避免在哈希表容量較小時，因為頻繁擴容而導致不必要的樹化操作。
- 如果數組長度小於 64，即使鏈表長度達到 8，
HashMap也會優先選擇 擴容（resize） 而不是樹化。