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