Java源碼解析HashMap的tableSizeFor函數(shù)
aka,HashMap的容量大小必須為2的指數(shù),即16,32,64,128這樣的值。那么,在構(gòu)造函數(shù)中,如果調(diào)用者指定了HashMap的初始大小不是2的指數(shù),那么,HashMap的tableSizeFor函數(shù),會計算一個大于或等于給定參數(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; }
這里采用的計算方法不太常見。先是對cap-1,然后一直進行右移操作,最后根據(jù)n和MAXIMUM_CAPCITY的大小關系,返回一個值。這究竟是如何實現(xiàn)找到一個大于或等于cap的2的指數(shù)的值呢?
首先需要解釋一下>>>符號。>>>是無符號右移操作,即,右移后,高位補0. 例如二進制的11000101,>>>1后,得到01100010,即不關心符號位,右移后,高位直接補充0.
還有一個符號是|=,例如n |= n>>>1,這個其實可以翻譯為n = n | n>>>1,| 是位或操作,即兩個數(shù)字按位進行或操作,即,某一位上,只有一個數(shù)字的該位為1,該位的結(jié)果即為1.
說清楚了兩個符號的含義,下面我們開始解釋算法的過程。
函數(shù)一開始,把cap -1 賦值給n。這里我們先按住不說,稍后回頭解釋。接下來就是對n的四次變換。舉個例,對于
01010000
這個值來說,n>>>1即可得到
00101000
兩個數(shù)字位或后,得到
01111000
可以這么來看這個事情,最開始的n,總有它的最高位為1. 右移1位后,與n進行位或操作,則結(jié)果的最高位和次高位都為1了,也就是得到了2個1,而且是高位的2位都為1了。
那么這時再對n進行n>>>2,再和n進行位或操作,即可得到4個1. 依此類推,n |= n>>>4,即可得到8個1。然后n |= n>>>8,即可得到16個1。然后 n |= n>>>16,即可得到32個1. 當然,后面幾步得到多少個1,得需要n的初始值足夠大才可以。否則,n右移后可能就位0了,那么在進行位或操作,也只是上一步的值而已。
通過上面的分析,可以知道,進行完n的四次右移然后位或操作后,得到的其實是n的所有為都為1的一個值。那么最后,返回的時候,取的n + 1,那么即可得到一個比n大的2的指數(shù)的值。
那么回過頭來看看第一步 n = cap -1就明白了,這里是為了處理當cap本身即是2的指數(shù)時的情況。
因為計算機進行移位和位或操作十分迅速,所以,這個函數(shù)的執(zhí)行效率其實很高。tableSizeFor函數(shù)就是這樣快速找到了一個大于等于cap的2的指數(shù)的值。
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值,謝謝大家對腳本之家的支持。如果你想了解更多相關內(nèi)容請查看下面相關鏈接
相關文章
Java 使用openoffice進行word轉(zhuǎn)換為pdf的方法步驟
這篇文章主要介紹了Java 使用openoffice進行word轉(zhuǎn)換為pdf的方法步驟,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-04-04Springboot整合Shiro實現(xiàn)登錄與權(quán)限校驗詳細解讀
本文給大家介紹Springboot整合Shiro的基本使用,Apache?Shiro是Java的一個安全框架,Shiro本身無法知道所持有令牌的用戶是否合法,我們將整合Shiro實現(xiàn)登錄與權(quán)限的驗證2022-04-04Spring Boot整合Spring Security的示例代碼
這篇文章主要介紹了Spring Boot整合Spring Security的示例代碼,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2018-04-04簡單的理解java集合中的HashSet和HashTree幾個重寫方法
這篇文章主要介紹了簡單的理解java集合中的HashSet和HashTree幾個重寫方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-10-10