HashMap是基于哈希表的Map接口的實(shí)現(xiàn)，允許null值和null鍵（HashMap和Hashtable大致一樣，除了不同步和允許null外）。HashMap不保存映射的順序，特別是不保證該順序恒久不變。
HashMap的實(shí)現(xiàn)假定hash函數(shù)將各個元素正確分布在各桶之間，可為基本操作（如get()和set()）提供穩(wěn)定的性能，迭代集合視圖所需的時間與HashMap 實(shí)例的“容量”（桶的數(shù)量）及其大小（鍵-值映射關(guān)系數(shù)）的和成比例。所以，如果迭代性能很重要，則不要將初始容量設(shè)置得太高（或?qū)⒓虞d因子設(shè)置得太低）。 （注：這段同HashSet很相似，其實(shí)HashSet是基本HashMap實(shí)現(xiàn)的，所以在性能的控制上也一樣）
HashMap 的實(shí)例有兩個參數(shù)影響其性能：初始容量和加載因子。容量是哈希表中桶的數(shù)量，初始容量只是哈希表在創(chuàng)建時的容量。加載因子是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時，通過調(diào)用 rehash 方法將容量翻倍。HashMap的默認(rèn)初始容量是16，默認(rèn)加載因子是0.75，這樣，當(dāng)HashMap里的元素超過16*0.75即12時，調(diào)用rehash方法，使容量增長一倍。
通常，默認(rèn)加載因子 (.75) 在時間和空間成本上尋求一種折衷。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數(shù) HashMap類的操作中，包括 get 和 put 操作，都反映了這一點(diǎn)）。在設(shè)置初始容量時應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子，以便最大限度地降低 rehash 操作次數(shù)。如果初始容量大于最大條目數(shù)除以加載因子，則不會發(fā)生 rehash 操作。
如果很多映射關(guān)系要存儲在 HashMap 實(shí)例中，則相對于按需執(zhí)行自動的 rehash 操作以增大表的容量來說，使用足夠大的初始容量創(chuàng)建它將使得映射關(guān)系能更有效地存儲。
注意，此實(shí)現(xiàn)不是同步的。 如果多個線程同時訪問此映射，而其中至少一個線程從結(jié)構(gòu)上修改了該映射，則它必須 保持外部同步。（結(jié)構(gòu)上的修改是指添加或刪除一個或多個映射關(guān)系的操作；僅改變與實(shí)例已經(jīng)包含的鍵關(guān)聯(lián)的值不是結(jié)構(gòu)上的修改。）這一般通過對自然封裝該映射的對象進(jìn)行同步操作來完成。如果不存在這樣的對象，則應(yīng)該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在創(chuàng)建時完成這一操作，以防止對映射進(jìn)行意外的不同步訪問，如下所示：
Map m = Collections.synchronizedMap(new HashMap(...));
由所有此類的“集合視圖方法”所返回的迭代器都是快速失敗的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對映射進(jìn)行修改，除非通過迭代器
自身的 remove
或 add
方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException
。因此，面對并發(fā)
的修改，迭代器很快就會完全失敗，而不冒在將來不確定的時間任意發(fā)生不確定行為的風(fēng)險。
注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發(fā)修改時，不可能作出任何堅決的保證。快速失敗迭代器盡最大
努力拋出 ConcurrentModificationException
。因此，編寫依賴于此異常程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應(yīng)
該僅用于檢測程序錯誤。
HashMap的構(gòu)造函數(shù)：
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);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
可以看出，當(dāng)生成HashMap對象時，如果initialCapacity的數(shù)值比較大時，capacity 會被賦于等于或大于initialCapacity 的值，然后
創(chuàng)建一個有capacity 個Entry對象的table數(shù)組，所以initialCapacity的數(shù)值不能太大，否則會生成比較大的數(shù)組table，占用比較大的應(yīng)用內(nèi)
存，造成內(nèi)存浪費(fèi)。
HashMap的默認(rèn)構(gòu)造函數(shù)：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
默認(rèn)構(gòu)造函數(shù)里的初始容量為16，加載因子為0.75，這樣會生成含有16*0.75=12個Entry對象的數(shù)組table，當(dāng)HashMap里的元素數(shù)
量超過12個時，會將HashMap的容量翻1倍，生成包含32個Entry對象的數(shù)組。
put方法：
public V put(K key, V value) {
K k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
if (e.hash == hash && eq(k, e.key)) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, k, value, i);
return null;
}
K k = maskNull(key);這行是判斷key是否為null，如果為null，則返回一個靜態(tài)的K（Object）對象做為鍵值，這就是HashMap為什么允許null鍵存在的原因。
int hash = hash(k);
int i = indexFor(hash, table.length);
這連續(xù)的兩步就是 HashMap 最牛的地方！研究完我都汗顏了，其中 hash 就是通過 key 這個Object的 hashcode 進(jìn)行 hash，然后通過 indexFor 獲得在Object table的索引值。
table？？？不要驚訝，其實(shí)HashMap也神不到哪里去，它就是用 table 來放的。最牛的就是用 hash 能正確的返回索引。其中的hash算法，我跟JDK的作者 Doug 聯(lián)系過，他建議我看看《The art of programing vol3》可恨的是，我之前就一直在找，我都找不到，他這樣一提，我就更加急了，可惜口袋空空啊！！！
不知道大家有沒有留意 put 其實(shí)是一個有返回的方法，它會把相同鍵值的 put 覆蓋掉并返回舊的值！如下方法徹底說明了 HashMap 的結(jié)構(gòu)，其實(shí)就是一個表加上在相應(yīng)位置的Entry的鏈表：
for (Entry e = table; e != null; e = e.next) {
if (e.hash == hash && eq(k, e.key)) {
Object oldvalue = e.value;
e.value = value; //把新的值賦予給對應(yīng)鍵值。
e.recordAccess(this); //空方法，留待實(shí)現(xiàn)
return oldvalue; //返回相同鍵值的對應(yīng)的舊的值。
}
}
modCount++; //結(jié)構(gòu)性更改的次數(shù)
addEntry(hash, k, value, i); //添加新元素，關(guān)鍵所在！
return null; //沒有相同的鍵值返回
}
我們把關(guān)鍵的方法拿出來分析：
void addEntry(int hash, Object key, Object value, int bucketIndex) {
table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);
因為 hash 的算法有可能令不同的鍵值有相同的hash碼并有相同的table索引，如：key＝“33”和key＝Object g的hash都是－8901334，那它經(jīng)過indexfor之后的索引一定都為i，這樣在new的時候這個Entry的next就會指向這個原本的 table，再有下一個也如此，形成一個鏈表，和put的循環(huán)對定e.next獲得舊的值。到這里，HashMap的結(jié)構(gòu)，大家也十分明白了吧？
if (size++ >= threshold) //這個threshold就是能實(shí)際容納的量
resize(2 * table.length); //超出這個容量就會將Object table重構(gòu)
所謂的重構(gòu)也不神，就是建一個兩倍大的table（我在別的論壇上看到有人說是兩倍加1，把我騙了），然后再一個個indexfor進(jìn)去！注意！！這就是效率！！如果你能讓你的HashMap不需要重構(gòu)那么多次，效率會大大提高！
說到這里也差不多了，get比put簡單得多，大家，了解put，get也差不了多少了。對于collections我是認(rèn)為，它是適合廣泛的，當(dāng)不完 全適合特有的，如果大家的程序需要特殊的用途，自己寫吧，其實(shí)很簡單。（作者是這樣跟我說的，他還建議我用LinkedHashMap,我看了源碼以后發(fā) 現(xiàn)，LinkHashMap其實(shí)就是繼承HashMap的，然后override相應(yīng)的方法，有興趣的同人，自己looklook）建個 Object table，寫相應(yīng)的算法，就ok啦。
舉個例子吧，像 Vector，list 啊什么的其實(shí)都很簡單，最多就多了的同步的聲明，其實(shí)如果要實(shí)現(xiàn)像Vector那種，插入，刪除不多的，可以用一個Object table來實(shí)現(xiàn)，按索引存取，添加等。
如果插入，刪除比較多的，可以建兩個Object table，然后每個元素用含有next結(jié)構(gòu)的一個table存，如果要插入到i，但是i已經(jīng)有元素，用next連起來，然后size＋＋，并在另一個table記錄其位置。