HashMap部分源碼

hash算法

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

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

可以看到hash算法計(jì)算分為三步

1.獲得key的hash值
2.在1的基礎(chǔ)上右移16位拇颅，即保留低16位茫负，抹去高16位
3.1和2的結(jié)果進(jìn)行異或運(yùn)算（相同為0宝穗，不同為1）

hash()方法，只是key的hashCode的再散列洲尊，使key更加散列晓锻。而元素究竟存在哪個(gè)桶中。還是要看putVal方法中 (n - 1) & hash 結(jié)果決定的肩祥。

tableSizeFor方法

該方法作用是返回一個(gè)大于輸入?yún)?shù)且最小的為2的n次冪的數(shù)

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;
}

舉例：當(dāng)輸入為13的時(shí)候后室，n等于12，轉(zhuǎn)成二進(jìn)制為1100混狠，右移1位為0110岸霹，將1100與0110進(jìn)行或("|")操作，得到1110将饺。接下來右移兩位得11贡避，再進(jìn)行或操作得1111，接下來操作n的值就不會(huì)變化了予弧。最后返回的時(shí)候刮吧，返回n+1，也就是10000掖蛤，十進(jìn)制為16皇筛。按照這種邏輯得到2的n次冪的數(shù)。

分析算法：實(shí)現(xiàn)把從最高位開始第一個(gè)為1的位之后所有的位全部變成1坠七，此時(shí)返回n+1即可得到一個(gè)正好比原數(shù)大的最小的2的n次冪

還有一個(gè)問題水醋，為什么要在前面減1即 n = cap - 1？

減一是為了傳進(jìn)來的本身就是2的冪次方整數(shù)這種情況不減一會(huì)返回本身的兩倍彪置，減一返回本身

重要成員變量和函數(shù)

// 16 默認(rèn)初始容量（這個(gè)容量不是說map能裝多少個(gè)元素拄踪，而是桶的個(gè)數(shù)）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量值
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//樹化閾值 一個(gè)桶鏈表長(zhǎng)度超過 8 進(jìn)行樹化
static final int TREEIFY_THRESHOLD = 8;
//鏈表化閾值 一個(gè)桶中紅黑樹元素少于 6 從紅黑樹變成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//最小樹化容量，當(dāng)容量未達(dá)到64拳魁，即使鏈表長(zhǎng)度>8惶桐，也不會(huì)樹化，而是進(jìn)行擴(kuò)容。
static final int MIN_TREEIFY_CAPACITY = 64;
//桶數(shù)組姚糊，bucket. 這個(gè)也就是hashmap的底層結(jié)構(gòu)贿衍。
transient Node<K,V>[] table;
//數(shù)量，即hashmap中的元素?cái)?shù)量
transient int size;
//hashmap進(jìn)行擴(kuò)容的閾值救恨。 （這個(gè)表示的元素多少贸辈，可不是桶被用了多少哦，比如閾值是16肠槽，當(dāng)有16個(gè)元素就進(jìn)行擴(kuò)容擎淤，而不是說當(dāng)桶被用了16個(gè)）
int threshold;
//當(dāng)前負(fù)載因子，默認(rèn)是 DEFAULT_LOAD_FACTOR=0.75
final float loadFactor;
/************************************三個(gè)構(gòu)造方法***************************************/
public HashMap(int initialCapacity, float loadFactor) {//1秸仙，初始化容量2嘴拢，負(fù)載因子
    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);//總要保持 初始容量為 2的整數(shù)次冪
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

這里需要注意：

1.當(dāng)容量未達(dá)到64，即使鏈表長(zhǎng)度>8寂纪，也不會(huì)樹化席吴，而是進(jìn)行擴(kuò)容。
2.一個(gè)桶中紅黑樹元素少于 6 從紅黑樹變成鏈表
3.默認(rèn)初始容量DEFAULT_INITIAL_CAPACITY不是說map能裝多少個(gè)元素捞蛋，而是桶的個(gè)數(shù)
4.threshold表示hashmap進(jìn)行擴(kuò)容的閾值孝冒。（這個(gè)表示的元素多少，可不是桶被用了多少哦襟交，比如閾值是16迈倍，當(dāng)有16個(gè)元素就進(jìn)行擴(kuò)容，而不是說當(dāng)桶被用了16個(gè)）

put過程源碼分析

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;
    //put1捣域，懶加載啼染，第一次put的時(shí)候初始化table（node數(shù)組）
    if ((tab = table) == null || (n = tab.length) == 0)
     //如果table為null或者長(zhǎng)度為0，hashmap數(shù)組初始化
        n = (tab = resize()).length;
        //計(jì)算下標(biāo)焕梅，返回null代表沒有hash碰撞
    if ((p = tab[i = (n - 1) & hash]) == null)
    //new一個(gè)Node放入數(shù)組中
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //如過命中第一個(gè)節(jié)點(diǎn)迹鹅，覆蓋舊值
        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 {
        //如果是鏈表，存在兩種情況贞言，超過閾值轉(zhuǎn)換成紅黑樹斜棚，否則直接在鏈表后面追加
            for (int binCount = 0; ; ++binCount) {
            //在鏈表尾部追加
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //樹化（轉(zhuǎn)化成紅黑樹）
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果key已經(jīng)存在，覆蓋舊值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //當(dāng)key已經(jīng)存在该窗，執(zhí)行覆蓋舊值邏輯弟蚀。
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //當(dāng)size > threshold咳短，進(jìn)行擴(kuò)容厉膀。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

可以看到put方法中調(diào)用putVal方法進(jìn)行元素的添加音羞，hash(key)方法獲得二次hash后的hash值作為putVal的入?yún)?/p>

1.判斷當(dāng)前table是否為空娜亿，hashMap將初始化操作放在第一次put的時(shí)候
2.計(jì)算hash及桶下標(biāo)。
3.判斷是否發(fā)生hash碰撞
3.1 沒有發(fā)生碰撞鲁冯，new一個(gè)node直接放入桶中
3.2 發(fā)生碰撞
（1） 如過命中第一個(gè)節(jié)點(diǎn)胯府，直接覆蓋節(jié)點(diǎn)并返回舊值
（2）如果是紅黑樹铝阐，插入到紅黑樹中。
（3）如果是鏈表删壮，存在兩種情況贪绘，超過閾值轉(zhuǎn)換成紅黑樹，否則直接在鏈表后面追加央碟，（當(dāng)數(shù)組長(zhǎng)度小于64時(shí)税灌，進(jìn)行擴(kuò)容而不是樹化）
4.根據(jù)上述步驟找到的key覆蓋舊節(jié)點(diǎn)并返回舊值。
5.如果size > threshold硬耍。進(jìn)行擴(kuò)容垄琐。

treeifyBin方法

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果容量 < 64則直接進(jìn)行擴(kuò)容边酒；不轉(zhuǎn)紅黑樹经柴。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

hashmap如何擴(kuò)容的？

（1）擴(kuò)容時(shí)機(jī)：

• 初始化后放入元素時(shí)：創(chuàng)建對(duì)象以后墩朦，HashMap并不是立即初始化table坯认，而是在第一次放入元素時(shí)，才會(huì)初始化table氓涣，這很HashMap節(jié)省內(nèi)存得一種機(jī)制牛哺，而table的初始化其實(shí)是resize方法實(shí)現(xiàn)的。
• 達(dá)到閾值時(shí)：這個(gè)就比較有意思劳吠，所謂閾值引润，就是HashMap中threshold這個(gè)屬性，閾值的計(jì)算方式很簡(jiǎn)單痒玩，基本上就是capacity（table容量） * loadFactor（負(fù)載因子）淳附，這里我覺得capacity應(yīng)該稱為理論容量，是因?yàn)檎Ｇ闆r下達(dá)到閾值就擴(kuò)容了蠢古，達(dá)到閾值時(shí)HashMap認(rèn)為哈希沖突的次數(shù)會(huì)不能接受奴曙，因此需要擴(kuò)容。

（2）這里為什么鏈表長(zhǎng)度大于8了還要滿足元素個(gè)數(shù)不小于64才會(huì)進(jìn)行擴(kuò)容呢草讶？

hashmap默認(rèn)容量為16洽糟，然而插入了9個(gè)元素，它們都在同一個(gè)桶里面堕战，如果這時(shí)進(jìn)行樹化坤溃，樹化本身就是一個(gè)耗時(shí)的過程。時(shí)間復(fù)雜度會(huì)增加嘱丢，性能下降薪介，不如直接進(jìn)行擴(kuò)容，空間換時(shí)間屿讽。

resize方法

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) {
    // 大于最大容量昭灵，不進(jìn)行擴(kuò)容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //擴(kuò)容為原來的兩倍吠裆，<< 位運(yùn)算
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //只有一個(gè)元素，直接移到新的桶中（為什么不先判斷是不是TreeNode烂完？注意TreeNode沒有next節(jié)點(diǎn)试疙，同樣返回為null
                if (e.next == null)
                //使用newCap計(jì)算桶下標(biāo)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                   //有多個(gè)元素
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //判斷成立，說明該元素不用移動(dòng)
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //判斷不成立抠蚣，說明該元素要移位到 (j + oldCap) 位置
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        //j + oldCap即newIndex
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

總結(jié)一下：

• 先確定newCap和newThr
• 創(chuàng)建一個(gè)兩倍于原來（oldTab）容量的數(shù)組（newTab）
• 遍歷oldTab
  • 如果當(dāng)前桶沒有元素直接跳過祝旷。
  • 如果當(dāng)前桶只有一個(gè)元素，直接移動(dòng)到newTab中的索引位嘶窄。（e.hash & (newCap - 1)）
  • 如果當(dāng)前桶為紅黑樹怀跛，在split()方法中進(jìn)行元素的移動(dòng)。
  • 如果當(dāng)前桶為鏈表柄冲，執(zhí)行鏈表的元素移動(dòng)邏輯吻谋。

get源碼分析

public V get(Object key) {
    Node<K,V> e;
    //計(jì)算哈希，調(diào)用getNode方法獲得Node
    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;
    //非空校驗(yàn)以及下標(biāo)計(jì)算
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //獲取桶的頭節(jié)點(diǎn)现横，如果頭結(jié)點(diǎn)key等于目標(biāo)key直接返回漓拾。
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
       // 如果是紅黑樹，執(zhí)行紅黑樹迭代邏輯戒祠，找到目標(biāo)節(jié)點(diǎn)返回骇两。
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
       // 如果是鏈表，執(zhí)行鏈表迭代邏輯姜盈，找到目標(biāo)節(jié)點(diǎn)返回低千。
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

jdk7死循環(huán)問題

jdk8之前采用頭插法，因?yàn)樽髡哒J(rèn)為新插入的數(shù)據(jù)被使用的概率更大馏颂，但是有一個(gè)弊端就是并發(fā)情況會(huì)造成鏈表閉環(huán)示血，get時(shí)死循環(huán)，主要發(fā)生在擴(kuò)容方法的transfer 方法

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 {
                //保留要轉(zhuǎn)移指針的下一個(gè)節(jié)點(diǎn)
                Entry<K, V> next = e.next;
                //計(jì)算出要轉(zhuǎn)移節(jié)點(diǎn)在hash桶中的位置
                int i = indexFor(e.hash, newCapacity);  -----------------1
                //使用頭插法將需要轉(zhuǎn)移的節(jié)點(diǎn)插入到hash桶中原有的單鏈表中
                e.next = newTable[i];                   -----------------2
                //將hash桶的指針指向單鏈表的頭節(jié)點(diǎn)
                newTable[i] = e;                        -----------------3
                //轉(zhuǎn)移下一個(gè)需要轉(zhuǎn)移的節(jié)點(diǎn)
                e = next;
            } while (e != null);
        }
    }
}

代碼解析：

1.記錄當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)
2.indexFor計(jì)算桶位置
3.當(dāng)前節(jié)點(diǎn)的next指向桶內(nèi)鏈表頭結(jié)點(diǎn)
4.當(dāng)前節(jié)點(diǎn)放入原表頭完成頭插
5.e指向第一步記錄的next節(jié)點(diǎn)饱亮，若不為null循環(huán)執(zhí)行邏輯

為什么會(huì)造成閉環(huán)呢矾芙？

HashMap擴(kuò)容導(dǎo)致死循環(huán)的主要原因在于擴(kuò)容后鏈表中的節(jié)點(diǎn)在新的hash桶使用頭插法插入。新的hash桶會(huì)倒置原h(huán)ash桶中的單鏈表近上，那么在多個(gè)線程同時(shí)擴(kuò)容的情況下就可能導(dǎo)致產(chǎn)生一個(gè)存在閉環(huán)的單鏈表剔宪，從而導(dǎo)致死循環(huán)。

在JDK1.8中壹无，HashMap是不會(huì)造成死循環(huán)的葱绒，因?yàn)樵贘DK1.8中，采用的是尾插法斗锭，保證了鏈表的順序與之前一致地淀。而且在1.8中鏈表過長(zhǎng)時(shí)會(huì)轉(zhuǎn)換為紅黑樹，在轉(zhuǎn)換為紅黑樹前岖是，也是先根據(jù)尾插法生成新鏈表再進(jìn)行轉(zhuǎn)換的帮毁，所以是不會(huì)造成死循環(huán)的实苞。

過程分析：首先假設(shè)在擴(kuò)容時(shí)，hash表中有一個(gè)單鏈表烈疚，單鏈表中有兩個(gè)元素：元素1和元素2黔牵。

如果該HashMap為單線程操作時(shí)沒問題，多線程時(shí)（假設(shè)有T1爷肝、T2兩個(gè)線程）：

• T1執(zhí)行到 next = e.next猾浦；時(shí)掛起；
• T2開始執(zhí)行并且執(zhí)行完了整個(gè)流程灯抛，也就是說T2把所有元素都插入了新數(shù)組之后（頭插法）金赦，原來的table引用現(xiàn)在指向了 newtable，即 table = newtable对嚼；

• T1回歸繼續(xù)執(zhí)行夹抗，這時(shí)就會(huì)有如下場(chǎng)景

  
  
• 當(dāng)元素1正常插入后 next 是 元素2，e = next = 元素2猪半，繼續(xù)執(zhí)行插入

• 此時(shí)兔朦，由于原表中 元素2 的 next 已經(jīng)被T2所修改偷线，不再是T1掛起時(shí)的 next = null了磨确，所以T1就會(huì)碰到如下情況，因?yàn)?next 永遠(yuǎn)都不為空声邦，所以就會(huì)一直循環(huán)執(zhí)行插入操作乏奥，造成死循環(huán)。（圖中這種狀態(tài)的鏈表稱為死鏈）

  
  

jdk8是怎么擴(kuò)容的呢（擴(kuò)容機(jī)制的優(yōu)化）亥曹？

if (loTail != null) {
   loTail.next = null;
   //新的位置為原老所處的位置
   newTab[j] = loHead;
}
if (hiTail != null) {
   hiTail.next = null;
   //新的位置為原老所處的位置+原數(shù)組的長(zhǎng)度
   newTab[j + oldCap] = hiHead;  
}

只需要注意newTab[j] = loHead和newTab[j + oldCap] = hiHead這兩行代碼邓了，其中newTab為新的數(shù)組，j為元素在原數(shù)組中的下標(biāo)媳瞪，oldCap為原數(shù)組的長(zhǎng)度骗炉，loHead和hiHead都為元素。

為什么經(jīng)過rehash之后蛇受，元素的位置要么是在原位置句葵，要么是在原位置加原數(shù)組長(zhǎng)度的位置？

rehash利用的特性：元素在重新計(jì)算hash之后兢仰，因?yàn)閚變?yōu)?倍乍丈，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會(huì)發(fā)生這樣的變化：ps：HashMap數(shù)組中鏈表節(jié)點(diǎn)存放了：key把将、value轻专、hash、next屬性察蹲。

擴(kuò)容前 hash & (length - 1) :
key1 : 0001 1001 & 0000 1111 -> 0000 1001
key2 : 0000 1001 & 0000 1111 -> 0000 1001

擴(kuò)容后 hash & (length - 1) :
key1 : 0001 1001 & 0001 1111 -> 0001 1001
key2 : 0000 1001 & 0001 1111 -> 0000 1001

因此请垛，我們?cè)跀U(kuò)充HashMap的時(shí)候催训，不需要像JDK1.7的實(shí)現(xiàn)那樣重新計(jì)算hash，只需要看原來的hash值在擴(kuò)容后新增的那一位是1還是0宗收，如果是0的話索引沒變瞳腌，是1的話索引變成“原索引+oldCap” 【涤辏可以看看下圖為16擴(kuò)充為32的resize示意圖：

這個(gè)設(shè)計(jì)確實(shí)非常的巧妙嫂侍，既省去了重新計(jì)算hash值的時(shí)間，而且同時(shí)荚坞，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的挑宠，因此resize的過程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket了颓影。代碼：

if ((e.hash & oldCap) == 0）

jdk8采用尾插法很好的避免了這個(gè)問題（但出現(xiàn)了數(shù)據(jù)丟失現(xiàn)象）各淀，那么jdk8就是線程安全的嗎？不是的!!!!

if ((p = tab[i = (n - 1) & hash]) == null)

這段代碼是判斷是否出現(xiàn)hash碰撞诡挂，假設(shè)兩個(gè)線程A碎浇、B都在進(jìn)行put操作，并且hash函數(shù)計(jì)算出的插入下標(biāo)是相同的璃俗，當(dāng)線程A執(zhí)行完代碼后由于時(shí)間片耗盡導(dǎo)致被掛起奴璃，而線程B得到時(shí)間片后在該下標(biāo)處插入了元素，完成了正常的插入城豁，然后線程A獲得時(shí)間片苟穆，由于之前已經(jīng)進(jìn)行了hash碰撞的判斷，所有此時(shí)不會(huì)再進(jìn)行判斷唱星，而是直接進(jìn)行插入雳旅，這就導(dǎo)致了線程B插入的數(shù)據(jù)被線程A覆蓋了（數(shù)據(jù)丟失），從而線程不安全间聊。

除此之外攒盈，++size操作和resize等操作都會(huì)因?yàn)樵有詥栴}造成數(shù)據(jù)丟失或者覆蓋。

常見問題總結(jié)

1.HashMap在jdk7與8兩個(gè)版本中有什么區(qū)別哎榴？

• 數(shù)據(jù)結(jié)構(gòu)不同：jdk7使用數(shù)組+鏈表型豁；jdk8使用數(shù)組+鏈表+紅黑樹，引入了紅黑樹叹话，目的是避免單條鏈表過長(zhǎng)而影響查詢效率偷遗；
• 鏈表插入方式不同：jdk7頭插法（多線程可能導(dǎo)致鏈表死循環(huán)）；jdk8采用尾插法驼壶，解決了多線程死循環(huán)問題氏豌，但仍是非線程安全的，多線程時(shí)可能會(huì)造成數(shù)據(jù)丟失問題热凹。
• 擴(kuò)容時(shí)機(jī)不同：在JDK1.7的時(shí)候是先擴(kuò)容后插入的泵喘，這樣就會(huì)導(dǎo)致無論這一次插入是不是發(fā)生hash沖突都需要進(jìn)行擴(kuò)容泪电，如果這次插入的并沒有發(fā)生Hash沖突的話，那么就會(huì)造成一次無效擴(kuò)容纪铺，但是在1.8的時(shí)候是先插入再擴(kuò)容的相速，優(yōu)點(diǎn)其實(shí)是因?yàn)闉榱藴p少這一次無效的擴(kuò)容，原因就是如果這次插入沒有發(fā)生Hash沖突的話鲜锚，那么其實(shí)就不會(huì)造成擴(kuò)容突诬。
• 擴(kuò)容后重新計(jì)算索引的方式不同：jdk1.7需要與新的數(shù)組長(zhǎng)度進(jìn)行重新hash運(yùn)算，這個(gè)方式是相對(duì)耗性能的芜繁，而且多線程環(huán)境下會(huì)造成死鎖旺隙；jdk8優(yōu)化resize 擴(kuò)容，會(huì)判斷之前hash中新增的那一位是0還是1骏令，如果是0的話索引沒變蔬捷，是1的話索引變成“原索引+oldCap” 。

ps：resize()方法會(huì)在HashMap的鍵值對(duì)達(dá)到“閾值”后進(jìn)行數(shù)組擴(kuò)容榔袋，而擴(kuò)容時(shí)會(huì)調(diào)用resize()方法周拐，此外，在jdk1.7中數(shù)組的容量是在HashMap初始化的時(shí)候就已經(jīng)賦予（默認(rèn)16）凰兑，而在jdk1.8中是在put第一個(gè)元素的時(shí)候才會(huì)賦予數(shù)組容量妥粟，而put第一個(gè)元素的時(shí)候也會(huì)調(diào)用resize()方法。

有一點(diǎn)注意區(qū)別聪黎，JDK1.7中rehash的時(shí)候罕容，舊鏈表遷移新鏈表的時(shí)候，如果在新表的數(shù)組索引位置相同稿饰，造成死循環(huán)（這也是擴(kuò)容優(yōu)化的關(guān)鍵原因），JDK1.8不會(huì)露泊。

2.HashMap的put和get方法的具體流程喉镰？

當(dāng)我們put的時(shí)候，首先計(jì)算 key的hash值惭笑，這里調(diào)用了 hash方法侣姆，hash方法實(shí)際是讓key.hashCode()與key.hashCode()>>>16進(jìn)行異或操作，高16bit補(bǔ)0沉噩，一個(gè)數(shù)和0異或不變捺宗，所以 hash 函數(shù)大概的作用就是：高16bit不變，低16bit和高16bit做了一個(gè)異或川蒙，目的是減少碰撞蚜厉。因?yàn)閎ucket數(shù)組大小是2的冪，計(jì)算下標(biāo)index = (table.length - 1) & hash畜眨。

put方法具體流程（jdk1.8）：

①.判斷鍵值對(duì)數(shù)組table[i]是否為空或?yàn)閚ull昼牛，否則執(zhí)行resize()進(jìn)行擴(kuò)容术瓮；
②.根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果table[i]==null贰健，直接新建節(jié)點(diǎn)添加胞四，轉(zhuǎn)向⑥，如果table[i]不為空伶椿，轉(zhuǎn)向③辜伟；
③.判斷table[i]的首個(gè)元素是否和key一樣，如果相同直接覆蓋value脊另，否則轉(zhuǎn)向④游昼，這里的相同指的是hashCode以及equals；
④.判斷table[i] 是否為treeNode尝蠕，即table[i] 是否是紅黑樹烘豌，如果是紅黑樹，則直接在樹中插入鍵值對(duì)看彼，否則轉(zhuǎn)向⑤廊佩；
⑤.遍歷table[i]，判斷鏈表長(zhǎng)度是否大于8靖榕，大于8的話把鏈表轉(zhuǎn)換為紅黑樹标锄，在紅黑樹中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作茁计；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可料皇；
⑥.插入成功后，存放元素后將 modCount 加 1星压。判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了最大容量threshold践剂，如果超過，進(jìn)行擴(kuò)容娜膘。

get方法具體流程（jdk1.8）：

1. 通過 hash & (table.length - 1)獲取查找的數(shù)組下標(biāo);
2. 判斷首節(jié)點(diǎn)是否為空, 為空則直接返回空,不為空進(jìn)入3;
3. 再判斷首節(jié)點(diǎn).key 是否和目標(biāo)值相同, 相同則直接返回(首節(jié)點(diǎn)不用區(qū)分鏈表還是紅黑樹)對(duì)應(yīng)的值逊脯，否則進(jìn)入4;
4. 首節(jié)點(diǎn).next為空, 則直接返回空;
5. 首節(jié)點(diǎn)是樹形節(jié)點(diǎn), 則進(jìn)入紅黑樹數(shù)的取值流程, 并返回結(jié)果;
6. 進(jìn)入鏈表的取值流程, 并返回結(jié)果;

3.簡(jiǎn)述hashmap為什么要轉(zhuǎn)為紅黑樹？為什么不直接開始就使用紅黑樹竣贪？

為什么使用紅黑樹军洼？

• 因?yàn)楫?dāng)鏈表長(zhǎng)度過長(zhǎng)，查找元素耗時(shí)（單鏈表）演怎，用紅黑樹可以減少遍歷時(shí)間匕争，提高遍歷效率。
• 如果一開始就使用紅黑樹爷耀，那么就要進(jìn)行左旋甘桑，右旋，變色等操作，在元素個(gè)數(shù)較小的時(shí)候會(huì)消耗時(shí)間扇住，并且遍歷時(shí)間消耗與鏈表沒什么區(qū)別春缕。

可不可以使用二叉樹，不用紅黑樹艘蹋？為什么閾值是8锄贼？

• 可以使用二叉樹，但是使用二叉樹可能會(huì)出現(xiàn)只有左子樹或者右子樹的情況（即退化為單鏈表）女阀。
• 閾值是8是因?yàn)椴此煞植迹?strong>單個(gè)hash槽中元素為8的概率小于百萬分之一宅荤，所以選擇7為分水嶺，為7不做操作浸策。
• 引入紅黑樹之后當(dāng)桶中鏈表長(zhǎng)度超過8且容量達(dá)到64將會(huì)樹化即轉(zhuǎn)為紅黑樹（put觸發(fā)）冯键。當(dāng)紅黑樹元素少于6會(huì)轉(zhuǎn)為鏈表（remove觸發(fā)）。

ps：為什么樹化和鏈表化的閾值不一樣庸汗？

• 想一個(gè)極端情況惫确，假設(shè)閾值都是8，一個(gè)桶中鏈表長(zhǎng)度為8時(shí)蚯舱，此時(shí)繼續(xù)向該桶中put會(huì)進(jìn)行樹化改化，然后remove又會(huì)鏈表化。如果反復(fù)put和remove枉昏。每次都會(huì)進(jìn)行極其耗時(shí)的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換陈肛。
• 如果是兩個(gè)閾值，將會(huì)形成一個(gè)緩沖帶兄裂，減少這種極端情況發(fā)生的概率句旱。

一般使用什么作為key？

• 一般使用String晰奖，Integer這種不可變類作為key谈撒，保證了hash值是不可更改的，減少了hash碰撞畅涂。
• 并且這種類已經(jīng)很好的實(shí)現(xiàn)了hashcode與equals方法的重寫港华！ps：因?yàn)閔ashcode生成是一串定長(zhǎng)的數(shù)字，當(dāng)數(shù)據(jù)量很大時(shí)候午衰，難免會(huì)出現(xiàn)不同對(duì)象hashcode相同的情況。也就是說hashcode相同冒萄，元素可能不同臊岸，hashcode不同，元素一定不同尊流。

HashMap 中的 key若 Object類型帅戒， 則需實(shí)現(xiàn)哪些方法？

• hashcode方法：計(jì)算數(shù)據(jù)存儲(chǔ)位置（只是為了縮小比較的范圍，提高效率）
• equals方法：判斷插入位置是否存在相同的key逻住，若相同钟哥，直接覆蓋value（保證key唯一）。

4.HashMap是如何確定鍵值對(duì)的位置瞎访？如何解決Hash沖突腻贰？

不用hash值直接做索引的原因：hashCode()方法返回的是int整數(shù)類型，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)扒秸，約有40億個(gè)映射空間播演，而HashMap的容量范圍是在16（初始化默認(rèn)值）~2 ^ 30，HashMap通常情況下是取不到最大值的伴奥，并且設(shè)備上也難以提供這么多的存儲(chǔ)空間写烤，從而導(dǎo)致通過hashCode()計(jì)算出的哈希值可能不在數(shù)組大小范圍內(nèi)，進(jìn)而無法匹配存儲(chǔ)位置拾徙。

如何確定鍵值對(duì)位置（確定插入的索引位置）：

• 如果key為null洲炊，則都會(huì)被放置在數(shù)組的第0位。
• 如果key不為null尼啡，則通過key的hashCode方法獲得hash值->與自身右移16位進(jìn)行異或運(yùn)算->與length - 1進(jìn)行與運(yùn)算暂衡，得到數(shù)組中的索引獲得元素 或 再到鏈表或紅黑樹中查詢。

hash表如何避免哈希沖突：

• hash算法
  • 在hashCode后獲得的hash值在與自身右移16位進(jìn)行異或運(yùn)算
  • 每次擴(kuò)容都只擴(kuò)容2的次冪玄叠，都是為了盡量減少hash沖突古徒，提高查詢效率。
• 擴(kuò)容機(jī)制
  • 當(dāng)哈希表中的元素個(gè)數(shù) >= 擴(kuò)容閾值（容量*加載因子）
• 數(shù)據(jù)結(jié)構(gòu)（存儲(chǔ)機(jī)制）
  • 鏈地址法 + 紅黑樹（jdk1.8）

5.HashMap存值過程中什么時(shí)候進(jìn)行數(shù)組擴(kuò)容读恃？為什么每次擴(kuò)容都是2的次冪隧膘？

擴(kuò)容時(shí)機(jī)：

• 在存值后進(jìn)行擴(kuò)容，即put操作寺惫。注意：當(dāng)數(shù)組容量未達(dá)到64疹吃，即使鏈表長(zhǎng)度>8，也不會(huì)樹化西雀，而是進(jìn)行擴(kuò)容萨驶。
• 在jdk1.8中，resize方法擴(kuò)容是在hashmap中的鍵值對(duì)大于閥值時(shí), 即當(dāng)前數(shù)組的長(zhǎng)度乘以加載因子的值的時(shí)候艇肴∏晃兀或者初始化時(shí)，就調(diào)用resize方法進(jìn)行擴(kuò)容再悼；

HashMap中的加載因子為什么是0.75核畴，如果調(diào)整為1會(huì)發(fā)生什么？

• 加載因子為0.75是官方給出的默認(rèn)數(shù)值冲九，在官方給出的注釋中也表明了這是一個(gè)折中的選擇谤草。
• 加載因子越小空間利用率越低，查詢效率越高；而越接近1丑孩，空間利用率越高冀宴，效率越低。
• 調(diào)整為1則當(dāng)HashMap中數(shù)組每個(gè)位置都有鍵值對(duì)時(shí)才進(jìn)行擴(kuò)容温学，即最大程度的利用空間略贮。

擴(kuò)容細(xì)節(jié)：

• 每次擴(kuò)容為2的冪次，因?yàn)?strong>只有當(dāng)數(shù)組大小為2的冪次枫浙，數(shù)組最大索引（數(shù)組的長(zhǎng)度 - 1）的二進(jìn)制表示的每個(gè)位置都是1刨肃，從而使&運(yùn)算的分布更加均勻，減少了hash沖突箩帚。
• 擴(kuò)展后Node對(duì)象的位置要么在原位置真友，看原來的hash值在擴(kuò)容后新增的那一位是1還是0，如果是0的話索引沒變紧帕，是1的話索引變成“原索引+oldCap” 盔然。

hashmap的長(zhǎng)度是2的冪次（分析）

• 為了能讓 HashMap 存取?效，盡量少碰撞是嗜，也就是要盡量把數(shù)據(jù)分配均勻愈案。Hash值?之前還要先做對(duì)數(shù)組的?度取模運(yùn)算，得到的余數(shù)才能?來要存放的位置也就是對(duì)應(yīng)的數(shù)組下標(biāo)鹅搪。這個(gè)數(shù)組下標(biāo)的計(jì)算?法是“ (n - 1) & hash ”站绪。我們?先可能會(huì)想到采?%取余的操作來實(shí)現(xiàn)。

• 但是丽柿，重點(diǎn)來了：“hash % length 等價(jià)于 hash & (length-1) 恢准。” （1）采??進(jìn)制位操作 &甫题，相對(duì)于%能夠提?運(yùn)算效率馁筐，（2）減少hash碰撞，2的n次方實(shí)際就是1后面n個(gè)0坠非，2的n次方-1 實(shí)際就是n個(gè)1敏沉；

6.HashMap有什么特點(diǎn)？

（1）鍵值允許為空（null）

• key可為null炎码，但是必須唯一（這時(shí)hash值默認(rèn)設(shè)置為0）盟迟；
• value可以有多個(gè)null，不需要唯一潦闲。

（2）線程安全問題

多線程下死循環(huán)問題（jdk1.7）：

• 在多線程下队萤，jdk1.7擴(kuò)容操作時(shí)可能會(huì)造成死循環(huán)，單鏈表倒置矫钓，具體見上邊例子。
• 不過，jdk 1.8 后解決了這個(gè)問題新娜，1.7鏈表元素采用的是頭插法赵辕，1.8改成尾插法。但是還是不建議在多線程下使? HashMap概龄，因?yàn)槎嗑€程下使? HashMap 還是會(huì)存在其他問題?如數(shù)據(jù)丟失还惠。并發(fā)環(huán)境下推薦使? ConcurrentHashMap。

多線程下數(shù)據(jù)丟失問題：

• 操作頭結(jié)點(diǎn)：HashMap底層在操作每個(gè)數(shù)組位置時(shí)都是將節(jié)點(diǎn)頭拿下來進(jìn)行操作私杜，操作后再將節(jié)點(diǎn)頭放回去蚕键。這樣就會(huì)導(dǎo)致兩個(gè)線程同時(shí)獲取相同的節(jié)點(diǎn)頭，先放上去節(jié)點(diǎn)頭的線程被后放上去的覆蓋導(dǎo)致數(shù)據(jù)丟失衰粹。
• 添加尾結(jié)點(diǎn)：再比如在元素添加時(shí)也會(huì)出現(xiàn)同時(shí)獲取到最后一個(gè)元素（多線程添加他的next節(jié)點(diǎn)）锣光，先添加的next節(jié)點(diǎn)被后添加的覆蓋導(dǎo)致數(shù)據(jù)丟失。

怎么解決hashmap線程安全問題铝耻？

• 使用HashTable 或 ConcurrentHashMap誊爹，但是推薦ConcurrentHashMap，因?yàn)閔ashtable加鎖的方式很粗暴瓢捉，加的是整個(gè)add方法频丘，也就是鎖住了整個(gè)數(shù)組，ConcurrentHashMap僅僅是鎖住了一個(gè)node節(jié)點(diǎn)泡态。

ps：hashset是基于hashmap實(shí)現(xiàn)的搂漠，默認(rèn)構(gòu)造函數(shù)是構(gòu)建一個(gè)初始容量為16，負(fù)載因子為0.75的hashmap某弦。封裝了一個(gè)hashmap 對(duì)象來存儲(chǔ)所有的集合元素桐汤，所有放在 hashset中的集合元素實(shí)際上由 hashmap的key來保存，而 hashset中的 hashmap的 value則存儲(chǔ)了一個(gè)PRESENT的靜態(tài)object對(duì)象

ps：hashset和 treeset有什么區(qū)別

• hashset是由一個(gè)hash表來實(shí)現(xiàn)的刀崖，因此它的元素是無序的惊科，add，remove亮钦，contains方法的時(shí)間復(fù)雜度是 O(1)
• treeset是由一個(gè)樹形結(jié)構(gòu)來實(shí)現(xiàn)的馆截，它里面的元素是有序的，因此蜂莉，add蜡娶，remove，contains方法的時(shí)間復(fù)雜度是 O(logn）

（3）hashmap不能保證有序

插入順序與存儲(chǔ)順序不一致

• 插入循序 == 用戶操作順序
• 存儲(chǔ)順序 == hash散列的索引順序（隨機(jī)性映穗、均勻性）

同時(shí)窖张，存儲(chǔ)位置會(huì)在擴(kuò)容時(shí)發(fā)生改變！

（4）hashmap三種遍歷方法

• 通過HashMap.entrySet()得到鍵值對(duì)集合蚁滋；
• 通過HashMap.keySet()獲得鍵的Set集合宿接；
• 通過HashMap.values()得到“值”的集合

巨人的肩膀：

https://blog.csdn.net/ethan_199402/article/details/107001112
https://blog.csdn.net/u012501054/article/details/103710171/
https://blog.csdn.net/AlohaHeja/article/details/90576432
https://blog.csdn.net/qq_36520235/article/details/82417949