探究HashMap的工作原理

摘要：經過大學四年，我也剛剛畢業了3個月了，學習android也有一兩年了，可是在大學的生活中，磨練出來的解決實際問題的能力是有的，完成開發任務還是可以的，但是總覺得技術遇到了瓶頸期，沒有辦法進步很多。因此想靜下心來看JDK的源碼，看看這些人是怎么設計出來的？為什么要這么設計？我能從中體會到什么？對我今后的職業生涯有什么幫助？跟著優秀的人一起成長吧。

我們用HaspMap最關心的兩個方法和幾個變量是：

/** 默認的初始化容量，2^4 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

/** 默認的負載因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/*數組，Entry是存放Key value的基礎bean */
transient Entry[] table;

/** 負載因子*/
final float loadFactor;

/** *下一次的負載table容量 (capacity * load factor) *
int threshold;

public V put(K key,V value)

public V get(Object key)

為了幫助理解和記憶，貼上兩張圖：

Paste_Image.png

Paste_Image.png

從上圖我們可以發現哈希表是由 數組+鏈表 組成的，一個長度為 我們看到的第一個變量 DEFAULT_INITIAL_CAPACITY=16 的數組中，每個元素存儲的是一個鏈表的頭結點。那么這些元素是按照什么樣的規則存儲到數組中呢。一般情況是通過hash(key.hashCode()%table.length)獲得，也就是元素的key的哈希值對數組長度取模得到。

HashMap其實也是一個線性的數組實現的,所以可以理解為其存儲數據的容器就是一個線性數組。HashMap里面實現一個靜態內部類Entry，其重要的屬性有key,value,next，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對實現的一個基礎bean，我們上面說到HashMap的基礎就是一個線性數組，這個數組就是Entry[]，Map里面的內容都保存在Entry[]里面。

HashMap存取過程

public V put(K key, V value) {    
     if (key == null)       
     return putForNullKey(value);    
     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;        
        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;
}

看源碼得出幾個結論：

1.HashMap可以存儲null的key。

2.通過key.hashCode找到hash值，然后跟table.length的取模，得到數組下標。然后遍歷鏈表，如果hash值且key值相等，則替換原來的值。

3.table添加新的元素時并沒有奇怪，奇怪的是我們知道數據的默認容量是16，超過了16怎么辦，HashMap是怎么處理的呢？

所以要看一下上述代碼中addEntry這個方法里面到底做什么操作。

void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

到這里已經很明顯，我們發現了HashMap的處理方式，是size > threshold的時候就會去擴容。那么這個threshold是什么東西呢？文章的開頭我們已經把他列出來了，threshold = capacity loadFactor的結果，loadFactor是負載因此，capacity是容量。那么我們可以得出很簡單的結論就是首次初始化的時候threshold = DEFAULT_INITIAL_CAPACITY（16） DEFAULT_LOAD_FACTOR （0.75） ，就是超過了容量的75%的時候就會去擴容。

當哈希表的容量超過默認容量時，必須調整table的大小。當容量已經達到最大可能值時，那么該方法就將容量調整到Integer.MAX_VALUE返回，這時，需要創建一張新表，將原表的映射到新表中。

我帶著好奇心繼續探索resize這個方法。

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    //重新計算index
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

到這里基本上清楚了HashMap的進行put時候的整個過程了。相同get方法我就不貼代碼了。有興趣可以去研究源碼。

當我看源碼看到這一步我可能比較困惑，HashMap究竟優勢在哪兒？

我們要分析一下HashMap的數據結構，上述我們已經了解HashMap的數據結構是 數組加鏈表。

數組存儲區間是連續的，占用內存嚴重，故空間復雜的很大。但數組的二分查找時間復雜度小，為O(1)；數組的特點是：尋址容易，插入和刪除困難；

鏈表存儲區間離散，占用內存比較寬松，故空間復雜度很小，但時間復雜度很大，達O（N）。鏈表 的特點是：尋址困難，插入和刪除容易。

來自：http://www.jianshu.com/p/006f9f446fcb