Java hashmap通過哈希表實現鍵值對的高效存儲與檢索，其底層結構為數組加鏈表（或紅黑樹），1. 哈希函數將鍵轉換為數組索引以定位存儲位置；2. 使用鏈地址法解決哈希沖突，jdk 1.8后引入紅黑樹優化長鏈表查找效率；3. put操作包括計算哈希、定位桶、處理沖突及擴容判斷；4. get操作通過哈希定位并遍歷鏈表或樹來獲取值；5. 負載因子控制擴容時機以平衡時間與空間；6. 非線程安全，多線程下推薦使用concurrenthashmap；7. 容量為2的冪以優化索引計算；8. 根據需求選擇hashmap、treemap或linkedhashmap；9. 性能優化包括合理設置容量、使用不可變鍵及重寫hashcode和equals方法。
Java HashMap的核心在于它如何存儲和檢索鍵值對，簡單來說，它使用哈希表來實現快速查找。理解它的工作原理，就像理解一個高效的圖書館，能讓你在海量數據中迅速找到所需信息。
HashMap的存儲結構和哈希機制是其高效的關鍵。
HashMap的內部結構：數組 + 鏈表（或紅黑樹）
HashMap的底層是一個數組，數組中的每個元素是一個鏈表（在JDK 1.8之后，當鏈表長度超過一定閾值時，會轉換為紅黑樹）。這個數組被稱為“桶”（bucket），每個桶存儲具有相同哈希值的鍵值對。
立即學習“Java免費學習筆記（深入）”；
想象一下，你有一個巨大的書架（數組），每個書架上可以放很多書（鏈表或紅黑樹）。哈希函數就像圖書館的索引系統，它告訴你應該把書放在哪個書架上。
哈希函數的作用：將鍵轉換為數組索引
哈希函數負責將鍵（key）轉換為數組的索引。理想情況下，哈希函數應該將不同的鍵均勻地分布到不同的桶中，以避免沖突。Java HashMap使用鍵的hashCode()方法來計算哈希值，然后通過一些位運算來確定數組索引。
如果兩個不同的鍵具有相同的哈希值（即發生沖突），它們將被存儲在同一個桶的鏈表（或紅黑樹）中。
如何處理哈希沖突？鏈地址法
當不同的鍵映射到同一個數組索引時，就會發生哈希沖突。HashMap使用鏈地址法來解決沖突。鏈地址法意味著將所有哈希到同一個索引的鍵值對存儲在一個鏈表中。
在JDK 1.8中，當鏈表長度超過8時，鏈表會轉換為紅黑樹，以提高查找效率。紅黑樹是一種自平衡的二叉搜索樹，可以在O(log n)的時間復雜度內進行查找。
HashMap的put()操作：存儲鍵值對
put(key, value)操作的步驟如下：
- 計算鍵的哈希值。
- 根據哈希值找到對應的數組索引（桶）。
- 如果桶是空的，直接將鍵值對放入桶中。
- 如果桶中已經存在鍵值對（發生沖突），則遍歷鏈表（或紅黑樹）：
- 如果找到與鍵相同的節點，則更新該節點的值。
- 如果未找到與鍵相同的節點，則將新的鍵值對添加到鏈表的末尾（或紅黑樹中）。
- 如果添加新元素后，鏈表長度超過閾值（8），則將鏈表轉換為紅黑樹。
- 如果HashMap中的元素數量超過了負載因子（load factor）乘以容量（capacity），則進行擴容。
HashMap的get()操作：檢索鍵值對
get(key)操作的步驟如下：
- 計算鍵的哈希值。
- 根據哈希值找到對應的數組索引（桶）。
- 如果桶是空的，則返回NULL。
- 如果桶中存在鍵值對，則遍歷鏈表（或紅黑樹）：
- 如果找到與鍵相同的節點，則返回該節點的值。
- 如果未找到與鍵相同的節點，則返回null。
負載因子和擴容：平衡時間和空間
負載因子（load factor）是HashMap中一個重要的參數，它表示HashMap在自動擴容之前可以達到的飽和度。默認的負載因子是0.75。
當HashMap中的元素數量超過了負載因子乘以容量時，HashMap會進行擴容。擴容意味著創建一個新的更大的數組，并將所有現有的鍵值對重新哈希到新的數組中。
擴容是一個耗時的操作，因為它需要重新計算所有鍵的哈希值，并將它們重新分配到新的桶中。但是，擴容可以避免HashMap中的鏈表變得過長，從而保證查找效率。
HashMap的線程安全性問題
HashMap不是線程安全的。如果在多線程環境下使用HashMap，可能會發生數據不一致的問題。例如，當多個線程同時put元素時，可能會導致覆蓋或丟失數據。
如果需要在多線程環境下使用HashMap，可以使用Collections.synchronizedMap(new HashMap(…))來創建一個線程安全的HashMap，或者使用ConcurrentHashMap。ConcurrentHashMap使用了更細粒度的鎖，可以提供更高的并發性能。
為什么HashMap的容量必須是2的冪？
HashMap的容量總是2的冪次方，這是為了優化哈希值的計算和數組索引的定位。當容量是2的冪次方時，可以使用位運算來代替取模運算，從而提高計算速度。
例如，假設容量是16（2的4次方），那么可以使用hash & (capacity – 1)來計算數組索引。這種位運算比取模運算更快。
HashMap vs. TreeMap vs. LinkedHashMap：選擇哪個？
- HashMap: 提供最快的查找速度，但不保證元素的順序。
- TreeMap: 基于紅黑樹實現，可以保證元素的順序（按照鍵的自然順序或自定義順序排序）。
- LinkedHashMap: 維護元素的插入順序，或者訪問順序（最近訪問的元素排在前面）。
選擇哪個取決于你的具體需求。如果你需要最快的查找速度，并且不關心元素的順序，那么HashMap是最好的選擇。如果你需要保證元素的順序，那么TreeMap或LinkedHashMap可能更適合。
如何優化HashMap的性能？
- 選擇合適的初始容量和負載因子： 如果你知道HashMap將要存儲的元素數量，可以設置合適的初始容量，以避免頻繁的擴容。
- 使用不可變對象作為鍵： 不可變對象的哈希值不會改變，可以避免在HashMap中出現意外的行為。
- 避免使用復雜的對象作為鍵： 復雜的對象的hashCode()方法可能比較耗時，會影響HashMap的性能。
- 重寫hashCode()和equals()方法： 如果你自定義了對象作為鍵，需要確保正確地重寫hashCode()和equals()方法，以保證HashMap的正確性。
HashMap是Java集合框架中一個非常重要的類，理解它的工作原理對于編寫高效的Java代碼至關重要。掌握了HashMap的內部結構、哈希機制、沖突處理、擴容機制等知識，你就可以更好地利用HashMap來解決實際問題。
