hashmap和hash算法研究
總述
hashmap作為java中非常重要的數據結構，對于key-value類型的存儲（緩存，臨時映射表，。。。）等不可或缺，hashmap本身是非線程安全的，對于多線程條件下需要做競爭條件處理，可以通過Collections和ConcurrentHashmap來替代。
Hashmap源碼探究
數據結構
hashmap存儲數據主要是通過數組+鏈表實現的，通過將key的hashcode映射到數組的不同元素（桶，hash中的叫法），然后沖突的元素放入鏈表中。
鏈表結構（Entry）
采用靜態內部類
存儲操作
當存入的值為null的時候，操作會找到table[0]，set key為null的值為新值
若果不是空值，則進行hash，
hash算法
可以看到，算法進行了二次hash，使高位也參與到計算中，防止低位不變造成的hash沖突
注：這一切的目的實際上都是為了使value盡量分布到不同的
對于任意給定的對象，只要它的 hashCode() 返回值相同，那么程序調用 hash(int h) 方法所計算得到的 hash 碼值總是相同的。我們首先想到的就是把 hash 值對數組長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。但是，“模”運算的消耗還是比較大的，在 HashMap 中是這樣做的：調用 indexFor(int h, int length) 方法來計算該對象應該保存在 table 數組的哪個索引處。indexFor(int h, int length) 方法的代碼如下：
這又要牽扯到hashmap的另外一個問題，關于length長度的定義
在put操作的開始，有判斷table是否為空，如果為空則會初始化table，初始化的代碼如下：
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
容量的提升都是以2的冪的方式
這段代碼保證初始化時 HashMap 的容量總是 2 的 n 次方，即底層數組的長度總是為 2的 n 次方。當 length 總是 2 的 n 次方時，h& (length-1)運算等價于對 length 取模，也就是h%length，但是&比%具有更高的效率。
這看上去很簡單，其實比較有玄機的，我們舉個例子來說明：
假設數組長度分別為 15 和 16，優化后的 hash 碼分別為 8 和 9，那么&運算后的結果如下：
讀操作：
讀操作通過hash后的值，一樣是調用indexFor方法找到對應的序號，然后遍歷鏈表找到對應的value返回
resize操作
resize只有在hashmap中元素的大小達到臨界值的時候才會進行，而臨界值和loadFactor 參數有關，只有數量達到loadFactor *table.length才會重新分配table，元素也將重新映射，這是非常耗性能的操作，所以最好一開始能確定元素的大概范圍
HashMap 的性能參數(這段直接從參考文章引來)：
HashMap 包含如下幾個構造器：
HashMap()：構建一個初始容量為 16，負載因子為 0.75 的 HashMap。
HashMap(int initialCapacity)：構建一個初始容量為 initialCapacity，負載因子
為 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負載因子創建一個 HashMap。HashMap 的基礎構造器 HashMap(int initialCapacity, float loadFactor)帶有兩個參數，它們是初始容量 initialCapacity 和加載因子 loadFactor。
initialCapacity：HashMap 的最大容量，即為底層數組的長度。
loadFactor：負載因子 loadFactor 定義為：散列表的實際元素數目(n)/ 散列表的容量(m)。負載因子衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均時間是 O(1+a)，因此如果負載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負載因子太小，那么散列表的數據將過于稀疏，對空間造成嚴重浪費。
HashMap 的實現中，通過 threshold 字段來判斷 HashMap 的最大容量：
Java 代碼
threshold = (int)(capacity * loadFactor);
結合負載因子的定義公式可知， threshold 就是在此 loadFactor 和 capacity 對應下允許的最大元素數目，超過這個數目就重新 resize，以降低實際的負載因子。默認的的負載因子0.75 是對空間和時間效率的一個平衡選擇。當容量超出此最大容量時， resize 后的 HashMap容量是容量的兩倍：
if (size++ >= threshold)
resize(2 * table.length);
快速失敗
我們知道 java.util.HashMap 不是線程安全的，因此如果在使用迭代器的過程中有其他
線程修改了 map，那么將拋出 ConcurrentModificationException，這就是所謂 fail-fast 策略。
這一策略在源碼中的實現是通過 modCount 域， modCount 顧名思義就是修改次數，對HashMap 內容的修改都將增加這個值，那么在迭代器初始化過程中會將這個值賦給迭代器的 expectedModCount。
來自：http://my.oschina.net/zhenglingfei/blog/403146