HashMap 數據結構
圖中的 "table" 在 HashMap 中是一個 Node
什麼是hash？
百度百科：hash 一般被翻譯為 “散列”， 也有直接音譯為“哈希”的，就是把任意長度的輸入，通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
wikipedia :
哈希函數 : 哈希函數就是能將任意長度的數據映射為固定長度的數據的函數。哈希函數返回的值被叫做哈希值、哈希碼、散列，或者直接叫做哈希。一個使用場景就是哈希表，哈希表被廣泛用於快速搜索數據。
哈希表：哈希表是一種能實現關聯數組的抽象數據結構，能把很多「鍵」映射到很多「值」上。哈希表使用哈希函數來計算索引，一個索引對應一個值。
HashMap 初始化
<code>// initialCapacity 初始化容量大小
// loadFactor 負載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// threshold 是HashMap是否要進行擴容的標記量
this.threshold = tableSizeFor(initialCapacity);
}/<code>
initialCapacity ， loadFactor 這兩個參數都影響著HashMap的性能。initialCapacity 決定了下一次 resize 後的容量（capacity << 1） , loadFactor 決定了 resize 發生的條件 （size > (capacity * loadFactor )） （一般情況下 ， 極端情況下是 size > Integer.MAX_VALUE） 。如果初始化時不指定這兩個參數，會使用默認值 ， capacity = 16 ， loadFactor = 0.75 。對於 16 的容量空間，如果不能充分利用的話會造成空間資源的浪費。（個人認為高手之所以高都體現在細節之中）
散列過程
散列的過程就是將存入的元素均勻的分佈到HashMap內部Node數據的過程。均勻分佈指的是 ， 數組中的每個位置儘量都存儲了一個Node節點，並且該位置上的鏈表只有一個元素。散列分佈的越均勻進行碰撞檢測的次數就越少，查詢性能就越高。
這就是一個散列較為均勻的 ， 查詢時最好情況下可以直接定位 ， 最壞情況下需要進行一次碰撞檢測。
這是一個散列的不均勻的，查詢時會進行多次碰撞檢測造成效率較低。
碰撞檢測
((capacity - 1) & hash) 會計算出 key 存儲在 Node 數組中的那個位置上 （得到的值始終會落在 Node數組的長度範圍內 ， 等同於 hash % capacity ， 不過位運算的效率更高）， 如果發現該位置上已經存在Node 了，會將新存入的數據作為鏈表的尾節點。這樣存儲和查詢時都會進行碰撞檢測。碰撞檢測其實就是比較傳入的 key 的 hash 與同一 bucket 上所有的 key 的 hash 是否一致的過程。 jdk8 在這方面做了優化，加入了樹型結構來彌補鏈表線性結構性能較低的不足。
提高碰撞檢測的性能 ， 從代碼中也能看出來 ， 該運算的最理想情況（hash 相等情況下）是執行兩步 ， 比較 hash ， 比較 key 。 最壞情況是執行 4 步 ， 只要取最好情況就達到了提高性能的目的 。以此類推 key 就可以用一些 String ， Enum 這之類的數據類型。
<code>if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
// .......
}/<code>
reszie
rezise 是一個較為消耗性能的過程 ， 在首次向HashMap中存入元素的時候會進行首次resize , 在之後每當產生新節點（這裡的節點指的是Node） ， 同時 size > threshold 的時候會進行 resize ，resize 的過程也是 rehash 的過程。本篇儘量不分析源碼只是做整體的，概念上的瞭解。
併發安全
HashMap 是不支持併發的 ， 在併發修改時它採用 fail-fast 的策略 ， 拋出 ConcurrentModificationException 。 多線程環境下操作HashMap有可能會造成死循環 ， 在 resize 的過程當中。不要在多線程場景下使用HashMap 。
閱讀更多 黑帽子技術 的文章
