1.HashMap的數(shù)據(jù)結(jié)構(gòu)

由數(shù)組和鏈表實現(xiàn)

數(shù)組：
數(shù)組存儲區(qū)間是連續(xù)的，占用內(nèi)存嚴(yán)重，故時間復(fù)雜度大。但數(shù)組的二分時間復(fù)雜度小，為O(1)；數(shù)組的特點是：尋址容易，插入和刪除困難；

鏈表：
鏈表存儲區(qū)間離散，占用內(nèi)存比較寬松，故空間復(fù)雜度小，時間復(fù)雜度大，達(dá)O(N)。鏈表的特點是：尋址困難，插入和刪除比較容易。

哈希表（Hash Table）
結(jié)合數(shù)組和鏈表的特點，做出尋址容易，插入和刪除也容易.

哈希表有多種不同的實現(xiàn)方法，下面是常用的拉鏈法，如圖：
![Uploading QQ圖片20170516092933_183614.png . . .]

從上圖可見，哈希表是由數(shù)組和鏈表組成的，一個長度為16的數(shù)組中，每個元素存儲的是一個鏈表的頭結(jié)點。比如12%16=12,28%16=12,108%16=12,140%16=12,16為數(shù)組的長度，hash(key)%len=數(shù)組的index

HashMap里面實現(xiàn)一個靜態(tài)內(nèi)部類Map.Entry，其重要的屬性有key,value,next,從屬性key，value我們就能看出Entry就是HashMap鍵值對實現(xiàn)的一個基礎(chǔ)的bean，并持有一個指向下一個數(shù)組的引用，構(gòu)成了鏈表。我們上面說的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;

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
...
}

transient聲明是個實例變量，當(dāng)對象存儲時，它不需要維持。transient關(guān)鍵字標(biāo)記的成員變量不需要序列化過程。

2.HashMap的存儲實現(xiàn)

1）put存儲

疑問：如果兩個key通過hash%Entry[].length得到的index相同，會不會有覆蓋的危險？
　　這里HashMap里面用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的一個概念。上面我們提到過Entry類里面有一個next屬性，作用是指向下一個Entry。打個比方， 第一個鍵值對A進(jìn)來，通過計算其key的hash得到的index=0，記做:Entry[0] = A。一會后又進(jìn)來一個鍵值對B，通過計算其index也等于0，現(xiàn)在怎么辦？HashMap會這樣做:B.next = A,Entry[0] = B,如果又進(jìn)來C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發(fā)現(xiàn)index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起。所以疑問不用擔(dān)心。也就是說數(shù)組中存儲的是最后插入的元素。到這里為止，HashMap的大致實現(xiàn)，我們應(yīng)該已經(jīng)清楚了。

public V put(K key, V value) {
        //HashMap允許存放null鍵和null值
        //當(dāng)key為null時，調(diào)用putForKey方法，將value放置在數(shù)組第一個位置。
        if (key == null)
            return putForNullKey(value);
        //根據(jù)key的keyCode重新計算hash值
        int hash = hash(key.hashCode());
        //搜索指定hash值在對應(yīng)table中的索引
        int i = indexFor(hash, table.length);
        //如果i索引處的Entry不為null，通過循環(huán)不斷遍歷e元素的下一個元素
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //如果i索引處的Entry為null，表明此處還沒有Entry。
        modCount++;
        //將key、value添加到索引處
        addEntry(hash, key, value, i);
        return null;
    }

從上面的源代碼中可以看出：當(dāng)我們往HashMap中put元素的時候，先根據(jù)key的hashCode重新計算hash值，根據(jù)hash值得到這個元素在數(shù)組中的位置（即下標(biāo)），如果數(shù)組該位置上已經(jīng)存放有其他元素了，那么在這個位置上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。如果數(shù)組該位置上沒有元素，就直接將該元素放到此數(shù)組中的該位置上。

void addEntry(int hash, K key, V value, int bucketIndex) {
             // 獲取指定 bucketIndex 索引處的 Entry 
        Entry<K, V> e = table[bucketIndex];
             // 將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry
        table[bucketIndex] = new Entry<K, V>(hash, key, value, e); // 參數(shù)e是Entry.next
             // 如果 Map 中的 key-value 對的數(shù)量超過了極限 
        if (size++ >= threshold)
             // 把 table 對象的長度擴(kuò)充到原來的2倍。
            resize(2 * table.length);

    }

HashMap里面包含一些優(yōu)化方面的實現(xiàn)，比如，Entry[]長度一定后，隨著map數(shù)據(jù)的越來越長，這樣同一個index的鏈就睡很長，會不會影響性能？HashMap里面設(shè)置一個因子，隨著map的size越來越大，Entry[]會以一定的規(guī)則加長長度。

static int indexFor(int hash, int length){
        return hash ＆ (length-1)

h& (length-1)運(yùn)算等價于對length取模，也就是h%length，但是&比%具有更高的效率。 這個方法非常巧妙，它通過 h & (table.length -1) 來得到該對象的保存位，而HashMap底層數(shù)組的長度總是 2 的 n 次方，這是HashMap在速度上的優(yōu)化。

在 HashMap 構(gòu)造器中有如下代碼：

int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;  

這段代碼保證初始化時HashMap的容量總是2的n次方，即底層數(shù)組的長度總是為2的n次方。

2）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;
}

歸納起來簡單地說，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。