HashMap 是一個散列表，它存儲的內容是鍵值對(key-value)映射。
HashMap 繼承於AbstractMap，實現了Map、Cloneable、java.io.Serializable接口。
HashMap 的實現不是同步的，這意味著它是線程不安全的。它的key、value都可以為null。此外，HashMap中的映射是無序的。
本文重點是介紹HashMap中的“拉鍊法”解決散列衝突。如果想了解其他方面的知識可參考http://www.cnblogs.com/skywang12345/p/3310835.html。
下面先介紹一下散列表及散列衝突的基本概念。
2.Hash表的概念
我們知道，有一種數據結構能夠快速地查找所需的對象（O（1）時間複雜度），這就是散列表（hash table）。散列碼（hash code）是由對象的實例產生的一個整數。
更準確的說，具有不同的數據域的對象將產生不同的散列碼。如下圖（這裡順帶提一下散列表的概念，即哈希表的概念）：
設所有可能出現的關鍵字集合記為U(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為K（|K|比|U|小得多）。
散列方法是使用函數h將U映射到表T[0..m-1]的下標上（m=O(|U|)）。這樣以U中關鍵字為自變量，以h為函數的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。
其中：
① h：U→{0，1，2，…，m-1} ，通常稱h為散列函數(Hash Function)。散列函數h的作用是壓縮待處理的下標範圍，使待處理的|U|個值減少到m個值，從而降低空間開銷。
② T為散列表(Hash Table)。
③ h(Ki)(Ki∈U)是關鍵字為Ki結點存儲地址(亦稱散列值或散列地址)。
④ 將結點按其關鍵字的散列地址存儲到散列表中的過程稱為散列(Hashing)
3.散列衝突
兩個不同的關鍵字，由於散列函數值相同，因而被映射到同一表位置上。該現象稱為衝突(Collision)或碰撞。發生衝突的兩個關鍵字稱為該散列函數的同義詞(Synonym)。
上圖中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的結點的存儲地址相同。
有了衝突，那自然要儘可能地去避免衝突。那麼如何安全避免衝突呢？有兩個條件：
- 其一是|U|≤m；
- 另一個是設計合適的哈希函數。
這隻適用於|U|較小，且關鍵字均事先已知的情況，此時經過精心設計散列函數h有可能完全避免衝突。通常情況下，h是一個壓縮映像。雖然|K|≤m（已知的關鍵字），但|U|>m（未知的關鍵字），故無論怎樣設計h，也不可能完全避免衝突。因此，只能在設計h時儘可能使衝突最少。同時還需要確定解決衝突的方法，使發生衝突的同義詞能夠存儲到表中。
HashMap中採用的“拉鍊法”就是一種衝突解決的方式（hash函數的設計才是衝突避免，但不是一種完全的衝突解決方法），如下圖所示為“拉鍊法”結構。
但是HashMap中的節點是Map.Entry類型的，而不是簡單的value，如下圖所示，左邊是一個Node
那麼它是如何解決衝突的呢？即key值不同的兩個或多個Map.Entry
閱讀更多 JAVA熊 的文章
