HashMap 如何解決 hash 沖突

• HashMap 底層采用數組的結構來存儲資料元素，數組的預設長度是 16，通過 put 方法添加資料的時候，HashMap 根據 key 的 hash 值進行取模運算，最終儲存到數組的指定位置
• 這種設計會存在 hash 沖突問題，也就是兩個不同 hash 值的 key，最終取模後會落到同一個數組下标
• HashMap 引傳入連結式尋址法來解決 hash 沖突問題， 對于存在沖突的 key，HashMap 把這些 key 組成一個單向連結清單
• 采用尾插法把這個 key 儲存到連結清單的尾部

  

• 為了避免連結清單過長的問題，當連結清單長度大于 8 并且數組長度大于等于 64 的時候，HashMap 會把連結清單轉化為紅黑樹，減少連結清單資料查詢的時間複雜度問題，提升查詢性能

  

• 解決 hash 沖突 還有其他一些方式：
  • 再 hash 法，某個 hash 函數産生了沖突，再用另外一個 hash 進行計算，比如布隆過濾器就采用了這種方法
  • 開放尋址法，直接從沖突的數組位置往下尋找一個空的數組下标進行資料存儲，這個在 ThreadLocal 裡面有使用到
  • 建立公共溢出區，把存在沖突的 key 統一放在一個公共溢出區裡面