場景描述
我們在日常學習和研發中，經常會接觸一些底層的原始碼，有些同學在遇到位運算（提高系統的運行效率）實作的方法時，讀起來就有些吃力了，例如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除錯，當然如果有想要學習反射簡單應用的同學歡迎訪問我的另一篇博客 Java 反射機制的應用，
代碼示例
假設用戶給定初始容量 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:\software\Java\jdk1.8.0_121\bin\java.exe "-javaagent:D:\IntelliJ IDEA 2019.1.4\lib\idea_rt.jar=51583:D:\IntelliJ IDEA 2019.1.4\bin" -Dfile.encoding=UTF-8 -classpath F:\software\Java\jdk1.8.0_121\jre\lib\charsets.jar;F:\software\Java\jdk1.8.0_121\jre\lib\deploy.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\access-bridge-64.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\cldrdata.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\dnsns.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\jaccess.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\jfxrt.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\localedata.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\nashorn.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\sunec.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\sunjce_provider.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\sunmscapi.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\sunpkcs11.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\zipfs.jar;F:\software\Java\jdk1.8.0_121\jre\lib\javaws.jar;F:\software\Java\jdk1.8.0_121\jre\lib\jce.jar;F:\software\Java\jdk1.8.0_121\jre\lib\jfr.jar;F:\software\Java\jdk1.8.0_121\jre\lib\jfxswt.jar;F:\software\Java\jdk1.8.0_121\jre\lib\jsse.jar;F:\software\Java\jdk1.8.0_121\jre\lib\management-agent.jar;F:\software\Java\jdk1.8.0_121\jre\lib\plugin.jar;F:\software\Java\jdk1.8.0_121\jre\lib\resources.jar;F:\software\Java\jdk1.8.0_121\jre\lib\rt.jar;D:\ideastudyspace\spring_study\spring-study\spring-study-proxy\target\classes;E:\software\MavenRepository\org\springframework\spring-webmvc\3.2.0.RELEASE\spring-webmvc-3.2.0.RELEASE.jar;E:\software\MavenRepository\org\springframework\spring-context\3.2.0.RELEASE\spring-context-3.2.0.RELEASE.jar;E:\software\MavenRepository\org\springframework\spring-aop\3.2.0.RELEASE\spring-aop-3.2.0.RELEASE.jar;E:\software\MavenRepository\org\springframework\spring-core\3.2.0.RELEASE\spring-core-3.2.0.RELEASE.jar;E:\software\MavenRepository\commons-logging\commons-logging\1.1.1\commons-logging-1.1.1.jar;E:\software\MavenRepository\org\springframework\spring-web\3.2.0.RELEASE\spring-web-3.2.0.RELEASE.jar;E:\software\MavenRepository\aopalliance\aopalliance\1.0\aopalliance-1.0.jar;E:\software\MavenRepository\org\springframework\spring-expression\3.2.0.RELEASE\spring-expression-3.2.0.RELEASE.jar;E:\software\MavenRepository\org\springframework\spring-beans\3.2.0.RELEASE\spring-beans-3.2.0.RELEASE.jar;E:\software\MavenRepository\com\alibaba\fastjson\1.2.47\fastjson-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:\software\Java\jdk1.8.0_121\bin\java.exe "-javaagent:D:\IntelliJ IDEA 2019.1.4\lib\idea_rt.jar=51640:D:\IntelliJ IDEA 2019.1.4\bin" -Dfile.encoding=UTF-8 -classpath F:\software\Java\jdk1.8.0_121\jre\lib\charsets.jar;F:\software\Java\jdk1.8.0_121\jre\lib\deploy.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\access-bridge-64.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\cldrdata.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\dnsns.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\jaccess.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\jfxrt.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\localedata.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\nashorn.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\sunec.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\sunjce_provider.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\sunmscapi.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\sunpkcs11.jar;F:\software\Java\jdk1.8.0_121\jre\lib\ext\zipfs.jar;F:\software\Java\jdk1.8.0_121\jre\lib\javaws.jar;F:\software\Java\jdk1.8.0_121\jre\lib\jce.jar;F:\software\Java\jdk1.8.0_121\jre\lib\jfr.jar;F:\software\Java\jdk1.8.0_121\jre\lib\jfxswt.jar;F:\software\Java\jdk1.8.0_121\jre\lib\jsse.jar;F:\software\Java\jdk1.8.0_121\jre\lib\management-agent.jar;F:\software\Java\jdk1.8.0_121\jre\lib\plugin.jar;F:\software\Java\jdk1.8.0_121\jre\lib\resources.jar;F:\software\Java\jdk1.8.0_121\jre\lib\rt.jar;D:\ideastudyspace\spring_study\spring-study\spring-study-proxy\target\classes;E:\software\MavenRepository\org\springframework\spring-webmvc\3.2.0.RELEASE\spring-webmvc-3.2.0.RELEASE.jar;E:\software\MavenRepository\org\springframework\spring-context\3.2.0.RELEASE\spring-context-3.2.0.RELEASE.jar;E:\software\MavenRepository\org\springframework\spring-aop\3.2.0.RELEASE\spring-aop-3.2.0.RELEASE.jar;E:\software\MavenRepository\org\springframework\spring-core\3.2.0.RELEASE\spring-core-3.2.0.RELEASE.jar;E:\software\MavenRepository\commons-logging\commons-logging\1.1.1\commons-logging-1.1.1.jar;E:\software\MavenRepository\org\springframework\spring-web\3.2.0.RELEASE\spring-web-3.2.0.RELEASE.jar;E:\software\MavenRepository\aopalliance\aopalliance\1.0\aopalliance-1.0.jar;E:\software\MavenRepository\org\springframework\spring-expression\3.2.0.RELEASE\spring-expression-3.2.0.RELEASE.jar;E:\software\MavenRepository\org\springframework\spring-beans\3.2.0.RELEASE\spring-beans-3.2.0.RELEASE.jar;E:\software\MavenRepository\com\alibaba\fastjson\1.2.47\fastjson-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位
001001
了解以上位運算子，我們便可以輕松明白這個方法的原理了
用戶指定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，這樣就造成了不必要的記憶體浪費 ，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/272474.html
標籤：java
上一篇：Java之資料型別與運算子詳解