歡迎訪問我的博客：http://wangnan.tech
參考：
- http://blog.csdn.net/vking_wang/article/details/14166593
- http://wiki.jikexueyuan.com/project/java-collection/hashmap.html
HashMap數(shù)據(jù)結(jié)構(gòu)
數(shù)組
數(shù)組存儲區(qū)間是連續(xù)的，占用內(nèi)存嚴(yán)重，故空間復(fù)雜的很大驰弄。但數(shù)組的二分查找時間復(fù)雜度小，為O(1)落追；數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難涯肩；
鏈表
鏈表存儲區(qū)間離散轿钠，占用內(nèi)存比較寬松，故空間復(fù)雜度很小病苗，但時間復(fù)雜度很大疗垛，達(dá)O（N）。鏈表的特點(diǎn)是：尋址困難硫朦，插入和刪除容易贷腕。
哈希表
首先HashMap里面實現(xiàn)一個靜態(tài)內(nèi)部類Entry，其重要的屬性有 key , value, next，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對實現(xiàn)的一個基礎(chǔ)bean泽裳，我們上面說到HashMap的基礎(chǔ)就是一個線性數(shù)組瞒斩，這個數(shù)組就是Entry[]，Map里面的內(nèi)容都保存在Entry[]里面涮总。
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
那么我們能不能綜合兩者的特性胸囱，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)瀑梗？答案是肯定的烹笔，這就是我們要提起的哈希表。哈希表（(Hash table）既滿足了數(shù)據(jù)的查找方便抛丽，同時不占用太多的內(nèi)容空間箕宙，使用也十分方便。
哈希表是由數(shù)組+鏈表組成的铺纽，一個長度為16的數(shù)組中，每個元素存儲的是一個鏈表的頭結(jié)點(diǎn)哟忍。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢狡门。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數(shù)組長度取模得到
簡單地說锅很，HashMap 在底層將 key-value 當(dāng)成一個整體進(jìn)行處理其馏，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry[] 數(shù)組來保存所有的 key-value 對爆安，當(dāng)需要存儲一個 Entry 對象時叛复，會根據(jù) hash 算法來決定其在數(shù)組中的存儲位置，在根據(jù) equals 方法決定其在該數(shù)組位置上的鏈表中的存儲位置扔仓；當(dāng)需要取出一個Entry 時褐奥，也會根據(jù) hash 算法找到其在數(shù)組中的存儲位置，再根據(jù) equals 方法從該位置上的鏈表中取出該Entry翘簇。
put
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //null總是放在數(shù)組的第一個鏈表中
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//遍歷鏈表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果key在鏈表中已存在撬码，則替換為新value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //參數(shù)e, 是Entry.next
//如果size超過threshold，則擴(kuò)充table大小版保。再散列
if (size++ >= threshold)
resize(2 * table.length);
}
get
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
//先定位到數(shù)組元素呜笑，再遍歷該元素處的鏈表
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.equals(k)))
return e.value;
}
return null;
}
初始大小
public HashMap(int initialCapacity, float 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();
}
rehash
當(dāng) HashMap 中的元素越來越多的時候，hash沖突的幾率也就越來越高彻犁，因為數(shù)組的長度是固定的叫胁。所以為了提高查詢的效率，就要對 HashMap 的數(shù)組進(jìn)行擴(kuò)容汞幢，數(shù)組擴(kuò)容這個操作也會出現(xiàn)在 ArrayList 中驼鹅，這是一個常用的操作，而在 HashMap 數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置谤民，并放進(jìn)去堰酿，這就是 resize。
那么 HashMap 什么時候進(jìn)行擴(kuò)容呢张足？當(dāng) HashMap 中的元素個數(shù)超過數(shù)組大小 loadFactor時触创，就會進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為 0.75为牍，這是一個折中的取值哼绑。也就是說，默認(rèn)情況下碉咆，數(shù)組大小為 16抖韩，那么當(dāng) HashMap 中元素個數(shù)超過 160.75=12 的時候，就把數(shù)組的大小擴(kuò)展為 2*16=32疫铜，即擴(kuò)大一倍茂浮，然后重新計算每個元素在數(shù)組中的位置，而這是一個非常消耗性能的操作壳咕，所以如果我們已經(jīng)預(yù)知 HashMap 中元素的個數(shù)席揽，那么預(yù)設(shè)元素的個數(shù)能夠有效的提高 HashMap 的性能。
Fail-Fast 機(jī)制
我們知道 java.util.HashMap 不是線程安全的谓厘，因此如果在使用迭代器的過程中有其他線程修改了 map幌羞，那么將拋出 ConcurrentModificationException，這就是所謂 fail-fast 策略竟稳。
ail-fast 機(jī)制是 java 集合(Collection)中的一種錯誤機(jī)制属桦。 當(dāng)多個線程對同一個集合的內(nèi)容進(jìn)行操作時，就可能會產(chǎn)生 fail-fast 事件他爸。
例如：當(dāng)某一個線程 A 通過 iterator去遍歷某集合的過程中聂宾，若該集合的內(nèi)容被其他線程所改變了；那么線程 A 訪問集合時诊笤，就會拋出 ConcurrentModificationException 異常亏吝，產(chǎn)生 fail-fast 事件。
由所有 HashMap 類的“collection 視圖方法”所返回的迭代器都是快速失敗的：在迭代器創(chuàng)建之后盏混，如果從結(jié)構(gòu)上對映射進(jìn)行修改蔚鸥，除非通過迭代器本身的 remove 方法，其他任何時間任何方式的修改许赃，迭代器都將拋出 ConcurrentModificationException
HashMap 的兩種遍歷方式
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
效率高
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
效率低
