散列表要解決的一個問題就是散列值的沖突問題通常是兩種方法鏈表法和開放地址法鏈表法就是將相同hash值的對象組織成一個鏈表放在hash值對應的槽位開放地址法是通過一個探測算法當某個槽位已經被占據的情況下繼續查找下一個可以使用的槽位javautilHashMap采用的鏈表法的方式鏈表是單向鏈表因此在刪除過程中要自己維持prev節點我想不采用雙向鏈表是從節省空間考慮一個典型的查找過程
for (Entry<KV> e = table[indexFor(hash tablelength)];
e != null;
e = enext) {
Object k;
if (ehash == hash &&
((k = ekey) == key || (key != null && keyequals(k))))
return e;
}
HashMap采用鏈表法而不是開放地址法猜想可能的原因是從實用角度出發對空間和時間效率做出的折中選擇采用開放地址法無論是線性探測或者二次探測都可能造成群集現象而雙重散列會要求散列表的裝填程度比較低的情況下會有比較好的查找效率容易造成空間的浪費
什麼是負載因子？負載因子a定義為
a=散列表的實際元素數目（n）/ 散列表的容量（m）
負載因子衡量的是一個散列表的空間的使用程度負載因子越大表示散列表的裝填程度越高反之愈小對於使用鏈表法的散列表來說查找一個元素的平均次數是 （+a）次因此如果負載因子越大對空間的利用更充分然而後果是查找效率的降低如果負載因子太小那麼散列表的數據將過於稀疏對空間造成嚴重浪費
回到HashMap的實現HashMap中的loadFactor其實定義的就是該map對象允許的最大的負載因子如果超過這個系數將重新resize這個是通過threshold字段來判斷看threshold的計算
threshold = (int)(capacity * loadFactor);
結合上面的負載因子的定義公式可知threshold就是在此loadFactor和capacity對應下允許的最大元素數目超過這個數目就重新resize以降低實際的負載因子默認的的負載因子是對空間和時間效率的一個平衡選擇注意到的一點是resize的規模是現有 capacity的兩倍
if (size++ >= threshold)
resize( * tablelength);
可能你也注意到了javautilHashMap對key的hash值多做了一步處理而不是直接使用hashCode
static int hash(int h) {
h ^= (h >>> ) ^ (h >>> );
return h ^ (h >>> ) ^ (h >>> );
}
這個處理的原因在於HashMap的容量總是采用的p次冪而取index（槽位）的方法是
static int indexFor(int h int length) {
return h & (length);
}
這一運算等價於對length取模也就是
h % ^p
返回的將是h的p個最低位組成的數字我們假設hash輸入是符合簡單一致散列然而這一假設並不能推論出hash的p個最低位也會符合簡單一致散列也許h的這p個最低位相同的幾率很大那麼沖突的幾率就非常大了優秀的散列函數應該需要考慮所有的位
因此為了防止這些壞的散列函數造成效率的降低HashMap預先對hash值做了處理以考慮到所有的位根據注釋也可以知道這個處理我看不懂留待高人解釋也許來自於某本算法書也不一定
我們知道javautilHashMap不是線程安全的因此如果在使用迭代器的過程中有其他線程修改了map那麼將拋出ConcurrentModificationException這就是所謂failfast策略（速錯）這一策略在源碼中的實現是通過 modCount域modCount顧名思義就是修改次數對HashMap內容的修改都將增加這個值那麼在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount
HashIterator() {
expectedModCount = modCount;
if (size > ) { // advance to first entry
Entry[] t = table;
while (index < tlength && (next = t[index++]) == null)
;
}
}
在迭代過程中判斷modCount跟expectedModCount是否相等如果不相等就表示已經有其他線程修改了map
final Entry<KV> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
注意到modCount聲明為volatile
保證線程之間修改的可見性
From:http://tw.wingwit.com/Article/program/Java/JSP/201311/19501.html
