HashMap源碼閱讀

HashMap是什么想必大家都是知道的,日常開發中經常使用,而且常駐于筆試題目及面試中,那么今天將從源碼的角度來深入理解一下HashMap。

PS:本文以下分析基于jdk1.7,1.8的改動會在文后總結

1.什么是HashMap?

HashMap是基于哈希表的Map接口實現,是一個key-value型的數據結構。他在性能良好的情況下,存取的時間復雜度皆為O(1).

要知道數組的獲取時間復雜度為O(1),但是他的插入時間復雜度為O(n).

那么HashMap是怎么做到的呢?

看一下HashMap的屬性:

//內部數組的默認初始容量,作為hashmap的初始容量,是2的4次方,2的n次方的作用是減少hash沖突
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 //默認的最大容量
 static final int MAXIMUM_CAPACITY = 1 << 30;

 //默認負載因子,當容器使用率達到這個75%的時候就擴容
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 /**
  *當數組表還沒擴容的時候,一個共享的空表對象
  */
 static final Entry<?,?>[] EMPTY_TABLE = {};

 //內部數組表,用來裝entry,大小只能是2的n次方。
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

 //存儲的鍵值對的個數
 transient int size;

 /**
  * 擴容的臨界點,如果當前容量達到該值,則需要擴容了。
  * 如果當前數組容量為0時(空數組),則該值作為初始化內部數組的初始容量
  */
 int threshold;

 //由構造函數傳入的指定負載因子
 final float loadFactor;

 //Hash的修改次數
 transient int modCount;

 //threshold的最大值
 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

 //計算hash值時候用,初始是0
 transient int hashSeed = 0;

 //含有所有entry節點的一個set集合
 private transient Set<Map.Entry<K,V>> entrySet = null;

 private static final long serialVersionUID = 362498820763181265L;
復制代碼

注釋已經比較完備,便不再做過多的說明。

由里面的

HashMap源碼閱讀

可以看出,HashMap的主體其實是個數組,是Entry這個內部類的數組。

Entry內部類是啥呢?

HashMap源碼閱讀

這是Entry內部類的屬性,可以看出這是個單鏈表的節點,因為它內部有指向下一個節點的next。

那么就相當明了了,HashMap內部是一個數組,數組的每一個節點是一個鏈表的頭結點,也就是拉鏈式。

2.HashMap具體是怎么做到的

對于HashMap來說,日常使用的就是兩個方法, get() , put() .

我們首先看 put .

public V put(K key, V value) {

    //判斷當前HashMap是否為空,為空則初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //判斷傳入的key是否為null,為null則放到table[0]的位置或者其鏈表上
    if (key == null)
        return putForNullKey(value);

     //計算key的hash值      
    int hash = hash(key);
    //計算key存放在數組中的下標
    int i = indexFor(hash, table.length);
    //遍歷該位置上的鏈表,如果存在key值和傳入的key值相等,則替換掉舊值
    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++;
    //如果沒有這個值,則添加一個Entry
    addEntry(hash, key, value, i);
    return null;
}
/**
 * Offloaded version of put for null keys
 */
private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
     //判斷是否需要擴容,是的話進行擴容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    //新建一個Entry
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    //將傳入的key-value放在鏈表的頭部,并且指向原鏈表的頭。
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

復制代碼

代碼中添加了一些注釋,大概是可以看懂的,那么這里總結一下流程。

  1. 判斷當前hashMap是否為空,為空則初始化。
  2. 判斷傳入的key是否為null,為null的話直接放到數組的0位置或者0位置的鏈表上。
  3. key不為空,計算key的hash值。
  4. 計算key在數組中應該存儲的下標
  5. 遍歷數組在該下標的鏈表,如果找到已經存在的key和傳入的key相等,則用新的value替換舊的value。
  6. 沒找到,則在數組的i位置添加一個Entry。
  7. 添加Entry時,先判斷是否需要擴容,需要的話擴容,不需要的話下一步。
  8. 創建一個Entry,創建的方法是將新傳入的key-value放在數組i位置的鏈表頭結點,并且指向原鏈表頭結點。

接下來是 get() 方法。

public V get(Object key) {
    //key為null,則在數組0位置尋找值
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

final Entry<K,V> getEntry(Object key) {
    //如果hashMap中存的值數量為0,則返回null
    if (size == 0) {
        return null;
    }
    //計算key的hash值
    int hash = (key == null) ? 0 : hash(key);

    //用indexof函數算出數組下標
    //在該下標位置上的鏈表中遍歷,尋找與傳入key相等的key,否則返回null
    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 != null && key.equals(k))))
            return e;
    }
    return null;
}

復制代碼

同樣這里總結一下流程:

  1. 判斷key==null,如果為null,在數組0位置尋找。
  2. key!=null,判斷hashMap中存的值數量是否為0,如果為0直接返回null。
  3. 計算key的hash值。
  4. 計算key應該在數組中的下標。
  5. 遍歷Entry數組在該位置的鏈表,尋找與傳入key相等的key,并返回值,如果遍歷結束找不到,則返回null。

hash()方法和indexOf()方法

大家可能注意到了,在 get()put() 方法的實現中,都使用到了這兩個方法,那么這里看一下源碼:

//通過一系列復雜的計算拿到一個int類型的hash值
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

/**
* Returns index for hash code h.
*/
//將hash值和數組長度與,結果等同于hash%length,拿到數組下標
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

復制代碼

這里重點是:indexOf()方法,將hash值和數組長度 ,結果等同于hash%length,拿到數組下標。

結果等同于取模法,但是運算過程更加快速。這里有一個重要的知識點,后續會說噢。

resize()方法

put() 方法及其調用的方法中,當在數組上新添加一個節點時,會判斷當前是否需要擴容,怎么判斷的呢?

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
復制代碼

可以看到,當當前已經存儲值得size大于閥值,則將數組擴容為原來的兩倍。

閥值threshold怎么計算呢?容量 * 負載因子。即 capacity * loadFactory

擴容的方法為:

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];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

復制代碼

新建一個容量為原來兩倍的數組,然后將舊數組中的值,rehash之后重新放入新數組,以保證散列均勻。

rehash這個操作是比較費時間的,總的來說擴容操作就比較費時間,因為需要將舊的值移動到新的數組中,因此如果在使用前能預估數量,盡量使用帶有參數構造方法,指定初始容量,盡量避免過多的擴容操作

remove()方法

差點忘記remove()方法了。。

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    /**
     * Removes and returns the entry associated with the specified key
     * in the HashMap.  Returns null if the HashMap contains no mapping
     * for this key.
     */
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        //計算hash
        int hash = (key == null) ? 0 : hash(key);
        //計算下標
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

復制代碼

具體的實現思路也是一樣的:首先計算hash繼而計算下標,然后遍歷數組在該位置的鏈表,找到該key-value然后將其移除掉。

3.HashMap的一些為什么?

3.1.為什么擴容的閥值在 capacity * loadFactory ?

首先了解一下

  1. capacity是指容量,數組最大的容量
  2. loadfactory是指負載因子,是形容當前數組裝的有多滿的一個值。默認為0.75.也就是如果初始capacity為16,那么當不發生hash碰撞,也就是沒有用到鏈表結構時,寫入12個元素即會擴容了。
  3. 數組在性能上是比鏈表優秀的(在HashMap中,數組可以存null,不用進行值的移位)。
  4. HashMap的數據結構,導致即使容量只有16,也可以存儲32(還可以更多)個值,只需要每個位置上的鏈表多鏈幾個節點就好了。

因此可以發現,HashMap的性能問題又來到了時間和空間的取舍上,當你不擴容,仍然可以存儲,只是由于鏈表的變長,性能下降。當你進行太多的擴容,hash碰撞減少,鏈表長度統一減少,性能提高了但是浪費的空間又多了。0.75這個值是開發者定義的一個對時間空間的折中值。

3.2.性能極限的情況

當存入的值越來越多,卻不擴容,HashMap性能就會下降,那么我們極限一點。

HashMap的容量只有1,存入了100個值。由上面的分析可知,這時候HashMap退化成了單鏈表,存取得時間復雜度都是O(n)。

HashMap的容量為16,存入一個值,在存入第二個值,立即擴容,這樣可以盡量的避免hash碰撞,避免產生鏈表,存取時間復雜度都為O(1).

因此,當你對存取速度要求很高,可以適當調低loadfactory,當你當前對速度無所謂,但是內存很小,可是調大loadfactory,當然大部分時候默認值0.75都是一個不錯的選擇。

loadfactory的值為:0.75,2,4等數字都是合法值

3.3.為什么HashMap的容量永遠是2的次冪?

看過上面的代碼我們可以發現,HashMap的初始容量為16,擴容為原容量乘以2。

也就是說,HashMap的容量永遠是2的次冪,這是為什么呢?

想一想哪里使用到了容量這個參數呢?

在拿到key的hash值,計算當前key在數組中的下標的時候,運用了如下的方法進行計算:

HashMap源碼閱讀

真實的length為16,我們假設一個假的lengthWrong = 15;

同時我們有兩個key,hash之后拿到的hash=8,和hash=9;

length – 1 二進制 8 & length – 1 9 & length- 1
15 1111 1000 & 1111 = 1000 = 8 1001 & 1111 = 1001 = 9
14 1110 1000 & 1110 = 1000 = 8 1001 & 1110 = 1000 = 8

可以看到當長度為15時,當h = 8,h =9 h & length - 1 拿到的結果一樣都為8,也就是這兩個key都存在數組中下標為8的鏈表上。這是為什么呢?

當length為偶數時,length- 1位奇數,奇數的二進制最后一位必然為1,而當length = 奇數時,length – 1位偶數,偶數的二進制最后一位為0.

二進制與運算有如下規則:

1 & 任意 = 任意;
0 & 任意 = 0;
復制代碼

也就是說,當length = 16時,計算的下標可以為1-16任意數字,而當length=15時,計算的下標只能為2,4,6,8 等等偶數,這樣就浪費了一般的存儲空間,同時還增大了hash碰撞的概率,使得HashMap的性能變差。

因此length必須為偶數,而length為2的次冪不僅能保證為偶數,還可以實現 h & length - 1 = h % length ,可謂是一舉兩得了。666啊。

擴展(Java8 的hashMap有哪些改進?)

在3.2中提到,當極限情況下HashMap會退化成鏈表,存取時間復雜度變為O(n),這顯然是不能接受的,因此在java8中對這一點做了優化。

在java7中,存儲在數組上的是一個鏈表的頭結點,當哈希碰撞之后,不斷的增長鏈表的長度,這會導致性能下降。在java8中,引入了紅黑樹數據結構,當鏈表長度小于8時,仍然使用鏈表存儲,而當長度大于8時,會將鏈表轉化為紅黑樹。同時,當樹的節點數小于6時,會從紅黑樹變成鏈表。

這樣改進之后,即使在性能最差的情況下,hashMap的存取時間復雜仍為O(logn).

而紅黑樹的具體實現,這里不再詳細敘述,這屬于數據結構的范圍了,在HashMap中展開不合適。

ChangeLog

2018-10-17 完成

以上皆為個人所思所得,如有錯誤歡迎評論區指正。

歡迎轉載,煩請署名并保留原文鏈接。

聯系郵箱:[email protected]mail.com

更多學習筆記見個人博客——>呼延十

原文 

https://juejin.im/post/5cff49c16fb9a07eec59c085

本站部分文章源于互聯網,本著傳播知識、有益學習和研究的目的進行的轉載,為網友免費提供。如有著作權人或出版方提出異議,本站將立即刪除。如果您對文章轉載有任何疑問請告之我們,以便我們及時糾正。

PS:推薦一個微信公眾號: askHarries 或者qq群:474807195,里面會分享一些資深架構師錄制的視頻錄像:有Spring,MyBatis,Netty源碼分析,高并發、高性能、分布式、微服務架構的原理,JVM性能優化這些成為架構師必備的知識體系。還能領取免費的學習資源,目前受益良多

轉載請注明原文出處:Harries Blog? » HashMap源碼閱讀

贊 (0)
分享到:更多 ()

評論 0

  • 昵稱 (必填)
  • 郵箱 (必填)
  • 網址
2013平特肖公式