在Java 8 之前，HashMap和其他基於map的類都是通過鏈地址法解決衝突，它們使用單向鏈表來存儲相同索引值的元素。在最壞的情況下，這種方式會將HashMap的get方法的性能從O(1)降低到O(n)。為瞭解決在頻繁衝突時hashmap性能降低的問題，Java 8中使用平衡樹來替代鏈表存儲衝突 ...
在Java 8 之前，HashMap和其他基於map的類都是通過鏈地址法解決衝突，它們使用單向鏈表來存儲相同索引值的元素。在最壞的情況下，這種方式會將HashMap的get方法的性能從O(1)降低到O(n)。為瞭解決在頻繁衝突時hashmap性能降低的問題，Java 8中使用平衡樹來替代鏈表存儲衝突的元素。這意味著我們可以將最壞情況下的性能從O(n)提高到O(logn)。
在Java 8中使用常量TREEIFY_THRESHOLD來控制是否切換到平衡樹來存儲。目前，這個常量值是8，這意味著當有超過8個元素的索引一樣時，HashMap會使用樹來存儲它們。
這一改變是為了繼續優化常用類。大家可能還記得在Java 7中為了優化常用類對ArrayList和HashMap採用了延遲載入的機制，在有元素加入之前不會分配記憶體，這會減少空的鏈表和HashMap占用的記憶體。
這一動態的特性使得HashMap一開始使用鏈表，併在衝突的元素數量超過指定值時用平衡二叉樹替換鏈表。不過這一特性在所有基於hash table的類中並沒有，例如Hashtable和WeakHashMap。
目前，只有ConcurrentHashMap,LinkedHashMap和HashMap會在頻繁衝突的情況下使用平衡樹。
什麼時候會產生衝突
HashMap中調用hashCode()方法來計算hashCode。
由於在Java中兩個不同的對象可能有一樣的hashCode,所以不同的鍵可能有一樣hashCode，從而導致衝突的產生。
總結
- HashMap在處理衝突時使用鏈表存儲相同索引的元素。
- 從Java 8開始，HashMap，ConcurrentHashMap和LinkedHashMap在處理頻繁衝突時將使用平衡樹來代替鏈表，當同一hash桶中的元素數量超過特定的值便會由鏈表切換到平衡樹，這會將get()方法的性能從O(n)提高到O(logn)。
- 當從鏈表切換到平衡樹時，HashMap迭代的順序將會改變。不過這並不會造成什麼問題，因為HashMap並沒有對迭代的順序提供任何保證。
- 從Java 1中就存在的Hashtable類為了保證迭代順序不變，即便在頻繁衝突的情況下也不會使用平衡樹。這一決定是為了不破壞某些較老的需要依賴於Hashtable迭代順序的Java應用。
- 除了Hashtable之外，WeakHashMap和IdentityHashMap也不會在頻繁衝突的情況下使用平衡樹。
- 使用HashMap之所以會產生衝突是因為使用了鍵對象的hashCode()方法，而equals()和hashCode()方法不保證不同對象的hashCode是不同的。需要記住的是，相同對象的hashCode一定是相同的，但相同的hashCode不一定是相同的對象。
- 在HashTable和HashMap中，衝突的產生是由於不同對象的hashCode()方法返回了一樣的值。
以上就是Java中HashMap如何處理衝突。這種方法被稱為鏈地址法，因為使用鏈表存儲同一桶內的元素。通常情況HashMap，HashSet，LinkedHashSet，LinkedHashMap，ConcurrentHashMap，HashTable，IdentityHashMap和WeakHashMap均採用這種方法處理衝突。
從JDK 8開始，HashMap，LinkedHashMap和ConcurrentHashMap為了提升性能，在頻繁衝突的時候使用平衡樹來替代鏈表。因為HashSet內部使用了HashMap，LinkedHashSet內部使用了LinkedHashMap，所以他們的性能也會得到提升。
