什么是 HashMap(JDK 1.8)

本文基于 JDK 1.8邻吭。

HashMap 是用于存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)探遵，它根據(jù)鍵的 hashCode 值來存儲(chǔ)數(shù)據(jù)淌喻。遍歷順序是不確定的。最多只允許一條記錄的鍵為 null瞄摊，允許多條記錄的值為 null勋又。非線程安全，即任一時(shí)刻多個(gè)線程同時(shí)寫可能會(huì)導(dǎo)致數(shù)據(jù)的不一致换帜。

本文主要結(jié)合源碼楔壤，從存儲(chǔ)結(jié)構(gòu)、常用函數(shù)惯驼、擴(kuò)容機(jī)制以及安全性等方面深入講解 HashMap 的工作原理挺邀。

存儲(chǔ)結(jié)構(gòu)

我們先來看看 HashMap 的成員變量。

// 數(shù)組默認(rèn)大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
// 數(shù)組最大長度
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 鏈表轉(zhuǎn)紅黑樹邊界
static final int TREEIFY_THRESHOLD = 8;
// 紅黑樹轉(zhuǎn)離鏈表邊界
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希桶數(shù)組
transient Node<K,V>[] table;
// 實(shí)際存儲(chǔ)的元素個(gè)數(shù)
transient int size;
//  HashMap 結(jié)構(gòu)變化次數(shù)
transient int modCount;
// 閾值 = table.length * loadFactor跳座，能容納 node 的最大數(shù)量
int threshold;
// 負(fù)載因子
final float loadFactor;

由源碼可知，HashMap 中的所有鍵值對(duì)都是以 Node 的形式存放在一個(gè) Node 數(shù)組 table 中泣矛。來看看 Node 的結(jié)構(gòu)疲眷。

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

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {...}
    public final V setValue(V newValue) {...}
    public final boolean equals(Object o) {...}
}

Node 是 HashMap 的一個(gè) 內(nèi)部類，實(shí)現(xiàn)了 Map.Entry<K,V> 接口您朽。就是一個(gè)鍵值對(duì)狂丝。

從存儲(chǔ)結(jié)構(gòu)來講，HashMap 是基于數(shù)組+鏈表+紅黑樹來實(shí)現(xiàn)的哗总。下圖中的一個(gè)黑點(diǎn)就是一個(gè) Node 對(duì)象几颜。

hashMap內(nèi)存結(jié)構(gòu)圖.png

大家都知道 HashMap 采用鍵的 hashCode 值作為 key 然后通過 hash 函數(shù)（下文有介紹）得到數(shù)組索引下標(biāo)來確定對(duì)象的存儲(chǔ)位置，那么問題來了讯屈，再好的 hashCode 算法都有可能產(chǎn)生 hash 沖突蛋哭，那么如何解決沖突也是一大難題。HashMap 采用的是鏈地址法涮母，就是當(dāng)兩個(gè)對(duì)象的 hashCode 一樣時(shí)谆趾，就把該數(shù)組下標(biāo)對(duì)應(yīng)的對(duì)象變?yōu)殒湵碓暝浮?shù)組只存放鏈表的頭結(jié)點(diǎn)。當(dāng)鏈表長度過長時(shí)沪蓬，會(huì)增加遍歷的時(shí)間復(fù)雜度彤钟，JDK 1.8 對(duì)此做了優(yōu)化，當(dāng)鏈表長度大于 8 時(shí)跷叉，將鏈表轉(zhuǎn)換為紅黑樹逸雹，利用紅黑樹快速增刪改查的特點(diǎn)大大提高了遍歷效率。

所以如何設(shè)計(jì)一個(gè)盡量散列均勻的 hash 函數(shù)是關(guān)鍵 云挟，如果哈希桶數(shù)組比較大梆砸，那么不是很好的 hash 函數(shù)也會(huì)比較分散，如果哈希桶數(shù)組很小 植锉，即使再好的 hash 函數(shù)也會(huì)產(chǎn)生較多 hash 沖突辫樱。說白了就是在時(shí)間和空間上做權(quán)衡。結(jié)合自己的業(yè)務(wù)場景來確定 hash 數(shù)組的大小俊庇，并設(shè)計(jì)一個(gè)好的 hash 算法狮暑。

常用函數(shù)

  • 構(gòu)造函數(shù)
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

其中用的最多的是第一個(gè)參數(shù)為空的構(gòu)造方法。將 loadFactor 設(shè)置為默認(rèn)值辉饱。這里說一下第三個(gè)構(gòu)造方法搬男，前幾行都是檢驗(yàn)參數(shù)的正確性的，不多說彭沼，最后一行缔逛，設(shè)置 HashMap 的閾值。我們來看看 tableSizeFor 方法姓惑。

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

函數(shù)不長褐奴，但是咋一看不知道用來干啥的。其實(shí)這個(gè)函數(shù)是用來找到大于等于 cap 的最小的 2 的冪于毙。
我們來舉例說明敦冬。
如果 n 為零，那么經(jīng)過移位操作之后結(jié)果還是零唯沮，返回 n + 1 = 1 脖旱。
如果 n 為負(fù)數(shù)，那么無論如何移位操作最后結(jié)果肯定還是負(fù)數(shù)介蛉，所以返回 1萌庆。
如果 n 為正數(shù)，那么 n 的二進(jìn)制位中肯定有一位為 1币旧。我們暫且只考慮最高位的 1践险，因?yàn)槠渌坏?1 無影響。

無符號(hào)右移 1 位之后做按位或操作，使得 n 最高位后面的一位也為變成了 1捏境。注意這時(shí)候最高位有兩個(gè)連續(xù)的 1于游；

無符號(hào)右移 2 位之后做按位或操作，n 最高位兩個(gè)連續(xù)的 1 后面兩位也都成了 1垫言。注意這時(shí)候最高位有四個(gè)連續(xù)的 1贰剥；

無符號(hào)右移 4 位之后做按位或操作，n 最高位四個(gè)個(gè)連續(xù)的 1 后面四位也都成了 1筷频。注意這時(shí)候最高位有八個(gè)連續(xù)的 1蚌成；

無符號(hào)右移 8 位之后做按位或操作，n 最高位八個(gè)連續(xù)的 1 后面八位也都成了 1凛捏。注意這時(shí)候最高位有十六個(gè)個(gè)連續(xù)的 1担忧；

無符號(hào)右移 16 位之后做按位或操作，n 最高位十六個(gè)連續(xù)的 1 后面十六位也都成了 1坯癣。注意這時(shí)候最高位有三十二個(gè)連續(xù)的 1瓶盛；

所以這個(gè)函數(shù)就是把 n 最高位的 1 的后面所有位都變成了 1。然后這個(gè)值如果 >= MAXIMUM_CAPACITY 的話就返回 MAXIMUM_CAPACITY示罗；否則返回 n + 1惩猫。為什么是 n + 1 而不是 n 呢。你想想二進(jìn)制中那么多個(gè)連續(xù)的 1 在增加 1 后是不是會(huì)進(jìn)位得到一個(gè) 2 的冪的數(shù)蚜点。剛開始為什么要 cap - 1 呢轧房。這是因?yàn)槿绻?減去 1 的話，如果 cap 剛好是 2 的冪那么返回的結(jié)果就會(huì)變成 cap 的 2 倍绍绘。
這個(gè)函數(shù)寫的真是大贊吶奶镶！
最后返回的這個(gè)值賦給了 threshold。按道理來講應(yīng)該這么寫才對(duì)芭憔小厂镇！

 this.threshold = tableSizeFor(initialCapacity) * loadFactor ;

這樣子才符合 threshold 的意思呀。但是請(qǐng)注意左刽，在構(gòu)造函數(shù)中并沒有對(duì)哈希桶 table 初始化剪撬，初始化的過程放到了 put 函數(shù)中，并且該函數(shù)會(huì)對(duì) threshold 重新計(jì)算值悠反！

  • put 函數(shù)

HashMap put 過程可以用下圖來表示。

hashMap put方法執(zhí)行流程圖.png
  1. 判斷鍵值對(duì)數(shù)組 table 是否為 null馍佑，是則執(zhí)行 resize() 進(jìn)行擴(kuò)容斋否；
  2. 根據(jù)鍵值 key 計(jì)算 hash 值得到插入的數(shù)組索引 i，如果 table[i]== null拭荤，直接新建節(jié)點(diǎn)插入茵臭，轉(zhuǎn)向 6，如果 table[i] 不為 null舅世，轉(zhuǎn)向下一步旦委；
  3. 判斷 table[i] 的首個(gè)元素的 key 是否和當(dāng)前 key 相同奇徒，如果相同直接覆蓋 value 并轉(zhuǎn)向 6，否則轉(zhuǎn)向下一步缨硝。
  4. 判斷 table[i] 是否為 treeNode摩钙，如果是紅黑樹，則直接在樹中插入鍵值對(duì)并轉(zhuǎn)向 6查辩，否則轉(zhuǎn)向下一步胖笛。
  5. 遍歷 table[i]，判斷鏈表長度是否大于 8宜岛，大于 8 的話把鏈表轉(zhuǎn)換為紅黑樹长踊，在紅黑樹中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作萍倡；遍歷過程中若發(fā)現(xiàn) key 已經(jīng)存在直接覆蓋 value 即可身弊；
  6. 插入成功后，判斷實(shí)際存在的鍵值對(duì)數(shù)量 size 是否超多了最大容量 threshold列敲，如果超過阱佛，進(jìn)行擴(kuò)容。

注意：上面 3 說的 key 相同指的是 hashCode 和 equals 均相同

put 函數(shù)源碼如下：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab 為空酿炸，則創(chuàng)建新的數(shù)組
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 該索引處沒有 node瘫絮，直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // key 存在，直接覆蓋
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 紅黑樹直接插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 遍歷鏈表
            for (int binCount = 0; ; ++binCount) {
                // 到達(dá)鏈表末尾
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 鏈表長度大于 8填硕，轉(zhuǎn)換為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key 存在麦萤，直接覆蓋
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // e 不為空說明在哈希桶中找到了對(duì)應(yīng)的節(jié)點(diǎn)，返回節(jié)點(diǎn) value 即可扁眯。
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 操作次數(shù) + 1
    ++modCount;
    // 容量 + 1壮莹，如果超過最大容量則擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

注意 put 函數(shù)拿到 key 的 hash 值之后時(shí)通過 (n - 1) & hash來確定索引位置的，因?yàn)?HashMap 的數(shù)組大小總為 2 的冪姻檀，所以 (n - 1) & hash 相當(dāng)于 n % hash命满。因?yàn)槲贿\(yùn)算效率比較高，這里是 HashMap 做的優(yōu)化绣版，所以 HashMap 限制哈希桶數(shù)組的大小為 2 的冪胶台。另外 put 函數(shù)中還有一個(gè) hash 函數(shù)，用以計(jì)算 key 的 hash 值杂抽。源碼如下诈唬。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

大家想想為啥不直接用 hashCode 作為值呢。主要有兩方面的考慮缩麸，其一一是防止開發(fā)人員重寫 hashCoder 函數(shù)時(shí)性能不是很好铸磅，散列不夠均勻；其二是預(yù)防數(shù)組比較小時(shí)，散列比較均勻阅仔。
例如：HashMap 初始化時(shí)默認(rèn)數(shù)組大小為 16吹散。兩個(gè)不同的 key 的 hashCode 即使相差很大，但如果最后四位二進(jìn)制相同的話得出的數(shù)組下標(biāo)也是相同的八酒，這很明顯不是我們想要的結(jié)果空民。

直接獲取hashCode.png

但是如 JDK 1.8 所寫，加入了高位運(yùn)算結(jié)果就迥然不同了丘跌。

高位參與運(yùn)算.png
  • get 函數(shù)

HashMap 的查找操作比較簡單袭景，過程可以用下圖來表示。

hashMap get 方法執(zhí)行流程圖.png
  1. 定位到鍵所在的數(shù)組的下標(biāo)闭树，并獲取對(duì)應(yīng)節(jié)點(diǎn) n耸棒。
  2. n 是否為 null，如果是則返回 null 并結(jié)束报辱。否則轉(zhuǎn)至下一步与殃。
  3. 判斷 n 的 key 和要查找的 key 的是否相同，如果相同則返回 n 并結(jié)束碍现。否則轉(zhuǎn)至下一步幅疼。
  4. 判斷是否有后續(xù)節(jié)點(diǎn) m，如果沒有則結(jié)束昼接。否則轉(zhuǎn)至下一步爽篷。
  5. m 是否為紅黑樹，是則遍歷紅黑樹慢睡，如果存在某一個(gè)節(jié)點(diǎn)的 key 與要找的 key 相同則返回該節(jié)點(diǎn)逐工，否則返回 null。如果不是紅黑樹轉(zhuǎn)至下一步漂辐。
  6. 遍歷鏈表泪喊，如果存在某一個(gè)節(jié)點(diǎn)的 key 與要找的 key 相同則返回該節(jié)點(diǎn)，否則返回 null髓涯。

注意：上面說的 key 相同指的是 hashCode 和 equals 均相同

get 函數(shù)源碼如下：

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 定位 hash 值所在的數(shù)組的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果 key 和哈希桶中的 key 相同（hashCode 和 equals）直接返回
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果有后續(xù)節(jié)點(diǎn)
        if ((e = first.next) != null) {
            // 紅黑樹
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 鏈表
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

擴(kuò)容機(jī)制

當(dāng) HashMap 里面的元素個(gè)數(shù)超過閾值時(shí)就要擴(kuò)容了袒啼，不然容易影響性能。但是數(shù)組是無法自動(dòng)擴(kuò)容的纬纪，像 ArrayList 一樣蚓再，需要申請(qǐng)一個(gè)新的數(shù)組，HashMap 是申請(qǐng)了一個(gè)原來容量大小 2 倍的數(shù)組包各。然后遍歷舊數(shù)組对途，重新計(jì)算每一個(gè)元素的索引位置，復(fù)制到新數(shù)組中去髓棋。這里也算是一個(gè)優(yōu)化，因?yàn)?HashMap 的哈希桶數(shù)組大小總是為 2 的冪。所以重新計(jì)算的索引位置要么還是在原來的位置不變按声，要么是原來的位置 + 舊數(shù)組長度膳犹。

看下面的例子就明白了。其中 n 為 table 的默認(rèn)長度 16签则，圖（a）表示擴(kuò)容前的 key1 和 key2 兩個(gè) key 確定索引位置的示例须床；圖（b）表示擴(kuò)容后 key1 和 key2 兩種 key 確定索引位置的示例，其中 hash1 和 hash2 分是 key1 與 key2 對(duì)應(yīng)的哈希與高位運(yùn)算結(jié)果渐裂。

hashMap 1.8 哈希算法例圖1.png

因?yàn)?n 變?yōu)榱嗽瓉淼?2 倍豺旬，所以 n - 1 會(huì)比原來多一個(gè)最高位的 1.所以 index 才會(huì)發(fā)生這樣的變化。

hash 原數(shù)組大小 原下標(biāo) 新數(shù)組大小 新下標(biāo)
0 0101 1111 0 0101 1 1111 0 0101 = 5
1 0101 1111 0 0101 1 1111 1 0101 = 21 = 16 + 5

所以柒凉，我們?cè)趶?fù)制數(shù)組元素確定索引位置時(shí)不需要重新計(jì)算 hash 值族阅。只需要看元素 e.hash & oldCap 的值是 0 還是 1 即可。如果是 0 則原位置不動(dòng)膝捞，如果是 1 則新位置 = 原位置 + oldCap坦刀。這個(gè)設(shè)計(jì)真的很贊，因?yàn)?code>e.hash & oldCap的值為 0 或 1可以認(rèn)為是隨機(jī)的蔬咬，因此在擴(kuò)容過程中鲤遥，均勻的把之前有沖突的節(jié)點(diǎn)分散到新的位置。并且順序不會(huì)顛倒林艘。也就是說擴(kuò)容前如果元素 A 和元素 B 均在下標(biāo)為 10 的位置盖奈，A 比 B 靠前。擴(kuò)容后如果兩元素的下標(biāo)沒有變化狐援，那么 A 還是會(huì)比 B 靠前钢坦。 「據(jù)說 JDK1.7 會(huì)顛倒原來的順序，我沒有驗(yàn)證」

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { // 哈希桶不為空咕村，擴(kuò)容時(shí)走這個(gè)分支场钉。分支 A
        if (oldCap >= MAXIMUM_CAPACITY) { // 容量超過最大值，無法擴(kuò)容懈涛，擴(kuò)大閾值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新的哈希桶擴(kuò)容至原來的 2 倍逛万，閾值也擴(kuò)容至原來的 2 倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) 
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // 調(diào)用非空構(gòu)造函數(shù)時(shí)走這個(gè)分支。分支 B
        newCap = oldThr;
    else { // oldCap == oldThr == 0
           // 調(diào)用空的構(gòu)造函數(shù)時(shí)走這個(gè)分支批钠，使用默認(rèn)大小和閾值初始化哈希桶宇植。分支 C
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 只有走分支 B 的時(shí)候 newThr 才為零。
    // 因?yàn)檎{(diào)用非空構(gòu)造函數(shù)時(shí)直接把容量大小賦值給了閾值埋心，所以這里要計(jì)算新的閾值指郁。
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        // 創(chuàng)建新的哈希桶
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 擴(kuò)容時(shí)走這個(gè)分支
    if (oldTab != null) {
        // 把每個(gè) node 移動(dòng)到新的數(shù)組中去
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 沒有后繼節(jié)點(diǎn)
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 紅黑樹
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 鏈表重組，并保持原來的順序
                else {
                    /**
                    * loHead 指向新的 hash 在原位置的頭節(jié)點(diǎn)
                    * loTail 指向新的 hash 在原位置的尾節(jié)點(diǎn)
                    * hiHead 指向新的 hash 在原位置 + oldCap 位置的頭節(jié)點(diǎn)
                    * hiTail 指向新的 hash 在原位置 + oldCap 位置的尾節(jié)點(diǎn)
                    */
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原位置 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 新的 hash 在原位置的頭節(jié)點(diǎn)放入哈希桶
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 新的 hash 在原位置 + oldCap 位置的頭節(jié)點(diǎn)放入哈希桶
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

安全性

HashMap 的設(shè)計(jì)是簡潔高效拷呆，但沒有任何措施保證在 put 和 remove 過程中的線程安全闲坎。
先來看看 putVal 的部分源代碼疫粥。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        ......

假設(shè)現(xiàn)在哈希桶數(shù)組為空。

  1. 線程 A 開始執(zhí)行 put 操作腰懂。這時(shí)候 table == null 為真梗逮，執(zhí)行擴(kuò)容操作。之后掛起了绣溜。
  2. 線程 B 開始執(zhí)行慷彤，發(fā)現(xiàn)不需要擴(kuò)容，跳過怖喻。計(jì)算索引值底哗，假如得到的索引為 6，之后掛起了锚沸。
  3. 線程 A 開始執(zhí)行跋选，計(jì)算 hash 對(duì)應(yīng)的索引，剛好也為 6咒吐。此時(shí)因?yàn)榫€程 B 還沒有執(zhí)行賦值操作野建，所以該位置還是為空的，于是線程 A 把 "a" 放在了下標(biāo)為 6 的位置恬叹。之后刮起了候生。
  4. 線程 B 開始執(zhí)行，把 "b" 也放在了下標(biāo)為 6 的位置绽昼。

所以線程 B 的寫入操作覆蓋了線程 A 的寫入操作唯鸭，導(dǎo)致線程 A 的寫入操作數(shù)據(jù)丟失。

另外硅确，在 JDK1.7 的版本中目溉，在多線程下使用 HashMap 有可能造成環(huán)形鏈表。具體請(qǐng)參考美團(tuán)點(diǎn)評(píng)技術(shù)團(tuán)隊(duì)的博客：Java 8系列之重新認(rèn)識(shí) HashMap菱农。但這個(gè) bug 在 JDK 1.8 的版本中改進(jìn)了缭付。因?yàn)樵?JDK1.7 中采取的是頭插法，遍歷一個(gè)節(jié)點(diǎn)就插入一個(gè)節(jié)點(diǎn)到新的哈希桶數(shù)組循未，所以才會(huì)導(dǎo)致出現(xiàn)循環(huán)鏈表陷猫。但 JDK1.8 中是采用兩個(gè)頭結(jié)點(diǎn)來保持舊鏈表的引用，直到該索引處對(duì)應(yīng)的鏈表全部遍歷完之后再分別把頭結(jié)點(diǎn)放在新的哈希桶數(shù)組對(duì)應(yīng)的位置的妖。而不是遍歷一個(gè)節(jié)點(diǎn)就插入一個(gè)節(jié)點(diǎn)到新的哈希桶數(shù)組绣檬。所以不會(huì)出現(xiàn)死鏈。

總結(jié)：

  • 哈希桶的初始化長度默認(rèn)為 16嫂粟，負(fù)載因子默認(rèn)值是0.75娇未，threshold 是 HashMap 所能容納的最大數(shù)據(jù)量的 Node 個(gè)數(shù)。在數(shù)組定義好長度之后星虹，負(fù)載因子越大零抬，所能容納的 Node 個(gè)數(shù)越多镊讼。
  • 當(dāng) HashMap 中存儲(chǔ)的元素個(gè)數(shù)超過 threshold 是就重新 resize(擴(kuò)容)，擴(kuò)容后的容量是之前容量的兩倍平夜。默認(rèn)的負(fù)載因子 0.75 是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇狠毯，建議不要修改，除非在時(shí)間和空間比較特殊的情況下褥芒，如果內(nèi)存空間很多而又對(duì)時(shí)間效率要求很高，可以降低負(fù)載因的值嫡良；相反锰扶，如果內(nèi)存空間緊張而對(duì)時(shí)間效率要求不高烘挫，可以增加負(fù)載因子loadFactor的值清酥，這個(gè)值可以大于1。
  • size 指 HashMap 中實(shí)際存在的鍵值對(duì)數(shù)量溜在。注意和 table 的長度 length很澄、容納最大鍵值對(duì)數(shù)量 threshold 的區(qū)別京闰。
  • modCount 字段主要用來記錄 HashMap 內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)，主要用于迭代的快速失敗甩苛。強(qiáng)調(diào)一點(diǎn)蹂楣，內(nèi)部結(jié)構(gòu)發(fā)生變化指的是結(jié)構(gòu)發(fā)生變化，例如 put 新鍵值對(duì)讯蒲，但是某個(gè) key 對(duì)應(yīng)的 value 值被覆蓋不屬于結(jié)構(gòu)變化痊土。
  • HashMap 是線程不安全的。
  • 擴(kuò)容是比較耗費(fèi)資源的操作墨林。
  • 哈希桶的大小必須為 2 的冪赁酝。
  • JDK1.8 引入了紅黑樹的操作。優(yōu)化了性能旭等。

寫的很贊的地方

  • tableSizeFor 函數(shù)設(shè)計(jì)的很贊酌呆，利用移位操作來獲取大于等于 cap 的 最小的 2 的冪。
  • 把哈希桶的大小設(shè)計(jì)為 2 的 冪搔耕，用位運(yùn)算代替取模來確定索引位置隙袁。
  • 把哈希桶的大小設(shè)計(jì)為 2 的 冪，擴(kuò)容是不需要重新計(jì)算元素的 hash 值度迂。只需要看元素 e.hash & oldCap 的值是 0 還是 1 即可藤乙。而且可以認(rèn)為這個(gè)值是隨機(jī)的。
  • hash 函數(shù)加入 key 的高位加入運(yùn)算惭墓。使得 hash 值更均勻坛梁。

參考鏈接：Java 8系列之重新認(rèn)識(shí) HashMap

之前對(duì) HashMap 的理解僅限于知道怎么用，大概知道里面的實(shí)現(xiàn)原理腊凶，但源碼讀起來才知道這個(gè)寫的太贊了划咐。從讀源碼拴念，到理解，然后寫出來褐缠，前前后后大概花了四個(gè)晚上的時(shí)間政鼠，如有不對(duì)之處還請(qǐng)大家指教。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末队魏，一起剝皮案震驚了整個(gè)濱河市公般，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌胡桨，老刑警劉巖官帘，帶你破解...
    沈念sama閱讀 219,539評(píng)論 6贊 508
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異昧谊，居然都是意外死亡刽虹，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,594評(píng)論 3贊 396
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門呢诬，熙熙樓的掌柜王于貴愁眉苦臉地迎上來涌哲，“玉大人，你說我怎么就攤上這事尚镰》Щ” “怎么了？”我有些...
    開封第一講書人閱讀 165,871評(píng)論 0贊 356
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵钓猬，是天一觀的道長稍刀。 經(jīng)常有香客問我，道長敞曹，這世上最難降的妖魔是什么账月？ 我笑而不...
    開封第一講書人閱讀 58,963評(píng)論 1贊 295
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮澳迫，結(jié)果婚禮上局齿，老公的妹妹穿的比我還像新娘。我一直安慰自己橄登，他們只是感情好抓歼，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,984評(píng)論 6贊 393
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著拢锹，像睡著了一般谣妻。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上卒稳，一...
    開封第一講書人閱讀 51,763評(píng)論 1贊 307
  • 城市分裂傳說
    那天蹋半，我揣著相機(jī)與錄音，去河邊找鬼充坑。 笑死减江，一個(gè)胖子當(dāng)著我的面吹牛染突，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播辈灼，決...
    沈念sama閱讀 40,468評(píng)論 3贊 420
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼份企，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了巡莹？” 一聲冷哼從身側(cè)響起司志，我...
    開封第一講書人閱讀 39,357評(píng)論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎降宅，沒想到半個(gè)月后俐芯，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,850評(píng)論 1贊 317
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡钉鸯，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,002評(píng)論 3贊 338
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了邮辽。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片唠雕。...
    茶點(diǎn)故事閱讀 40,144評(píng)論 1贊 351
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖吨述，靈堂內(nèi)的尸體忽然破棺而出岩睁，到底是詐尸還是另有隱情，我是刑警寧澤揣云，帶...
    沈念sama閱讀 35,823評(píng)論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布捕儒，位于F島的核電站，受9級(jí)特大地震影響邓夕，放射性物質(zhì)發(fā)生泄漏刘莹。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,483評(píng)論 3贊 331
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一焚刚、第九天 我趴在偏房一處隱蔽的房頂上張望点弯。 院中可真熱鬧，春花似錦矿咕、人聲如沸抢肛。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,026評(píng)論 0贊 22
  • 一樁弒父案碳柱，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽捡絮。三九已至，卻和暖如春莲镣，著一層夾襖步出監(jiān)牢的瞬間福稳，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,150評(píng)論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來泰國打工剥悟， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留灵寺，地道東北人曼库。 一個(gè)月前我還...
    沈念sama閱讀 48,415評(píng)論 3贊 373
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像略板，于是被迫代替她去往敵國和親毁枯。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,092評(píng)論 2贊 355