場景描述
我們在日常學習和研發中，經常會接觸一些底層的源碼，有些同學在遇到位運算（提高系統的運行效率）實現的方法時，讀起來就有些吃力了，例如HashMap類中的tableSizeFor(int cap)方法，源代碼如下。
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 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;
}
當我們使用HashMap集合沒有指定初始容量時默認是16，如果給定了一個初始容量，tableSizeFor(int cap)方法會返回一個等于2的n次方的數來作為集合的初始容量。如果用戶給定的初始容量就等于2的n次方，那么返回的這個數就等于用戶給定值，否則將會返回一個大于且最接近用戶給定值的2的n次方的數來作為HashMap集合的初始容量。
案例演示
為了演示效果我這里使用反射的方式直接調用HashMap類里的tableSizeFor(int cap)方法測試容量的返回值。有對反射不是很理解的同學可以將源碼復制出來測試也可以在這個方法上添加斷點debug調試。
代碼示例
假設用戶給定初始容量 cap=7
import JAVA.lang.reflect.Method;
public class Demo {
public static void main(String[] args) throws Exception {
Class aClass = Class.forName("java.util.HashMap");
Object instance = aClass.newInstance();
Method tableSizeFor = aClass.getDeclaredMethod("tableSizeFor", int.class);
//設置目標類中的tableSizeFor方法可訪問
tableSizeFor.setAccessible(true);
//假設用戶給定的初始值時cap=7
Object invoke = tableSizeFor.invoke(instance, 7);
//打印返回值
System.out.println("tableSizeFor方法返回值："+invoke);
}
}
運行結果
F:softwareJavajdk1.8.0_121binjava.exe "-javaagent:D:IntelliJ IDEA 2019.1.4libidea_rt.jar=51583:D:IntelliJ IDEA 2019.1.4bin" -Dfile.encoding=UTF-8 -classpath F:softwareJavajdk1.8.0_121jrelibcharsets.jar;F:softwareJavajdk1.8.0_121jrelibdeploy.jar;F:softwareJavajdk1.8.0_121jrelibextaccess-bridge-64.jar;F:softwareJavajdk1.8.0_121jrelibextcldrdata.jar;F:softwareJavajdk1.8.0_121jrelibextDNSns.jar;F:softwareJavajdk1.8.0_121jrelibextjaccess.jar;F:softwareJavajdk1.8.0_121jrelibextjfxrt.jar;F:softwareJavajdk1.8.0_121jrelibextlocaledata.jar;F:softwareJavajdk1.8.0_121jrelibextnashorn.jar;F:softwareJavajdk1.8.0_121jrelibextsunec.jar;F:softwareJavajdk1.8.0_121jrelibextsunjce_provider.jar;F:softwareJavajdk1.8.0_121jrelibextsunmscapi.jar;F:softwareJavajdk1.8.0_121jrelibextsunpkcs11.jar;F:softwareJavajdk1.8.0_121jrelibextzipfs.jar;F:softwareJavajdk1.8.0_121jrelibjavaws.jar;F:softwareJavajdk1.8.0_121jrelibjce.jar;F:softwareJavajdk1.8.0_121jrelibjfr.jar;F:softwareJavajdk1.8.0_121jrelibjfxswt.jar;F:softwareJavajdk1.8.0_121jrelibjsse.jar;F:softwareJavajdk1.8.0_121jrelibmanagement-agent.jar;F:softwareJavajdk1.8.0_121jrelibplugin.jar;F:softwareJavajdk1.8.0_121jrelibresources.jar;F:softwareJavajdk1.8.0_121jrelibrt.jar;D:ideastudyspacespring_studyspring-studyspring-study-proxytargetclasses;E:softwareMavenRepositoryorgspringframeworkspring-webmvc3.2.0.RELEASEspring-webmvc-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-context3.2.0.RELEASEspring-context-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-aop3.2.0.RELEASEspring-aop-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-core3.2.0.RELEASEspring-core-3.2.0.RELEASE.jar;E:softwareMavenRepositorycommons-loggingcommons-logging1.1.1commons-logging-1.1.1.jar;E:softwareMavenRepositoryorgspringframeworkspring-web3.2.0.RELEASEspring-web-3.2.0.RELEASE.jar;E:softwareMavenRepositoryaopallianceaopalliance1.0aopalliance-1.0.jar;E:softwareMavenRepositoryorgspringframeworkspring-expression3.2.0.RELEASEspring-expression-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-beans3.2.0.RELEASEspring-beans-3.2.0.RELEASE.jar;E:softwareMavenRepositorycomalibabafastjson1.2.47fastjson-1.2.47.jar com.shiguang.service.Demo
tableSizeFor方法返回值：8
Process finished with exit code 0
此時我們設置初始容量cap=9
import java.lang.reflect.Method;
public class Demo {
public static void main(String[] args) throws Exception {
Class aClass = Class.forName("java.util.HashMap");
Object instance = aClass.newInstance();
Method tableSizeFor = aClass.getDeclaredMethod("tableSizeFor", int.class);
//設置目標類中的tableSizeFor方法可訪問
tableSizeFor.setAccessible(true);
//將初始值時變更為cap=9
Object invoke = tableSizeFor.invoke(instance, 9);
//打印返回值
System.out.println("tableSizeFor方法返回值："+invoke);
}
}
運行結果
F:softwareJavajdk1.8.0_121binjava.exe "-javaagent:D:IntelliJ IDEA 2019.1.4libidea_rt.jar=51640:D:IntelliJ IDEA 2019.1.4bin" -Dfile.encoding=UTF-8 -classpath F:softwareJavajdk1.8.0_121jrelibcharsets.jar;F:softwareJavajdk1.8.0_121jrelibdeploy.jar;F:softwareJavajdk1.8.0_121jrelibextaccess-bridge-64.jar;F:softwareJavajdk1.8.0_121jrelibextcldrdata.jar;F:softwareJavajdk1.8.0_121jrelibextdnsns.jar;F:softwareJavajdk1.8.0_121jrelibextjaccess.jar;F:softwareJavajdk1.8.0_121jrelibextjfxrt.jar;F:softwareJavajdk1.8.0_121jrelibextlocaledata.jar;F:softwareJavajdk1.8.0_121jrelibextnashorn.jar;F:softwareJavajdk1.8.0_121jrelibextsunec.jar;F:softwareJavajdk1.8.0_121jrelibextsunjce_provider.jar;F:softwareJavajdk1.8.0_121jrelibextsunmscapi.jar;F:softwareJavajdk1.8.0_121jrelibextsunpkcs11.jar;F:softwareJavajdk1.8.0_121jrelibextzipfs.jar;F:softwareJavajdk1.8.0_121jrelibjavaws.jar;F:softwareJavajdk1.8.0_121jrelibjce.jar;F:softwareJavajdk1.8.0_121jrelibjfr.jar;F:softwareJavajdk1.8.0_121jrelibjfxswt.jar;F:softwareJavajdk1.8.0_121jrelibjsse.jar;F:softwareJavajdk1.8.0_121jrelibmanagement-agent.jar;F:softwareJavajdk1.8.0_121jrelibplugin.jar;F:softwareJavajdk1.8.0_121jrelibresources.jar;F:softwareJavajdk1.8.0_121jrelibrt.jar;D:ideastudyspacespring_studyspring-studyspring-study-proxytargetclasses;E:softwareMavenRepositoryorgspringframeworkspring-webmvc3.2.0.RELEASEspring-webmvc-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-context3.2.0.RELEASEspring-context-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-aop3.2.0.RELEASEspring-aop-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-core3.2.0.RELEASEspring-core-3.2.0.RELEASE.jar;E:softwareMavenRepositorycommons-loggingcommons-logging1.1.1commons-logging-1.1.1.jar;E:softwareMavenRepositoryorgspringframeworkspring-web3.2.0.RELEASEspring-web-3.2.0.RELEASE.jar;E:softwareMavenRepositoryaopallianceaopalliance1.0aopalliance-1.0.jar;E:softwareMavenRepositoryorgspringframeworkspring-expression3.2.0.RELEASEspring-expression-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-beans3.2.0.RELEASEspring-beans-3.2.0.RELEASE.jar;E:softwareMavenRepositorycomalibabafastjson1.2.47fastjson-1.2.47.jar com.shiguang.service.Demo
tableSizeFor方法返回值：16
Process finished with exit code 0
這個時候返回的是16,2的4次方，也是大于且最接近9的2的n次方的數。那么tableSizeFor(int cap)方法是如何實現這個功能的呢？
代碼分析
首先我們先理解三個位運算符
“|” 或運算
舉例：
0001
0010
------------------或運算（對應二進制位同是0時等于0，只要有1等于1）
0011
“|=” 或等于
舉例：a |= b 就相當于 a = a | b
">>>" 無符號右移
舉例：1001 >>> 2
1001
---------- 1001無符號右移2位
0010 01
了解以上位運算符，我們便可以輕松明白這個方法的原理了
用戶指定HashMap初始數組容量 cap=9,進入tableSizeFor(int cap)方法
1 [執行代碼]：int n = cap - 1; n=8[最后我們再解釋為什么這里要cap-1]
2 [執行代碼]: n |= n >>> 1;
首先計算n >>> 1
------------------------------------------------------
二進制 十進制 描述
------------------------------------------------------
0000 1000 8 初始值
----------------------n >>> 1
0000 0100~~0~~ 4 結果
接著計算 n|n >>> 1
0000 1000 8
0000 0100 4
-------------------------------或運算
0000 1100 12 結果
3 [執行代碼]: n |= n >>> 2;[注意]此時的n=0000 1100
首先計算n >>> 2
0000 1100 12
-------------------------n >>> 2
0000 0011~~00~~ 3 結果
接著計算 n|n >>> 2
0000 1100 12
0000 0011 3
--------------------------------或運算
0000 1111 15 結果
4 [執行代碼]: n |= n >>> 4;[注意]此時的n=0000 1111
首先計算 n >>> 4
0000 1111 15
-------------------------n >>> 4
0000 0000~~1111~~ 0 結果
接著計算 n|n >>> 4
0000 1111 15
0000 0000 0
--------------------------------或運算
0000 1111 15
5 [執行代碼]: n |= n >>> 8;
0000 1111 15 結果
6 [執行代碼]: n |= n >>> 16;
0000 1111 15 結果
----------------------------------------------------
我們不難發現規律
start 0000 1000
end 0000 1111
初始值經過兩輪[無符號右移]加[或運算]后已將最高二進制位上的1后面的所有二進制位都變成了1
我們知道int類型占4個字節,也就是32位, 這樣任意一個int類型的數進來經過這5輪[無符號右移]加[或運算],最高二進制位上的1后面的所有二進制位都會變成1
接著我們執行這個方法的最后一行代碼
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
顯然此時我們的n=15,在[0,MAXIMUM_CAPACITY]這個區間內,所以
return n + 1;
系統設置HashMap集合的初始容量 cap=16;
那int n = cap - 1這行代碼又有什么用呢？
顯然這行代碼是為了防止用戶給定的初始值就等于2的n次方，如果用戶給定值是8，而tableSizeFor(int cap)方法里沒有cap - 1這行代碼，那么方法的返回值就變成了16，這樣就造成了不必要的內存浪費 。
