java.util.BitSet是个很有趣的类,了解其内部实现对正确的使用非常重要。
对象构造:
private final static int ADDRESS_BITS_PER_WORD = 6;
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
private long[] words;
private static int wordIndex(int bitIndex) {
return bitIndex >> ADDRESS_BITS_PER_WORD;
}
private void initWords(int nbits) {
words = new long[wordIndex(nbits-1) + 1];
}
public BitSet() {
initWords(BITS_PER_WORD);
...
}
public BitSet(int nbits) {
...
initWords(nbits);
...
}
从贴出来的代码可以看出,long[] words这个数组是BitSet内部的关键实现,如果用户在构造函数中输入一个nbits变量,initWords方法会把这个数减1再右移6位加1,按照这个长度产生words数组的长度。
如果是输入的28,那么words的长度是1,
如果是输入的2^6 = 64,那么words的长度是1,
如果是输入的2^6+1 = 65,那么words的长度是2,
如果是输入的(2^6)*2 = 128,那么words的长度是2,
如果是输入的(2^6)*2+1 = 129,那么words的长度是3,
如果是输入的(2^6)*3 = 192,那么words的长度是3,
如果是输入的(2^6)*3+1 = 193,那么words的长度是4,
...
到这里已经很清楚了,BitSet用long类型表示“位图”,因为一个long是64bit,所以每个long表示64个数据,也就是说:数组中words中的第一个long表示0~63,第二个long表示64~127,第三个long表示128~191 ...
再看看get函数,检测某个数是否被置位:
public boolean get(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
...
int wordIndex = wordIndex(bitIndex);
return (wordIndex < wordsInUse)
&& ((words[wordIndex] & (1L << bitIndex)) != 0);
}
说明:
- wordsInUse变量主要用来控制long的容量,当set的数值过大时,BitSet类可以扩充words数组的长度,这一点和很多集合类(例如ArrayList,HashMap)是相似的
- 下面的语句值得注意:
1L << bitIndex
一般看到这条语句,会认为bitIndex如果超过64位,高位会溢出并得到返回0,事实上这个1会重新循环到低位,也就是说:
1L << 64 返回为1。
术语上这叫循环左移,经过检测java同样支持循环右移,运行下面的测试:
for (int i = 0;i < 70 ;i++)
System.out.println(i + " =" + (1 >> i));
在i为0,32,64时,(1 >> i)重新为1,搞位运算编程的需要注意这个陷阱。
注: 经过仔细考虑和试验,这里不是循环左移和循环右移,是一种比较“奇怪”的实现,回头写写这个问题。
BitSet类的一个缺陷:
size方法属于类的内部实现细节,导出成公有方法会让不了解实现细节的开发人员很迷惑。
public int size() {
return words.length * BITS_PER_WORD;
}
例如: 开发人员可能通过bitset.set(100)设置位,然后调用bitset.size(),如果不了解细节,很难理解为什么结果为128。
另外,如果实现位域(bit fields),应该考虑使用EnumSet,这一点可以参考Effective Java。
分享到:
相关推荐
解决no such provider: BC 问题所需的JAR 在jdk中的jre\lib\security修改java.security文件, security.provider.6=com.sun.security.sasl.Provider 下面添加...bcprov-jdk16-143.jar提供加密,解密,生成密钥对等方法
bcprov-jdk16-1.46.jar
开发工具 jdk-8u121-windows-i586开发工具 jdk-8u121-windows-i586开发工具 jdk-8u121-windows-i586开发工具 jdk-8u121-windows-i586开发工具 jdk-8u121-windows-i586开发工具 jdk-8u121-windows-i586开发工具 jdk-8...
bcprov-jdk15-133.jar bcprov-jdk15-133.jar
解决no such provider: BC 问题所需的JAR 在jdk中的jre\lib\security修改java.security文件, security.provider.6=com.sun.security.sasl.Provider 下面添加 ...在\jre\lib\ext中添加bcprov-jdk15-135.jar的jar包
bcprov-jdk16-143.jar提供加密,解密,生成密钥对等方法
json-lib-2.4-jdk15-sources.jar 是net.sf.json-lib-jdk15-2.4的源码文件
jdk-8u311-windows-x64.exe jdk-8u311-windows-x64.exe.zip jdk-8u311-windows-x64.exe jdk-8u311-windows-x64.exe.zip jdk-8u311-windows-x64.exe jdk-8u311-windows-x64.exe.zip jdk-8u311-windows-x64.exe jdk-8u...
java中对pdf文件操作,若要加密,需要这个包。 注意bcprov有许多版本,如bcprov-jdk16-145.jar, 请确认你的iText包的版本,本包适用于iText-2.0.1.jar版
jdk1.7 自带源码,并补充缺少sun包下的源码,补充源码来自1.7 openjdk
bcprov-jdk15on-1.64.jar bcprov-jdk15on-1.64-sources.jar bcprov-jdk15on-1.64-sources.jar.src.zip
openjdk-18 GA源码(jdk18-jdk-18-ga.zip)
openjdk-17 GA源码(jdk17-jdk-17-ga.tar.gz)
openjdk-18 GA源码(jdk18-jdk-18-ga.tar.gz)
slf4j-jdk14-1.7.7.jar
jdk1.8 jdk-8u5-windows-i586 32位官方正式版 jdk1.8 jdk-8u5-windows-i586 32位官方正式版
协同过滤推荐算法(java原生JDK实现-附源码地址).pdf协同过滤推荐算法(java原生JDK实现-附源码地址).pdf协同过滤推荐算法(java原生JDK实现-附源码地址).pdf协同过滤推荐算法(java原生JDK实现-附源码地址).pdf协同过滤...
bcprov-jdk16-141.jar
jdk-7-windows-x32 32为 JDK 7