HashMap源碼閱讀

1. 什么是HashMap景馁？

image.png

1.1 map的定義

首先你要知道什么是map乘盼，map就是用于存儲(chǔ)鍵值對(duì)（<key,value>）的集合類(lèi)头朱，也可以說(shuō)是一組鍵值對(duì)的映射勘高。

1.2 Map的特點(diǎn)

1.沒(méi)有重復(fù)的 key（一方面帝嗡，key用set保存晶通，所以key必須是唯一，無(wú)序的哟玷；另一方面狮辽，map的取值基本上是通過(guò)key來(lái)獲取value，如果有兩個(gè)相同的key巢寡，計(jì)算機(jī)將不知道到底獲取哪個(gè)對(duì)應(yīng)值喉脖；這時(shí)候有可能會(huì)問(wèn)，那為什么我編程時(shí)候可以用put（）方法傳入兩個(gè)key值相同的鍵值對(duì)抑月？那是因?yàn)樵创a中树叽，傳入key值相同的鍵值對(duì)，將作為覆蓋處理）

2.每個(gè) key 只能對(duì)應(yīng)一個(gè) value, 多個(gè) key 可以對(duì)應(yīng)一個(gè) value（這就是映射的概念谦絮，最經(jīng)典的例子就是射箭题诵，一排射手，一排箭靶层皱，一個(gè)射手只能射中一個(gè)箭靶性锭，而每個(gè)箭靶可能被不同射手射中。這里每個(gè)射手只有一根箭叫胖，不存在三箭齊發(fā)還都中靶這種騷操作草冈。將射手和射中的靶子連線(xiàn)，這根線(xiàn)加射手加靶子就是一個(gè)映射）

3.key,value 都可以是任何引用類(lèi)型（包括 null）的數(shù)據(jù)（只能是引用類(lèi)型）

1.3 HashMap

HashMap在JDK1.8中是基于（數(shù)組+鏈表）+紅黑樹(shù)的一個(gè)Map容器

2. HashMap解讀

2.1 靜態(tài)屬性（默認(rèn)值）

   /**
     *  如果沒(méi)有給容量初始化值得話(huà)瓮增，就用這個(gè)作為初始化值怎棱，16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * Map容量最大值
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     *  負(fù)載因子，用來(lái)判斷擴(kuò)容量的
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 當(dāng)Node的長(zhǎng)度達(dá)到8的時(shí)候就轉(zhuǎn)換成紅黑樹(shù)
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 當(dāng)Node的長(zhǎng)度被remove到6的時(shí)候就從紅黑樹(shù)轉(zhuǎn)成鏈表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

   /**
    * 容器可以樹(shù)化的最小容量绷跑。
    *（否則拳恋，如果bin中的節(jié)點(diǎn)太多，則會(huì)調(diào)整表的大小你踩。）
    * 應(yīng)至少為4 * TREEIFY_THRESHOLD诅岩，以避免調(diào)整
    * 大小和樹(shù)化閾值之間的沖突讳苦。
    */
    static final int MIN_TREEIFY_CAPACITY = 64;

2.2 HashMap實(shí)例的屬性

    /**
     * HashMap底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)Node數(shù)組，可以是紅黑樹(shù)樹(shù)吩谦，也可以是鏈表鸳谜，默認(rèn)是鏈表
     */
    transient Node<K,V>[] table;

    /**
     * Map中存儲(chǔ)元素的數(shù)量
     */
    transient int size;

    /**
     * 要調(diào)整大小的下一個(gè)大小值（容量*加載因子）
     * 此外，如果尚未分配表數(shù)組式廷，則此字段保存初始數(shù)組容量
     * put一個(gè)元素進(jìn)Map的時(shí)候咐扭，都會(huì)判斷添加后的size和這個(gè)
     * threshold比較，如果大于了這個(gè)值滑废，就擴(kuò)容蝗肪。
     */
    int threshold;

    /**
     * 哈希表的加載因子
     * 這個(gè)就是為了計(jì)算出threshold的，下面會(huì)說(shuō)
     */
    final float loadFactor;

2.3 HashMap初始化

HashMap總共定義了四個(gè)構(gòu)造函數(shù)蠕趁。

2.3.1 // 傳入初始化容量薛闪，和負(fù)載因子進(jìn)行初始化

    // 傳入初始化容量，和負(fù)載因子
    public HashMap(int initialCapacity, float loadFactor) {
        // 如果初始化容量小于0俺陋，則拋出異常豁延。
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 如果大于最大的容量，就設(shè)置成最大容量腊状。
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 如果負(fù)載因子小于0诱咏，或者不是個(gè)數(shù)字則，拋出異常缴挖。
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // 這里進(jìn)行第一次計(jì)算初始化容量
        this.threshold = tableSizeFor(initialCapacity);
    }

剛剛上面看到了第一次計(jì)算容量用的是tableSizeFor(); 這個(gè)方法袋狞，我們現(xiàn)在來(lái)看一下這個(gè)方法。

   /**
     * 返回的大小一定是2的冪
     * 意思就是映屋，你傳的初始化容量大小苟鸯，取比這個(gè)數(shù)最大的2的n次方的值
     * 打比方：
     * 傳1那么容量就是2的0次方，那么容量就是1
     * 傳入的是2那么就是2的1次方秧荆，那么容量就是2
     * 傳入的是3那么就是2的2次方倔毙，那么容量就是4
     * 傳入的是4那么就是2的3次方，那么容量就是8 
     */
    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;
    }

2.3.2 傳一個(gè)初始化容量大小初始化

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

2.3.3 默認(rèn)構(gòu)造函數(shù)

 public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }

2.3.4 傳一個(gè)Map進(jìn)行初始化

剛剛介紹的三種構(gòu)造函數(shù)可以看出來(lái)乙濒，都沒(méi)有給HashMap進(jìn)行初始化，但是這個(gè)構(gòu)造函數(shù)卵蛉，會(huì)給出初始化颁股。

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
// 將傳入的Map的值都添加進(jìn)目前初始化的HashMap
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
            // 傳入的Map大小
            int s = m.size();
            if (s > 0) {
                    if (table == null) { 
                        // 如果table是空的就計(jì)算容量，容量大小就是 (size/loadFactor) + 1.0F
                        float ft = ((float)s / loadFactor) + 1.0F;
                        int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                        // 如果容量大于了擴(kuò)容標(biāo)準(zhǔn)傻丝，就計(jì)算新的擴(kuò)容的標(biāo)準(zhǔn)大小甘有。
                        if (t > threshold)
                              threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                // 如果size大于了擴(kuò)容標(biāo)準(zhǔn)，調(diào)用進(jìn)行resize()擴(kuò)容
                resize();
            // 循環(huán)put進(jìn)去
            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);
            }
        }
    }

從上面可以看到主要是兩個(gè)方法葡缰，resize(); 擴(kuò)容方法亏掀，和putVal(); put一個(gè)元素到容器的方法忱反，我們繼續(xù)來(lái)看看putVal();方法
JDK1.7是通過(guò)hash%cap得出存儲(chǔ)數(shù)據(jù)位置，就是hash值模上數(shù)組length得出位置
JDK1.8是通過(guò)容量大小與key值進(jìn)行hash的算法在開(kāi)始的時(shí)候只會(huì)對(duì)低位進(jìn)行計(jì)算滤愕，雖然容量的2進(jìn)制高位一開(kāi)始都是0温算，但是key的2進(jìn)制高位通常是有值的，因此先在hash方法中將key的hashCode右移16位在與自身異或间影，使得高位也可以參與hash注竿，更大程度上減少了碰撞率。先是jdk1.8的圖解