HashMap源碼分析

HashMap在面試和工作中使用很多。

Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入(又叫做預映射， pre-image)，通過雜湊演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，是以不可能從散列值來唯一的确定輸入值。簡單的說就是一種将任意長度的消息壓縮到某一固定長度的消息摘要的函數。 HASH函數(計算機算法領域) 概述 HashMap是Map接口下一個線程不安全的，基于哈希表的實作類，它解決沖突的方法是連結清單法，是以它的資料結構是數組+連結清單 JDK1.8之後的資料結構則變為數組 + 連結清單 + 紅黑樹

HashMap有兩個參數影響其性能：初始容量和擴容因子。預設初始容量是16，加載因子是0.75。

initialCapacity 初始容量，通過tableSizeFor計算會傳回一個比給定整數大且最接近的2的幂次方整數，并指派給threshold      

預設初始容量為16，必須為2的幂      

loadFactor 擴容因子 預設為DEFAULT_LOAD_FACTOR 即0.75（在0.75屬于時間和空間的一個平衡）
當容量一定是2^n時，h & (length - 1) == h % length
MIN_TREEIFY_CAPACITY：
是指當桶被轉化為樹形結構的時候，此時桶所擁有的最小容量

MAXIMUM_CAPACITY = 1 << 30;這是定義容量的最大值。
      

public HashMap()// 預設構造函

public HashMap(int initialCapacity, float loadFactor) / /指定“容量大小”和“加載因子”的構造函數

public HashMap(int initialCapacity) // 指定“容量大小”的構造函數

public HashMap(Map<? extends K, ? extends V> m) // 包含“子Map”的構造函數,将m中的全部元素逐個添加到HashMap中

哈希沖突的解決方法：開放位址法，鍊位址法，公共溢出法，再哈希法

小結

(1) 擴容是一個特别耗性能的操作，是以當程式員在使用HashMap的時候，估算map的大小，初始化的時候給一個大緻的數值，避免map進行頻繁的擴容。