Java源碼解析HashMap的tableSizeFor函數(shù)

aka，HashMap的容量大小必須為2的指數(shù)，即16，32，64，128這樣的值。那么，在構(gòu)造函數(shù)中，如果調(diào)用者指定了HashMap的初始大小不是2的指數(shù)，那么，HashMap的tableSizeFor函數(shù)，會計(jì)算一個大于或等于給定參數(shù)的2的指數(shù)的值。先來看一下tableSizeFor函數(shù)的源碼，如下

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

這里采用的計(jì)算方法不太常見。先是對cap-1，然后一直進(jìn)行右移操作，最后根據(jù)n和MAXIMUM_CAPCITY的大小關(guān)系，返回一個值。這究竟是如何實(shí)現(xiàn)找到一個大于或等于cap的2的指數(shù)的值呢？

首先需要解釋一下>>>符號。>>>是無符號右移操作，即，右移后，高位補(bǔ)0. 例如二進(jìn)制的11000101，>>>1后，得到01100010，即不關(guān)心符號位，右移后，高位直接補(bǔ)充0. 

還有一個符號是|=，例如n |= n>>>1，這個其實(shí)可以翻譯為n = n | n>>>1，| 是位或操作，即兩個數(shù)字按位進(jìn)行或操作，即，某一位上，只有一個數(shù)字的該位為1，該位的結(jié)果即為1.

說清楚了兩個符號的含義，下面我們開始解釋算法的過程。

函數(shù)一開始，把cap -1 賦值給n。這里我們先按住不說，稍后回頭解釋。接下來就是對n的四次變換。舉個例，對于

01010000

這個值來說，n>>>1即可得到

00101000

兩個數(shù)字位或后，得到

01111000

可以這么來看這個事情，最開始的n，總有它的最高位為1. 右移1位后，與n進(jìn)行位或操作，則結(jié)果的最高位和次高位都為1了，也就是得到了2個1，而且是高位的2位都為1了。

那么這時再對n進(jìn)行n>>>2，再和n進(jìn)行位或操作，即可得到4個1. 依此類推，n |= n>>>4，即可得到8個1。然后n |= n>>>8，即可得到16個1。然后 n |= n>>>16，即可得到32個1. 當(dāng)然，后面幾步得到多少個1，得需要n的初始值足夠大才可以。否則，n右移后可能就位0了，那么在進(jìn)行位或操作，也只是上一步的值而已。

通過上面的分析，可以知道，進(jìn)行完n的四次右移然后位或操作后，得到的其實(shí)是n的所有為都為1的一個值。那么最后，返回的時候，取的n + 1，那么即可得到一個比n大的2的指數(shù)的值。

那么回過頭來看看第一步 n = cap -1就明白了，這里是為了處理當(dāng)cap本身即是2的指數(shù)時的情況。

因?yàn)橛?jì)算機(jī)進(jìn)行移位和位或操作十分迅速，所以，這個函數(shù)的執(zhí)行效率其實(shí)很高。tableSizeFor函數(shù)就是這樣快速找到了一個大于等于cap的2的指數(shù)的值。

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，謝謝大家對億速云的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接