一嘲恍、HashMap內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是什么？

數(shù)組+單向鏈表

image.png

二嚷狞、怎么驗(yàn)證內(nèi)部結(jié)構(gòu)是數(shù)組和單向鏈表块促？

a、數(shù)組：通過(guò)HashMap 源碼知道床未、HashMap內(nèi)部有個(gè)屬性 transient Node<K,V>[] table
b竭翠、單向鏈表：內(nèi)部類Node里面維護(hù)了一個(gè)next的屬性 Node<K,V> next，是指向下一個(gè)節(jié)點(diǎn)的薇搁；

三斋扰、HashMap里面為什么會(huì)有hash的存在？hash計(jì)算的理解啃洋？

我們先看下我的事例代碼

public class HashMapDemo {

    public static void main(String[] args) {
        HashMap<String,String> map=new HashMap<String, String>();
        String keys="names";
        String values="zhangsans";
        map.put(keys,values);
        System.out.println("數(shù)組的默認(rèn)大写酢："+ (1<<4));
        System.out.println("對(duì)應(yīng)二進(jìn)制："+binaryToDecimal((15)));
        int hashCodes=keys.hashCode();
        System.out.println("hashCode值："+hashCodes);
        System.out.println("對(duì)應(yīng)二進(jìn)制："+binaryToDecimal(hashCodes));
        int dw=(hashCodes >>> 16);
        System.out.println("向右移16位，高位補(bǔ)0 值："+dw);
        System.out.println("對(duì)應(yīng)二進(jìn)制："+binaryToDecimal(dw));
        int yhValues=hashCodes ^ dw;
        System.out.println("異或運(yùn)算結(jié)果："+yhValues);
        System.out.println("對(duì)應(yīng)二進(jìn)制："+binaryToDecimal(yhValues));
        //(n:數(shù)組長(zhǎng)度 - 1) & hash ：hash值
        System.out.println("下標(biāo)計(jì)算："+(yhValues & (16-1)));
    }

    /**
     * 轉(zhuǎn)換二進(jìn)制
     * @param n
     * @return
     */
    public static String binaryToDecimal(int n){
      String str = "";
       for(int i = 31;i >= 0; i--){
           int ys=(n >>> i & 1);
           str = str + ys;
       }
       return str;
    }
}

結(jié)果：

數(shù)組的默認(rèn)大泻曷Α：16
對(duì)應(yīng)二進(jìn)制：00000000000000000000000000001111
hashCode值：104585032
對(duì)應(yīng)二進(jìn)制：00000110001110111101011101001000
向右移16位问裕，高位補(bǔ)0 值：1595
對(duì)應(yīng)二進(jìn)制：00000000000000000000011000111011
異或運(yùn)算結(jié)果：104583539
對(duì)應(yīng)二進(jìn)制：00000110001110111101000101110011
下標(biāo)計(jì)算：3

1. 為了Node節(jié)點(diǎn)數(shù)據(jù)落在何處 ;
2. 當(dāng)put數(shù)據(jù)的時(shí)候，我們通過(guò)源碼知道孵坚，會(huì)先經(jīng)過(guò)數(shù)組粮宛，而數(shù)組的默認(rèn)大小是16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 
//這個(gè)時(shí)候我們知道了數(shù)組默認(rèn)大小，那么我們put的數(shù)據(jù)放在哪塊呢卖宠？隨機(jī)放巍杈？

a. 首先我們會(huì) 通過(guò)對(duì) Object.hashCode() 得到一個(gè)整型數(shù)，【3373707】逗堵；
b. 根據(jù)數(shù)組默認(rèn)大小秉氧，我們知道數(shù)組下標(biāo)必須在0-15（擴(kuò)容的下面說(shuō)），那么我們的算法肯定得控制在這個(gè)值之類蜒秤，否則就會(huì)發(fā)生數(shù)組越界
c. 而hashCode是通過(guò) key.hashCode()高16位和低16位進(jìn)行異或運(yùn)算得到一個(gè)整數(shù)類型的值

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

d. 最后經(jīng)過(guò) & “與”運(yùn)算汁咏，得到下標(biāo)亚斋；

(n - 1) & hash

這個(gè)地方順帶說(shuō)下：
這個(gè)也正好解釋了為啥HashMap的數(shù)組長(zhǎng)度要取2的整次冪。數(shù)組長(zhǎng)度-1攘滩，正好相當(dāng)于一個(gè)“低位掩碼”帅刊，然后呢， & “與”運(yùn)算的結(jié)果就是散列值得高位全部歸零漂问，只保留低位值赖瞒；然后我們拿數(shù)組默認(rèn)長(zhǎng)度來(lái)說(shuō)，16蚤假，下標(biāo)就是 0-15栏饮；然后倒除法得到二進(jìn)制值 1111

//高位全部歸零，只保留末四位

    0000 0110 0011 1011 1101 0111 0100 1000
&   0000 0000 0000 0000 0000 0000 0000 1111
-------------------------------------------
    0000 0000 0000 0000 0000 0000 0000 1000    

看到這里磷仰，我們大概就會(huì)想到一個(gè)問(wèn)題袍嬉，這樣就算我的散列值分布再松散，要是只取最后幾位的話灶平，碰撞也會(huì)很嚴(yán)重伺通。分布上成等差數(shù)列的漏洞，恰好使最后幾個(gè)低位呈現(xiàn)規(guī)律性重復(fù)逢享。

這時(shí)候 “擾動(dòng)函數(shù)" 的價(jià)值就體現(xiàn)出來(lái)了, 下面是所有值得二進(jìn)制變化

h=hashCode()            0000 0110 0011 1011 1101 0111 0100 1000
—————————————————————————————————————————————————————————————————
h >>> 16                0000 0000 0000 0000 0000 0110 0011 1011
—————————————————————————————————————————————————————————————————
hash ^ hash >>>16       0000 0110 0011 1011 1101 0001 0111 0011
—————————————————————————————————————————————————————————————————
16-1                    0000 0000 0000 0000 0000 0000 0000 1111
—————————————————————————————————————————————————————————————————
(16-1) & hash           0000 0000 0000 0000 0000 0000 0000 0011
—————————————————————————————————————————————————————————————————
                                                              3

在上面大家可以比對(duì)下 h 和 h >>> 16 是不是發(fā)現(xiàn)了一個(gè)很有意思的東西罐监，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位瞒爬，以此來(lái)加大低位的隨機(jī)性弓柱。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來(lái)侧但。
JDK8只做了一次干擾吆你，為什么呢？推薦大家看下《An introduction to optimising a hashing strategy》的一個(gè)實(shí)驗(yàn)應(yīng)該就是明白了
e. 其實(shí)上面b-d可以直接替換成 Object.hashCode() % 16 這樣得到的結(jié)果和&運(yùn)算的結(jié)果都是保證在 0-15 的俊犯，但是對(duì)于計(jì)算機(jī)來(lái)說(shuō)妇多，& 運(yùn)算的效率比取模運(yùn)算的效率高。（這里也是一個(gè)注意點(diǎn)）

四燕侠、HashMap者祖，put的流程（里面包含了很多面點(diǎn)，問(wèn)題和解釋）

image.png