面試官：你了解HashMap嗎?【Java培訓(xùn)】

　　一、前言：

　　 面試過的人都知道，HashMap是Java程序員在面試中最最最經(jīng)常被問到的一個(gè)點(diǎn)，可以說，不了解HashMap都不好意思說自己是做Java開發(fā)的?；旧夏闳ッ嬖囀夜?，有七八家都會問到你HashMap。那么今天，就帶著大家從源碼的角度去分析一下，HashMap具體是怎么實(shí)現(xiàn)的。

　　二、HashMap的構(gòu)造方法

　　1.HashMap構(gòu)造方法

　　我們先來看HashMap的四個(gè)構(gòu)造方法

```java
//initialCapacity給定的初始化容量，loadFactor擴(kuò)容因子
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);
    }

public HashMap(int initialCapacity) {
        //內(nèi)部調(diào)用了上邊的構(gòu)造方法
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

public HashMap() {//空參構(gòu)造
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

public HashMap(Map<? extends K, ? extends V> m) {//構(gòu)造傳入一個(gè)map，將map中的值放到hashmap中
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
```

　　2.構(gòu)造方法里的putMapEntries方法

　　剛才構(gòu)造方法中提到了putMapEntries這個(gè)方法，接下來就讓我們一起看一下

//該函數(shù)用于將一個(gè)map賦值給新的HashMap
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    //定義變量接收舊hashmap的size    
    int s = m.size();
        //判斷s的容量是否大于0
        if (s > 0) {
            //判斷當(dāng)前數(shù)組有沒有初始化
            if (table == null) { // pre-size
                ////求出以  舊hashmap數(shù)組容量為閾值  的數(shù)組容量賦值給ft
                float ft = ((float)s / loadFactor) + 1.0F;
                //判斷是不是大于最大容量，如果是，賦值為最大容量，否則將ft賦值給t
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                //判斷t是否大于threshold(數(shù)組擴(kuò)容閾值)
                if (t > threshold)
                  //通過tablesizefor方法求出大于等于t的最小2的次冪值賦值給threshold（數(shù)組擴(kuò)容閾值）
                    threshold = tableSizeFor(t);
            }
            //如果數(shù)組長度大于擴(kuò)容閾值，進(jìn)行resize擴(kuò)容操作 
            else if (s > threshold)
                resize();
            //循環(huán)遍歷取出舊hashmap的值放入當(dāng)前hashmap
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
/*  
    if (table == null)分支，是判斷當(dāng)前數(shù)組是否初始化，因?yàn)樵趈dk1.8之后，只有當(dāng)你第一次放值時(shí)，才會幫你創(chuàng)建16位的數(shù)組。
    
    float ft = ((float)s / loadFactor) + 1.0F經(jīng)過除運(yùn)算再加上1.0F是為了向上取整
    
    if (t > threshold)注意一個(gè)細(xì)節(jié)，做判斷的的時(shí)候，數(shù)組還沒有初始化，這里的threshold的值還是給定的數(shù)組長度的值，也就是capacity的值
    
    else if (s > threshold)說明傳入的map集合大于當(dāng)前的擴(kuò)容閾值，需要進(jìn)行resize擴(kuò)容操作
*/
```

　　tableSizeFor方法

　　剛才putMapEntries方法中，調(diào)用了tableSizeFor方法，接下來我們看一下這個(gè)tableSizeFor方法。

　　作用：創(chuàng)建hashMap對象時(shí)調(diào)用有參構(gòu)造，傳入初始容量，需要保證hashMap的初始長度為2的n次冪。

　　tableSizeFor方法用來計(jì)算大于等于并離傳入值最近的2的n次冪的數(shù)值，比如傳入15，算出結(jié)果為16，傳入17，算出結(jié)果為32。

　　通過二進(jìn)制的位移，第一次右移一位，第二次右移兩位，第三次右移四位。。。通過五次位移，將范圍內(nèi)所有的位數(shù)都變?yōu)?，高位補(bǔ)0，最后得出來的結(jié)果再加上1，最后算出來的結(jié)果一定是2的n次冪。

//這個(gè)方法的作用是找到大于等于給定容量的最小2的次冪值
//>>>表示無符號右移，也叫邏輯右移，即若該數(shù)為正，則高位補(bǔ)0，而若該數(shù)為負(fù)數(shù)，則右移后高位同樣補(bǔ)0
7--》8
16--》16
static final int tableSizeFor(int cap) {
        //先將數(shù)組長度減1，之所以在開始移位前先將容量-1，是為了避免給定容量已經(jīng)是8,16這樣2的冪時(shí)，不減一       直接移位會導(dǎo)致得到的結(jié)果比預(yù)期大。比如預(yù)期16得到應(yīng)該是16，直接移位的話會得到32。
        int n = cap - 1;
        //右移一位，在進(jìn)行或運(yùn)算，這個(gè)時(shí)候最高位和次高位就已經(jīng)都是1，此時(shí)是2個(gè)1
        n |= n >>> 1;
        //右移兩位，在進(jìn)行或運(yùn)算，這個(gè)時(shí)候由上次運(yùn)算得出的兩個(gè)1，變成了四個(gè)1
        n |= n >>> 2;
        //右移四位
        n |= n >>> 4;
        //右移八位
        n |= n >>> 8;
        //右移十六位，這個(gè)時(shí)候所有的位數(shù)都變?yōu)榱?
        n |= n >>> 16;
        //n+1操作，是為了進(jìn)1，這個(gè)時(shí)候算出來的數(shù)值就一點(diǎn)是 2的n次冪
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
```

　　移位的思想

　　2的整數(shù)冪用二進(jìn)制表示都是最高有效位為1，其余全是0。

　　對任意十進(jìn)制數(shù)轉(zhuǎn)換為2的整數(shù)冪，結(jié)果是這個(gè)數(shù)本身的最高有效位的前一位變成1，最高有效位以及其后的位都變?yōu)?。

　　核心思想是，先將最高有效位以及其后的位都變?yōu)?，最后再+1，就進(jìn)位到前一位變成1，其后所有的滿2變0。所以關(guān)鍵是如何將最高有效位后面都變?yōu)?。

　　先移位，再或運(yùn)算。

　　> 右移一位，再或運(yùn)算，就有兩位變?yōu)?;

　　>

　　> 右移兩位，再或運(yùn)算，就有四位變?yōu)?，，，

　　>

　　> 最后右移16位再或運(yùn)算，保證32位的int類型整數(shù)最高有效位之后的位都能變?yōu)?。

　　三、HashMap的底層原理

　　先來看幾個(gè)重要的參數(shù)：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認(rèn)數(shù)組初始容量

static final int MAXIMUM_CAPACITY = 1 << 30;//數(shù)組最大容量

static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認(rèn)加載因子

static final int TREEIFY_THRESHOLD = 8;//樹化的閾值

static final int UNTREEIFY_THRESHOLD = 6;//由樹退化到鏈表的閾值

static final int MIN_TREEIFY_CAPACITY = 64;//樹化最小數(shù)組容量

//node節(jié)點(diǎn)，繼承了Map.entry,在Entry原有的K,V的基礎(chǔ)上追加了hash和next字段
//分別表示key的hash值和下一個(gè)節(jié)點(diǎn)
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

}
//重寫了計(jì)算hash的方法
//將 Hash 值的高 16 位右移并與原 Hash 值取異或運(yùn)算(^)，混合高 16 位和低 16 位的值
//得到一個(gè)更加散列的低 16 位的 Hash 值。
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
```

　　HashMap在JDK1.8之前的實(shí)現(xiàn)方式數(shù)組+鏈表,

　　但是在JDK1.8后對HashMap進(jìn)行了底層優(yōu)化,改為了由 **數(shù)組+鏈表或者數(shù)值+紅黑樹**實(shí)現(xiàn),主要的目的是提高查找效率

　　1. Jdk8數(shù)組+鏈表或者數(shù)組+紅黑樹實(shí)現(xiàn)，當(dāng)鏈表中的元素大于等于8 個(gè)并且數(shù)組長度大于等于64以后， 會將鏈表轉(zhuǎn)換為紅黑樹，當(dāng)紅黑樹節(jié)點(diǎn) 小于 等于6 時(shí)又會退化為鏈表。

　　2. 當(dāng)new HashMap()時(shí)，底層沒有創(chuàng)建數(shù)組，首次調(diào)用put()方法示時(shí)，會調(diào)用resize方法，底層創(chuàng)建長度為16的數(shù)組，jdk8底層的數(shù)組是：Node[],而非Entry[]，用數(shù)組容量大小乘以加載因子得到一個(gè)值，一旦數(shù)組中存儲的元素個(gè)數(shù)超過該值就會調(diào)用resize方法將數(shù)組擴(kuò)容到原來的兩倍，在做擴(kuò)容的時(shí)候會生成一個(gè)新的數(shù)組，原來的所有數(shù)據(jù)需要重新計(jì)算哈希碼值重新分配到新的數(shù)組，所以擴(kuò)容的操作非常消耗性能。

　　默認(rèn)的負(fù)載因子大小為0.75，數(shù)組大小為16。也就是說，默認(rèn)情況下，那么當(dāng)HashMap中元素個(gè)數(shù)超過16*0.75=12的時(shí)候，就把數(shù)組的大小擴(kuò)展為2*16=32，即擴(kuò)大一倍。

　　3. 在我們Java中任何對象都有hashcode，hash算法就是通過hashcode與自己進(jìn)行向右位移16的異或運(yùn)算。這樣做是為了使高位的16位hash也能參與運(yùn)算，使運(yùn)算出來的hash值足夠隨機(jī)，足夠分散，還有產(chǎn)生的數(shù)組下標(biāo)足夠隨機(jī)。

　　map.put(k,v)實(shí)現(xiàn)原理：

　　(1)首先將k,v封裝到Node對象當(dāng)中(節(jié)點(diǎn))。

　　(2)先調(diào)用k的hashCode()方法得出哈希值，并通過哈希算法轉(zhuǎn)換成數(shù)組的下標(biāo)。

　　(3)下標(biāo)位置上如果沒有任何元素，就把Node添加到這個(gè)位置上。如果說下標(biāo)對應(yīng)的位置上有鏈表。此時(shí)，就會拿著k和鏈表上每個(gè)節(jié)點(diǎn)的k進(jìn)行equal。如果所有的equals方法返回都是false，那么這個(gè)新的節(jié)點(diǎn)將被添加到鏈表的末尾。如其中有一個(gè)equals返回了true，那么這個(gè)節(jié)點(diǎn)的value將會被覆蓋。

　　HashMap中的put()方法

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

　　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;
        //判斷數(shù)組是否未初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            //如果未初始化，調(diào)用resize方法 進(jìn)行初始化
            n = (tab = resize()).length;
        //通過 & 運(yùn)算求出該數(shù)據(jù)（key）的數(shù)組下標(biāo)并判斷該下標(biāo)位置是否有數(shù)據(jù)
        if ((p = tab[i = (n - 1) & hash]) == null)
            //如果沒有，直接將數(shù)據(jù)放在該下標(biāo)位置
            tab[i] = newNode(hash, key, value, null);
        //該數(shù)組下標(biāo)有數(shù)據(jù)的情況
        else {
            Node<K,V> e; K k;
            //判斷該位置數(shù)據(jù)的key和新來的數(shù)據(jù)是否一樣
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //如果一樣，證明為修改操作，該節(jié)點(diǎn)的數(shù)據(jù)賦值給e,后邊會用到
                e = p;
            //判斷是不是紅黑樹
            else if (p instanceof TreeNode)
                //如果是紅黑樹的話，進(jìn)行紅黑樹的操作
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //新數(shù)據(jù)和當(dāng)前數(shù)組既不相同，也不是紅黑樹節(jié)點(diǎn)，證明是鏈表
            else {
                //遍歷鏈表
                for (int binCount = 0; ; ++binCount) {
                    //判斷next節(jié)點(diǎn)，如果為空的話，證明遍歷到鏈表尾部了
                    if ((e = p.next) == null) {
                        //把新值放入鏈表尾部
                        p.next = newNode(hash, key, value, null);
                        //因?yàn)樾虏迦肓艘粭l數(shù)據(jù)，所以判斷鏈表長度是不是大于等于8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //如果是，進(jìn)行轉(zhuǎn)換紅黑樹操作
                            treeifyBin(tab, hash);
                        break;
                    }
                    //判斷鏈表當(dāng)中有數(shù)據(jù)相同的值，如果一樣，證明為修改操作
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //把下一個(gè)節(jié)點(diǎn)賦值為當(dāng)前節(jié)點(diǎn)
                    p = e;
                }
            }
            //判斷e是否為空（e值為修改操作存放原數(shù)據(jù)的變量）
            if (e != null) { // existing mapping for key
                //不為空的話證明是修改操作，取出老值
                V oldValue = e.value;
                //一定會執(zhí)行  onlyIfAbsent傳進(jìn)來的是false
                if (!onlyIfAbsent || oldValue == null)
                    //將新值賦值當(dāng)前節(jié)點(diǎn)
                    e.value = value;
                afterNodeAccess(e);
                //返回老值
                return oldValue;
            }
        }
        //計(jì)數(shù)器，計(jì)算當(dāng)前節(jié)點(diǎn)的修改次數(shù)
        ++modCount;
        //當(dāng)前數(shù)組中的數(shù)據(jù)數(shù)量如果大于擴(kuò)容閾值
        if (++size > threshold)
            //進(jìn)行擴(kuò)容操作
            resize();
        //空方法
        afterNodeInsertion(evict);
        //添加操作時(shí) 返回空值
        return null;
    }
```

　　map中resize方法

//擴(kuò)容、初始化數(shù)組
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        //如果當(dāng)前數(shù)組為null的時(shí)候，把oldCap老數(shù)組容量設(shè)置為0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //老的擴(kuò)容閾值
        int oldThr = threshold;
        int newCap, newThr = 0;
        //判斷數(shù)組容量是否大于0，大于0說明數(shù)組已經(jīng)初始化
        if (oldCap > 0) {
            //判斷當(dāng)前數(shù)組長度是否大于最大數(shù)組長度
            if (oldCap >= MAXIMUM_CAPACITY) {
                //如果是，將擴(kuò)容閾值直接設(shè)置為int類型的最大數(shù)值并直接返回
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果在最大長度范圍內(nèi)，則需要擴(kuò)容  OldCap << 1等價(jià)于oldCap*2
            //運(yùn)算過后判斷是不是最大值并且oldCap需要大于16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold  等價(jià)于oldThr*2
        }
        //如果oldCap<0，但是已經(jīng)初始化了，像把元素刪除完之后的情況，那么它的臨界值肯定還存在，                如果是首次初始化，它的臨界值則為0
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        //數(shù)組未初始化的情況，將閾值和擴(kuò)容因子都設(shè)置為默認(rèn)值
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //初始化容量小于16的時(shí)候，擴(kuò)容閾值是沒有賦值的
        if (newThr == 0) {
            //創(chuàng)建閾值
            float ft = (float)newCap * loadFactor;
            //判斷新容量和新閾值是否大于最大容量
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //計(jì)算出來的閾值賦值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        //根據(jù)上邊計(jì)算得出的容量 創(chuàng)建新的數(shù)組       
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //賦值
        table = newTab;
        //擴(kuò)容操作，判斷不為空證明不是初始化數(shù)組
        if (oldTab != null) {
            //遍歷數(shù)組
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //判斷當(dāng)前下標(biāo)為j的數(shù)組如果不為空的話賦值個(gè)e，進(jìn)行下一步操作
                if ((e = oldTab[j]) != null) {
                    //將數(shù)組位置置空
                    oldTab[j] = null;
                    //判斷是否有下個(gè)節(jié)點(diǎn)
                    if (e.next == null)
                        //如果沒有，就重新計(jì)算在新數(shù)組中的下標(biāo)并放進(jìn)去
                        newTab[e.hash & (newCap - 1)] = e;
                    //有下個(gè)節(jié)點(diǎn)的情況，并且判斷是否已經(jīng)樹化
                    else if (e instanceof TreeNode)
                        //進(jìn)行紅黑樹的操作
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //有下個(gè)節(jié)點(diǎn)的情況，并且沒有樹化（鏈表形式）
                    else {
                        //比如老數(shù)組容量是16，那下標(biāo)就為0-15
                        //擴(kuò)容操作*2，容量就變?yōu)?2，下標(biāo)為0-31
                        //低位：0-15，高位16-31
                        //定義了四個(gè)變量
                        //        低位頭          低位尾
                        Node<K,V> loHead = null, loTail = null;
                        //        高位頭          高位尾
                        Node<K,V> hiHead = null, hiTail = null;
                        //下個(gè)節(jié)點(diǎn)
                        Node<K,V> next;
                        //循環(huán)遍歷
                        do {
                            //取出next節(jié)點(diǎn)
                            next = e.next;
                            //通過 與操作 計(jì)算得出結(jié)果為0
                            if ((e.hash & oldCap) == 0) {
                                //如果低位尾為null，證明當(dāng)前數(shù)組位置為空，沒有任何數(shù)據(jù)
                                if (loTail == null)
                                    //將e值放入低位頭
                                    loHead = e;
                                //低位尾不為null，證明已經(jīng)有數(shù)據(jù)了
                                else
                                    //將數(shù)據(jù)放入next節(jié)點(diǎn)
                                    loTail.next = e;
                                //記錄低位尾數(shù)據(jù)
                                loTail = e;
                            }
                            //通過 與操作 計(jì)算得出結(jié)果不為0
                            else {
                                 //如果高位尾為null，證明當(dāng)前數(shù)組位置為空，沒有任何數(shù)據(jù)
                                if (hiTail == null)
                                    //將e值放入高位頭
                                    hiHead = e;
                                //高位尾不為null，證明已經(jīng)有數(shù)據(jù)了
                                else
                                    //將數(shù)據(jù)放入next節(jié)點(diǎn)
                                    hiTail.next = e;
                               //記錄高位尾數(shù)據(jù)
                                hiTail = e;
                            }
                            //如果e不為空，證明沒有到鏈表尾部，繼續(xù)執(zhí)行循環(huán)
                        } while ((e = next) != null);
                        //低位尾如果記錄的有數(shù)據(jù)，是鏈表
                        if (loTail != null) {
                            //將下一個(gè)元素置空
                            loTail.next = null;
                            //將低位頭放入新數(shù)組的原下標(biāo)位置
                            newTab[j] = loHead;
                        }
                        //高位尾如果記錄的有數(shù)據(jù)，是鏈表
                        if (hiTail != null) {
                            //將下一個(gè)元素置空
                            hiTail.next = null;
                            //將高位頭放入新數(shù)組的(原下標(biāo)+原數(shù)組容量)位置
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //返回新的數(shù)組對象
        return newTab;
    }
```

　　map.get(k)實(shí)現(xiàn)原理

　　(1)、先調(diào)用k的hashCode()方法得出哈希值，并通過哈希算法轉(zhuǎn)換成數(shù)組的下標(biāo)。

　　(2)、在通過數(shù)組下標(biāo)快速定位到某個(gè)位置上。重點(diǎn)理解如果這個(gè)位置上什么都沒有，則返回null。如果這個(gè)位置上有單向鏈表，那么它就會拿著參數(shù)K和單向鏈表上的每一個(gè)節(jié)點(diǎn)的K進(jìn)行equals，如果所有equals方法都返回false，則get方法返回null。如果其中一個(gè)節(jié)點(diǎn)的K和參數(shù)K進(jìn)行equals返回true，那么此時(shí)該節(jié)點(diǎn)的value就是我們要找的value了，get方法最終返回這個(gè)要找的value。

　　HashMap中的get()方法

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

　　getNode()方法

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //判斷數(shù)組不為null并且長度大于0，并且通過hash算出來的數(shù)組下標(biāo)的位置不為空，證明有數(shù)據(jù)
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //判斷數(shù)組的位置的key的hash和內(nèi)容是否等同與要查詢的數(shù)據(jù)
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                //相等的話直接返回
                return first;
            //判斷是否有下個(gè)節(jié)點(diǎn)
            if ((e = first.next) != null) {
                //判斷是否為為紅黑樹
                if (first instanceof TreeNode)
                    //進(jìn)行紅黑樹查詢操作
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //鏈表查詢操作
                do {
                    //循環(huán)鏈表，逐一判斷
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        //發(fā)現(xiàn)key的話就返回
                        return e;
                } while ((e = e.next) != null);
            }
        }
        //沒有查詢到返回null
        return null;
    }

　　四、HashMap常見面試題分析

　　為何HashMap的數(shù)組長度一定是2的次冪?

　　首先，HashMap的初始化的數(shù)組長度一定是2的n次的，每次擴(kuò)容仍是原來的2倍的話，就不會破壞這個(gè)規(guī)律，每次擴(kuò)容后，原數(shù)據(jù)都會進(jìn)行數(shù)據(jù)遷移，根據(jù)二進(jìn)制的計(jì)算，擴(kuò)容后數(shù)據(jù)要么在原來位置，要么在【原來位置+擴(kuò)容長度】，這樣就不需要重新hash，效率上更高。

　　HashMap中，如果想存入數(shù)據(jù)，首先它需要根據(jù)key的哈希值去定位落入哪個(gè)桶中

　　HashMap的做法，我總結(jié)的是，三步：>>>無符號右移、^異或、&與

　　具體是：拿著key的哈希值，先“>>>”無符號右移16位，然后“^”異或上key的哈希值，得到一個(gè)值，再拿著這個(gè)值去“&”上數(shù)組長度減一

　　最后得出一個(gè)數(shù)(如果數(shù)組長度是15的話，那這個(gè)數(shù)就是一個(gè)0-15之間的一個(gè)數(shù))，這個(gè)數(shù)就是得出的數(shù)組腳標(biāo)位置，也就是存入的桶的位置。

　　由上邊可以知道，定位桶的位置最后需要做一個(gè) “&” 與運(yùn)算，&完了得出一個(gè)數(shù)，就是桶的位置

　　知道了這些以后，再來說為什么HashMap的長度之所以一定是2的次冪?

　　至少有以下**兩個(gè)原因**：

　　1、HashMap的長度是2的次冪的話，可以讓**數(shù)據(jù)更散列更均勻的分布**，更充分的利用數(shù)組的空間

　　怎么理解呢?下面舉例子說一下如果不是2的次冪的數(shù)的話假設(shè)數(shù)組長度是一個(gè)奇數(shù)，那參與最后的&運(yùn)算的肯定就是偶數(shù)，那偶數(shù)的話，它二進(jìn)制的最后一個(gè)低位肯定是0，0做完&運(yùn)算得到的肯定也是0，那意味著&完后得到的數(shù)的最低位一定是0最低位一定是0的話，那說明一定是一個(gè)偶數(shù)，換句話說就是：&完得到的數(shù)一定是一個(gè)偶數(shù)，所以&完獲取到的腳標(biāo)永遠(yuǎn)是偶數(shù)位，那意味著奇數(shù)位的腳標(biāo)永遠(yuǎn)都沒值，**有一半的空間是浪費(fèi)的**奇數(shù)說完了，來說一下偶數(shù)，假設(shè)數(shù)組長度是一個(gè)偶數(shù)，比如6，那參與&運(yùn)算的就是55的二進(jìn)制 00000000 00000000 00000000 00000101發(fā)現(xiàn)任何一個(gè)數(shù)&上5，倒數(shù)第二低位永遠(yuǎn)是0，那就意味著&完以后，最起碼肯定得不出2或者3(這點(diǎn)剛開始不好理解，但是好好想一下就能明白)意味著第二和第三腳標(biāo)位肯定不會有值。

　　雖然偶數(shù)的話，不會像奇數(shù)那么夸張會有一半的腳標(biāo)位得不到，但是也總會有一些腳標(biāo)位得不到的。**所以不是2的次冪的話，不管是奇數(shù)還是偶數(shù)，就肯定注定了某些腳標(biāo)位永遠(yuǎn)是沒有值的，而某些腳標(biāo)位永遠(yuǎn)是沒有值的，就意味著浪費(fèi)空間，會讓數(shù)據(jù)散列的不充分，這對HashMap來說絕對是個(gè)災(zāi)難!**

　　2、HashMap的長度一定是2的次冪，還有另外一個(gè)原因，那就是在擴(kuò)容遷移的時(shí)候不需要再重新通過哈希定位新的位置了。擴(kuò)容后，元素新的位置，要么在原腳標(biāo)位，要么在原腳標(biāo)位+擴(kuò)容長度這么一個(gè)位置。

　　比如擴(kuò)容前長度是8，擴(kuò)容后長度是16
　　第一種情況：
　　擴(kuò)容前：
　　00000000 00000000 00000000 00000101
　　&00000000 00000000 00000000 00000111 8-1=7
　　-------------------------------------
　　101 ===== 5 原來腳標(biāo)位是5
　　擴(kuò)容后：
　　00000000 00000000 00000000 00000101
　　&00000000 00000000 00000000 00001111 16-1=15
　　-------------------------------------
　　101 ===== 5 擴(kuò)容后腳標(biāo)位是5(原腳標(biāo)位)
　　第二種情況：
　　擴(kuò)容前：
　　00000000 00000000 00000000 00001101
　　&00000000 00000000 00000000 00000111 8-1=7
　　-------------------------------------
　　101 ===== 5 原來腳標(biāo)位是5
　　擴(kuò)容后：
　　00000000 00000000 00000000 00001101
　　&00000000 00000000 00000000 00001111 16-1=15
　　-------------------------------------
　　1101 ===== 13 擴(kuò)容后腳標(biāo)位是13(原腳標(biāo)位+擴(kuò)容長度)
　　```

　　擴(kuò)容后到底是在原來位置還是在原腳標(biāo)位+擴(kuò)容長度的位置，主要是看新擴(kuò)容最左邊一個(gè)1對應(yīng)的上方數(shù)字是0還是1如果是0則擴(kuò)容后在原來位置，如果是1則擴(kuò)容后在原腳標(biāo)位+擴(kuò)容長度的位置HashMap源碼里擴(kuò)容也是這么做的。

　　總結(jié)來說，就是hash&(n-1)這個(gè)計(jì)算有關(guān)。如果不為n不為2的n次方的話，那轉(zhuǎn)換為二進(jìn)制情況下，n-1就會有某一位為0，那與hash做了&運(yùn)算后，該位置永遠(yuǎn)為0，那么計(jì)算出來的數(shù)組位置就永遠(yuǎn)會有某個(gè)下標(biāo)的數(shù)組位置是空的，也就是這個(gè)位置永遠(yuǎn)不會有值。

　　JDK1.8中HashMap的性能優(yōu)化

　　JDK1.8在1.7的基礎(chǔ)上對一些操作進(jìn)行了優(yōu)化。

　　| 不同 | JDK1.7 | JDK1.8 |

　　| ------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |

　　| 存儲結(jié)構(gòu) | 數(shù)組+鏈表 | 數(shù)組+鏈表+紅黑樹 |

　　| 初始化方式 | 單獨(dú)函數(shù)inflateTable() | 集成至擴(kuò)容方法resize() |

　　| hash值計(jì)算方式 | 擾動(dòng)處理=9次擾動(dòng)=4次位運(yùn)算+5次異或運(yùn)算 | 擾動(dòng)處理=2次擾動(dòng)=1次位運(yùn)算+1次異或運(yùn)算 |

　　| 存放數(shù)據(jù)規(guī)則 | 無沖突時(shí)，存放數(shù)組;沖突時(shí)存放鏈表 | 無沖突時(shí)，存放數(shù)組;沖突&鏈表長度<8:c存放單鏈表;沖突&鏈表長度 >8:樹化并存放紅黑樹 |

　　| 插入數(shù)據(jù)方式 | 頭插法(將原位置的數(shù)據(jù)移動(dòng)到后一位，再插入數(shù)據(jù)到該位置) | 尾插法 (直接插入鏈表尾部/紅黑樹) |

　　| 擴(kuò)容后存儲位置的計(jì)算方式 | 全部按照原來的方法進(jìn)行運(yùn)算(hashCode()->>擾動(dòng)函數(shù)->>(h&length-1)) | 按照擴(kuò)容后的規(guī)則計(jì)算(即擴(kuò)容后位置=原位置或原位置+舊容量) |

　　注意：JDK1.8里轉(zhuǎn)換為紅黑樹的時(shí)候，數(shù)組長度必須大于64，如果數(shù)組長度小于64，鏈表長度達(dá)到8的話，會進(jìn)行resize擴(kuò)容操作。

　　五、總結(jié)

　　 看到這里，我們已經(jīng)HashMap的源碼和實(shí)現(xiàn)有了清晰的理解，并且對它的構(gòu)造方法再到它的一個(gè)put數(shù)據(jù)和get數(shù)據(jù)的一個(gè)源碼解析，還有一些它里邊比較精妙和重要的一些方法也都探索清楚了，希望這些知識點(diǎn)可以在大家以后的面試中也能夠幫助到大家，斬獲一個(gè)心儀的offer。