必知必會--HashMap容量細節

前言

HashMap作為Java中最常用的資料結構之一，在工作中使用HashMap的頻率和你遇見NullPointException一樣多。作為最常用的資料結構之一，我們都知道HashMap的容量為2次幂。當被問到為什麼是2次幂時，大家應該都能回答出來，是為了将結點均勻分散到數組中。當容量為2次幂能夠均勻分散結點，3次幂為什麼不能？HashMap中如何解決Hash碰撞？在HashMap的構造方法中可以傳入容量，如果傳入非2次幂怎麼辦？看完這篇文章你會解決其中的疑問。

ps:代碼來源于JDK1.8

正文

HashMap底層資料結構為數組+連結清單+紅黑樹。當我們向HashMap中插入一個對象，HashMap會通過Index映射算法得到該對象插入到數組的下标index。此時HashMap分辨這個位置有沒有值以及值類型。如果index沒有值，将目前對象放入目前位置。如果index有值，判斷對象的key是否與該值的key相等（key的hash值相等以及key本身相等），如果key相等則覆寫該值，如果key不相等，将對象插入該值的尾部（連結清單和紅黑樹不同的處理）。

Index映射算法

int index = (n - 1) & hash
           

對于為什麼采用&運算而不是%。1：&運算比%運算效率高很多；2：當n為2次幂，(n-1)&hash等同于hash%n。

如果HashMap的容量不是2次幂

假設目前HashMap的初始容量為17，即n等于17時。

1：n=17則n-1=16，16的二進制表示為0010000。

2：如果我現在向HashMap中插入兩個鍵值對，key1=A，Key2=B。假設通過Hash算法得知A的hash值為1010110，B的Hash值為0110000

3：分别算出key等于A，B時所映射的index

0010000  0010000

1010110  0110000

-------------------------

0010000  0010000

Hash值差别那麼大，得到的index值确實相同。這是由于&運算的特殊性導緻的，在二進制中&符号兩邊的元素隻要有一個為0，"&"操作執行後的結果就為0。是以當n=17時，計算出來的index隻有兩個值，0或者16。

如果我們向這個HashMap中儲存大量的鍵值對，所有的鍵值對都會堆積在資料的第0個或者第16個位置，而第1-15個位置會一直是null。

為什麼當n為二次幂時，可以讓鍵值對均勻分散，不會造成鍵值對堆積呢？

當n為二次幂，n-1的二進制表示中所有的低位均為1，如果n是16，n-1的二進制表示就是01111。這個時候通過（n-1）&hash得到的值能夠分散到0-15的每一個位置中，而且分散到每一個位置的機率都相同，不會發生鍵值對堆積在某幾個位置的現象。

講到這裡大家對HashMap的容量為什麼是二次幂應該有了解，為了讓鍵值對均勻分散到數組中。如果鍵值對隻是堆積在某幾個位置，這完全浪費了數組其餘位置的資源，同時還增加了HashMap擷取鍵值對的複雜度，對cpu資源也是一種浪費。

HashMap如果解決碰撞

說到Hash碰撞，來思考這一個問題，如果有很多key的hash值低位不變化，隻是在高位變化，這樣豈不是也會造成鍵值對的堆積。比如010110000，110110000，000010000。如果此時n等于32，計算出來的index都等于16。我們關注一下如何計算一個key的hash值。

/**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
           

在注釋中我們可以找到這個問題的答案

翻譯：計算key的hashcode值，同時将hash值的高位傳遞給低位。因為表的長度使用二次幂，是以僅在高位變化的散列總是發生沖突（已知的例子是在小的表中儲存連續整數的浮點鍵）。所有我們就利用了一個轉換，将高位向下轉移。這是一個在速度，效率，位移動上的交易。因為許多的Hash值是合理分布的（所有不利于傳遞）。并且我們使用紅黑樹去處理更多hash值的碰撞情況。所有我們用一些減少系統消耗并且廉價的方式去轉移一些位元組，以及可以利用高位的值來計算index值，否則高位不會參與到index的計算中。

為了避免Hash值低位不變，僅高位變化的情況，HashMap的設計者在設計Hash算法時利用^運算使得Hash值的高位與低位互相碰撞，讓Hash值的高位與低位同時參與index的計算中。

HashMap如何将任意值轉化為一個二次幂的值

我們發現在HashMap的構造方法中可以傳入容量這個參數。如果傳入的值是非二次幂，那是不是會造成鍵值對堆積的情況。

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    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);
    }
           

HashMap初始化會根據initialCapacity分為三種情況

情況1：如果傳入的initialCapacity小于0，抛異常。

情況2：如果initialCapacity大于最大容量，将最大容量賦予給initialCapacity。

最後3：調用tableSizeFor方法，将initialCapacity轉化為一個二次幂的值，然後賦予給threshold。HashMap初始化時，使用threshold作為HashMap數組的長度。

是以如果通過HashMap的構造函數傳入的容量是一個非二次幂，HashMap會通過tableSizeFor方法将這個值轉化為二次幂。

/**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }
           

這部分有點難了解，舉個例子說明

假設傳入的參數cap是一個非二次幂，cap=17

1.n-1=16。二次幂表示為0010000（一個1）

2.n |= n >>> 1。計算得到n等于0011000（兩個1）

3.n |= n >>> 2。計算得到n等于0011110（四個1）

4.n |= n >>> 4。計算得到n等于0011111（五個一）

5.n |= n >>> 8。計算得到n等于0011111（五個一）

6.n |= n >>> 16。計算得到n等于0011111（五個一）

7.n+1等于0100000，十進制等于32。

總結

1.當HashMap的數組長度為二次幂，能夠将鍵值對均勻分散到數組的每一個位置上。

2.index映射算法和%能夠達成一樣的效果，并且效率更高效。

3.Hash算法在設計時利用移位和異或運算符^來避免Hash碰撞。

4.如果通過HashMap的構造函數傳入的容量是一個非二次幂，HashMap會通過tableSizeFor方法将這個值轉化為二次幂的值。