HashMap源碼剖析

一本正經(jīng)地胡鬧 2019-09-03

展開全文

本文來自：我的博客，原文地址：https://blog.csdn.net/silentljh/article/details/80444216，轉(zhuǎn)載請注明。

HashMap可以說是Java中最常用的集合類框架之一，是Java語言中非常典型的數(shù)據(jù)結(jié)構(gòu)，我們總會在不經(jīng)意間用到它，很大程度上方便了我們?nèi)粘ｉ_發(fā)。

注：以下分析全部基于JDK1.7，不同版本之間會有較大的改動，讀者需要注意。

HashMap概述

HashMap是一種基于哈希表實現(xiàn)的Map，它通過鍵的hashCode來快速的存取元素
HashMap允許插入null鍵和null值，允許多條記錄的值為null，但只允許一條記錄的鍵為null
HashMap不是線程安全的，在并發(fā)環(huán)境下，可能會引起死循環(huán)
HashMap中的元素是無序的，無法保證遍歷時的順序是固定不變的
HashMap在不考慮哈希碰撞的情況下，插入和查詢的時間復(fù)雜度可以達到O(1)

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

HashMap是基于哈希表實現(xiàn)的，哈希表是由數(shù)組和鏈表共同構(gòu)成的一種結(jié)構(gòu)，其中數(shù)組保存著每個單向鏈表的頭結(jié)點，鏈表保存著具有相同hash值的不同元素，它是用來解決哈希沖突(Hash Collision)的。一個好的哈希函數(shù)應(yīng)該盡量使元素在數(shù)組中均勻分布，減少哈希沖突，從而縮短鏈表的長度。鏈表的長度越長，意味著在查找時需要遍歷的結(jié)點越多，哈希表的性能也就越差。

HashMap中的數(shù)組是一個Entry數(shù)組，數(shù)組存放的每個Entry都是單向鏈表的頭結(jié)點。HashMap使用Entry類來表示Key-Value型的元素，一個Entry對象就是一個鍵值對，里面包含了key，value，hash值以及指向下一個Entry對象的引用。

static class Entry<K, V> implements Map.Entry<K, V> {
    final K key;
    V value;
    Entry<K, V> next;    // 下一個Entry對象的引用
    int hash;            // 元素的hash, 其實就是key的hash值   
｝

HashMap源碼剖析

1、常量和屬性解析

// 默認初始化容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap允許的最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認的負載率 75%
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 空的哈希表
static final Entry<?, ?>[] EMPTY_TABLE = {};
// 實際使用的哈希表
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
// HashMap的大小,即存儲的key-value的數(shù)量
transient int size;
// 擴容的閥值，當(dāng)HashMap的size達到閥值時，就開始擴容 threshold=length*threshold 
int threshold;
// 負載率
final float loadFactor;
// 修改次數(shù), 用于fail-fast機制
transient int modCount;
// 替代哈希使用的默認擴容閥值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
// 隨機的哈希種子, 有助于減少發(fā)生哈希碰撞的幾率
transient int hashSeed = 0;

2、構(gòu)造方法

HashMap提供了一下4種構(gòu)造方法, 但最終都會調(diào)用HashMap(int initialCapacity, float loadFactor)方法。如果使用無參構(gòu)造函數(shù)創(chuàng)建HashMap，其內(nèi)部是通過調(diào)用HashMap(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR)實現(xiàn)。下面我們來分析一下這個構(gòu)造方法。

public HashMap(int initialCapacity, float loadFactor) {
    // 如果初始容量小于0，則拋出異常
    if (initialCapacity < 0) {
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    }
    // 如果初始容量大于容量最大值，則使用最大值作為初始容量
    if (initialCapacity > MAXIMUM_CAPACITY) { initialCapacity = MAXIMUM_CAPACITY; }
    // 如果負載率小于等于0或負載率不是浮點數(shù)，則拋出異常
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    }
    // 設(shè)置負載率
    this.loadFactor = loadFactor;
    // 設(shè)置閥值為初始容量
    threshold = initialCapacity;
    // 空實現(xiàn), 交由子類實現(xiàn)
    init();
}

看完這個方法，我們發(fā)現(xiàn)這個構(gòu)造方法并沒有根據(jù)傳入的initialCapacity去新建一個Entry數(shù)組，此時的哈希表依然是一個空表。HashMap在構(gòu)造時不會新建Entry數(shù)組，而是在put操作時會先檢查當(dāng)前哈希表是否是個空表，如果是空表就調(diào)用inflateTable方法進行初始化。上面貼出了這個方法的代碼，可以看到方法內(nèi)部會重新計算Entry數(shù)組的容量，因為在構(gòu)造HashMap時傳入的初始化大小可能不是2的冪，因此要將這個數(shù)轉(zhuǎn)換成2的冪再去根據(jù)新的容量新建Entry數(shù)組。初始化哈希表時再次重新設(shè)置閥值，閥值一般是capacity*loadFactor。此外，在初始化哈希表時還會去初始化hashSeed，這個hashSeed用于優(yōu)化哈希函數(shù)，默認為0是不使用替代哈希算法，但是也可以自己去設(shè)置hashSeed的值，以達到優(yōu)化效果。具體下面會講到。

3、put方法

public V put(K key, V value) {
    // 如果哈希表沒有初始化就進行初始化
    if (table == EMPTY_TABLE) {
        // 初始化哈希表
        inflateTable(threshold);
    }
    // 當(dāng)key為null時，調(diào)用putForNullKey方法，保存null于table的第一個位置中，這是HashMap允許為null的原因
    if (key == null) {
        return putForNullKey(value);
    }
    // 計算key的hash值
    int hash = hash(key);
    // 根據(jù)key的hash值和數(shù)組的長度定位到entry數(shù)組的指定槽位
    int i = indexFor(hash, table.length);
    // 獲取存放位置上的entry，如果該entry不為空，則遍歷該entry所在的鏈表
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 通過key的hashCode和equals方法判斷，key是否存在， 如果存在則用新的value取代舊的value，并返回舊的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 修改次數(shù)增加1
    modCount++;
    // 如果找不到鏈表 或者 遍歷完鏈表后，發(fā)現(xiàn)key不存在，則創(chuàng)建一個新的Entry，并添加到HashMap中
    addEntry(hash, key, value, i);
    return null;
}

put方法執(zhí)行流程:

檢查哈希表是否是個空表，如果是空表就調(diào)用inflateTable方法進行初始化
判斷key是否為null，如果為null，就調(diào)用putForNullKey方法, 將key為null的key-value存儲在哈希表的第一個位置中
如果key不為null，則調(diào)用hash方法計算key的hash值
根據(jù)hash值和Entry數(shù)組的長度定位到Entry數(shù)組的指定槽位i
判斷Entry數(shù)組指定槽位的值e是否為null, 如果e不為null, 則遍歷e指向的單鏈表, 如果傳入的key在單鏈表中已經(jīng)存在了, 就進行替換操作, 否則就新建一個Entry并添加到單鏈表的表頭位置
如果e為null, 就新建一個Entry并添加到指定槽位

從put方法的執(zhí)行流程我們發(fā)現(xiàn), 在發(fā)生哈希碰撞的情況下, 插入key-value會遍歷指定槽位的單鏈表, 如果key已經(jīng)存在于單鏈表中了, 就會用value覆蓋舊的值, 如果key不存在, 則會將key-value插入單鏈表的表頭. 基于這個邏輯, put方法的算法復(fù)雜度就從O(1)變成了O(n), 因此優(yōu)化hash函數(shù), 減少哈希碰撞的發(fā)生, 就可以使得put方法的算法復(fù)雜度接近O(1).

4、get方法

public V get(Object key) {
    // 如果key為null，調(diào)用getForNullKey方法從entry數(shù)組第一個位置獲取key對應(yīng)的value
    if (key == null) {
        return getForNullKey();
    }
    Entry<K, V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}

final Entry<K, V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    // 計算hash值
    int hash = (key == null) ? 0 : hash(key);
    // 通過hash值和數(shù)組長度計算出Entry數(shù)組的指定槽位
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        // 通過hash值和equals判斷key是否存在，如果存在則返回對應(yīng)的value
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { return e; }
    }
    return null;
}

get方法執(zhí)行流程:

判斷key是否為null，如果為null，就調(diào)用getForNullKey方法, 從哈希表的第一個位置獲取
如果key不為null，調(diào)用hash方法計算key的Hash值
根據(jù)hash值和Entry數(shù)組的長度定位到Entry數(shù)組的指定槽位i
判斷Entry數(shù)組指定槽位的值e是否為null, 如果是則返回null
如果e不為null, 則遍歷e指向的單鏈表, 如果傳入的key在單鏈表中已經(jīng)存在了,

5、哈希表是如何初始化的?

private void inflateTable(int toSize) {
    // 尋找大于toSize的,最小的,2的n次方作為新的容量
    int capacity = roundUpToPowerOf2(toSize);
    // 閥值=容量*負載因子, 如果容量*負載因子>最大容量時, 閥值=最大容量
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 按新的容量創(chuàng)建一個新的數(shù)組
    table = new Entry[capacity];
    // 重新初始化hashSeed
    initHashSeedAsNeeded(capacity);
}

6、HashMap是如何通過key的hash值來定位到Entry數(shù)組的指定槽位的?(size為什么必須是2的整數(shù)次冪?)

static int indexFor(int h, int length) {
    // 對hash值和length-1進行與運算來計算索引
    return h & (length - 1);
}

indexFor方法是根據(jù)hash值和entry數(shù)組的長度來計算出在數(shù)組中對應(yīng)的下標(biāo)。我們可以看到在這個方法內(nèi)部使用了與(&)操作符。與操作是對兩個操作數(shù)進行位運算，如果對應(yīng)的兩個位都為1，結(jié)果才為1，否則為0。與操作經(jīng)常用于去除操作數(shù)的高位值，例如：01011010 & 00001111 = 00001010。我們繼續(xù)回到代碼中，看看h&(length-1)做了些什么。

已知傳入的length是Entry數(shù)組的長度，我們知道數(shù)組下標(biāo)是從0開始計算的，所以數(shù)組的最大下標(biāo)為length-1。如果length為2的冪，那么length-1的二進制位后面都為1。這時h&(length-1)的作用就是去掉了h的高位值，只留下h的低位值來作為數(shù)組的下標(biāo)，h的低位值肯定不會比length-1大，所以可以保證數(shù)組不會越界。由此可以看到Entry數(shù)組的大小規(guī)定為2的冪就是為了能夠使用這個算法來確定數(shù)組的下標(biāo)。

7、哈希函數(shù)是怎樣計算Hash值的？

final int hash(Object k) {
    int h = hashSeed;
    // 如果hashSeed不為0且key是字符串對象,則調(diào)用系統(tǒng)內(nèi)部提供的hash算法計算hash值
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    // 擾動函數(shù)
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

hash方法的最后兩行是真正計算hash值的算法，計算hash值的算法被稱為擾動函數(shù)，所謂的擾動函數(shù)就是把所有東西雜糅到一起，可以看到這里使用了四個向右移位運算。目的就是將h的高位值與低位值混合一下，以此增加低位值的隨機性。在上面我們知道定位數(shù)組的下標(biāo)是根據(jù)hash值的低位值來確定的。key的hash值是通過hashCode方法來生成的，而一個糟糕的hashCode方法生成的hash值的低位值可能會有很大的重復(fù)。為了使得hash值在數(shù)組上映射的比較均勻，擾動函數(shù)就派上用場了，把高位值的特性糅合進低位值，增加低位值的隨機性，從而使散列分布的更加松散，以此提高性能。下圖舉了個例子幫助理解。

8、HashMap在什么時候判斷擴容？是怎么進行擴容的？

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果鍵值對的總數(shù)大于等于閥值，且當(dāng)前要插入的key-value沒有發(fā)生hash碰撞，則進行擴容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 擴容到原來容量的兩倍
        resize(2 * table.length);
        // 擴容后重新計算hash值
        hash = (null != key) ? hash(key) : 0;
        // 擴容后重新確定Entry數(shù)組的槽位
        bucketIndex = indexFor(hash, table.length);
    }
    // 創(chuàng)建一個Entry對象，并添加到Entry數(shù)組的指定位置中
    createEntry(hash, key, value, bucketIndex);
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 如果舊數(shù)組的長度已經(jīng)達到最大值，則不進行擴容，并將閥值設(shè)置為最大值
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 以新的長度創(chuàng)建一個新的數(shù)組
    Entry[] newTable = new Entry[newCapacity];
    // initHashSeedAsNeeded(newCapacity) 確定是否重新進行hash計算
    // 將舊數(shù)組中的元素逐個重新計算hash和index，然后全部轉(zhuǎn)移到新的數(shù)組中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    // 將閥值設(shè)置為新的容量*負載率
    threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

在調(diào)用put方法添加一個鍵值對時，如果集合中沒有存在的key就去調(diào)用addEntry方法新建一個Entry?？吹缴厦尜N出的addEntry代碼，在新建一個Entry之前會先判斷當(dāng)前集合元素的大小是否超過了閥值，如果超過了閥值就調(diào)用resize進行擴容。傳入的新的容量是原來哈希表的兩倍，在resize方法內(nèi)部會新建一個容量為原先的2倍的Entry數(shù)組。然后將舊的哈希表里面的元素全部遷移到新的哈希表，其中可能會對舊的元素重新進行哈希運算，根據(jù)initHashSeedAsNeeded方法計算的值來確定是否重新計算哈希。完成哈希表的遷移之后，將當(dāng)前哈希表替換為新的，最后再根據(jù)新的哈希表容量來重新計算HashMap的閥值。由此可見，HashMap的擴容操作時非常低效的，我們在創(chuàng)建HashMap對象時，可以先預(yù)估一下容量，然后指定一個初始容量，來減少擴容的頻率，提高程序運行的效率

9、替代哈希是怎么回事？

hash方法中首先會將hashSeed賦值給h。這個hashSeed就是哈希種子，它是一個隨機的值，作用就是幫助優(yōu)化哈希函數(shù)。hashSeed默認是0，也就是默認不使用替代哈希算法。那么什么時候使用hashSeed呢？首先需要設(shè)置開啟替代哈希，在系統(tǒng)屬性中設(shè)置jdk.map.althashing.threshold的值，在系統(tǒng)屬性中這個值默認是-1，當(dāng)它是-1的時候使用替代哈希的閥值為Integer.MAX_VALUE。這也意味著可能你永遠也不會使用替代哈希了。當(dāng)然你可以把這個閥值設(shè)小一點，這樣當(dāng)集合元素達到閥值后就會生成一個隨機的hashSeed，以此增加hash函數(shù)的隨機性。為什么要使用替代哈希呢？當(dāng)集合元素達到你設(shè)定的閥值之后，意味著哈希表已經(jīng)比較飽和了，出現(xiàn)哈希沖突的可能性就會大大增加，這時對再添加進來的元素使用更加隨機的散列函數(shù)能夠使后面添加進來的元素更加隨機的分布在散列表中。

10、Fail-Fast機制：

我們知道HashMap不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了map，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。這一策略在源碼中的實現(xiàn)是通過modCount域，modCount顧名思義就是修改次數(shù)，對HashMap內(nèi)容的修改都將增加這個值，那么在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount。

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;    // next entry to return
    int expectedModCount;    // For fast-fail
    int index;        // current slot
    Entry<K,V> current;    // current entry
    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }
    public final boolean hasNext() {
        return next != null;
    }
    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
        current = e;
        return e;
    }
    public void remove() {
        if (current == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Object k = current.key;
        current = null;
        HashMap.this.removeEntryForKey(k);
        expectedModCount = modCount;
    }
}

modCount是volatile變量，保證了線程之間修改的可見性。在迭代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了Map。

在HashMap的API中指出：

由所有HashMap類所返回的迭代器都是快速失敗的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對Map進行修改，除了通過迭代器本身的 remove 方法之外，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發(fā)的修改，迭代器很快就會完全失敗，而不承擔(dān)在將來不確定的時間發(fā)生任意不確定行為的風(fēng)險。

注意，迭代器的快速失敗行為不能得到保證，一般來說，存在非同步的并發(fā)修改時，不可能作出任何堅決的保證。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的做法是錯誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯誤

11、HashMap在并發(fā)環(huán)境下有可能會出現(xiàn)死循環(huán)是怎么回事？

HashMap是線程不安全的，如果被多個線程共享的操作，將會引發(fā)不可預(yù)知的問題，據(jù)sun的說法，在擴容時，會引起鏈表的閉環(huán)，在get元素時，就會無限循環(huán)，后果是cpu100%。

https:///articles/9606.html/comment-page-1

12、key為Null的鍵值對是如何存儲和查找的？

13、為什么HashMap常用String, Integer對象作為Key

14、如何正確使用HashMap?

a.不要在并發(fā)場景中使用HashMap，如果要使用，請換成CurrentHashMap

b.最好在初始化時，給HashMap設(shè)定一個合理的容量值

本文來自：我的博客，原文地址：https://blog.csdn.net/silentljh/article/details/80444216，轉(zhuǎn)載請注明。