Java集合類之HashMap源碼分析

    hash表是一種常見的數據結構，主要是通過hash算法將數據盡可能的散列開來存放，當要查找某一數據時，可以通過hash算法直接定位，節省了對比查找的時間。map是一種key、value形式的鍵值對，將hash表和map結合即形成了HashMap。

    在Java中HashMap的數據是以Entry數組的形式存放的，HashMap通過對key進行hash運算得到一個數組下標，然后將數據存放到Entry數組對應的位置，又因為不同的key進行hash運算可能會得到一個相同的數組下標，為了解決碰撞覆蓋沖突，所以Entry本身又是一個鏈表的結構，即以后不同的key相同數組下標的數據的next會被賦值為已存在Entry鏈表，新的Entry會替換數組值。

HashMap的存儲數據的示例圖如下：

HashMap 的put方法的源碼解析

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value); // HashMap接收key為null的數據
        int hash = hash(key.hashCode()); //對key的hashCode再進行hash運算
        int i = indexFor(hash, table.length);//根據hash值和entry數組的大小計算出新增數據應該存放的數組位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
             // for循環遍歷找到的數組下標的entry，如果hash值和key都相等，則覆蓋原來的value值

            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++;
    //如果上面for循環沒有找到相同的hash和key，則增加一個entry
    addEntry(hash, key, value, i);
    return null;
}</K,V></pre> <p></p>


void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry e = table[bucketIndex]; //找到下標的entry
        //new 一個新的entry，賦值給當前下標數組
        table[bucketIndex] = new Entry(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }
Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n; //即將原來數組下標對應的entry賦值給新的entry的next
            key = k;
            hash = h;
        }
 

    （1）hash值相同且key相等數據將被覆蓋。 

    （2）添加新的entry時，將已存在的數據下標的entry（可能是null）賦值給新entry的next，新entry將替換原數組下標的值。 

HashMap的get方法源碼解析  


public V get(Object key) {
        //key為null時特別處理
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        //indexFor(hash, table.length) 根據hash值和數組長度計算出下標，然后遍歷Entry鏈表
        for (Entry 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時，必須覆蓋hashCode()和equals()方法，hashCode()的返回值盡可能的分散。 
當HashMap的entry的數組足夠大，key的hash值足夠分散時，即是可以實現一個entry數組下標最多只對應了一個entry，此時get方法的時間復雜度可以達到O(1)。 
在數組長度和get方法的速度上要達到一個平衡。數組比較長碰撞出現的概率就比較小，所以get方法獲取值時就比較快，但浪費了比較多的空間；當數組長度沒有冗余時，碰撞出現的概率比較大，雖然節省了空間，但會犧牲get方法的時間。 
HashMap有默認的裝載因子loadFactor=0.75，默認的entry數組的長度為16。裝載因子的意義在于使得entry數組有冗余，默認即允許25%的冗余，當HashMap的數據的個數超過12（16*0.75）時即會對entry數組進行第一次擴容，后面的再次擴容依次類推。 
HashMap每次擴容一倍，resize時會將已存在的值從新進行數組下標的計算，這個是比較浪費時間的。在平時使用中，如果能估計出大概的HashMap的容量，可以合理的設置裝載因子loadFactor和entry數組初始長度即可以避免resize操作，提高put的效率。 
HashMap不是線程安全的，多線程環境下可以使用Hashtable或ConcurrentHashMap。