`

java.util.BitSet 分析

 
阅读更多

我们知道bit-map在大数据处理方面有着很大的用途,比如排序,去重等。

JDK 从1.0开始就提供了 java.util.BitSet 来对bit-map的支持。BitSet的set,get操作主要是通过 “位运算” 进行的。

BitSet的核心是一个 long的数组:

  1. /* 
  2.      * BitSets are packed into arrays of "words."  Currently a word is 
  3.      * a long, which consists of 64 bits, requiring 6 address bits. 
  4.      * The choice of word size is determined purely by performance concerns. 
  5.      */  
  6.     private final static int ADDRESS_BITS_PER_WORD = 6;  
  7.     private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;  
  8.     private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;  
  9.   
  10.     /* Used to shift left or right for a partial word mask */  
  11.     private static final long WORD_MASK = 0xffffffffffffffffL;  
  12.   
  13.     /** 
  14.      * The internal field corresponding to the serialField "bits". 
  15.      */  
  16.     private long[] words;  
  17.   
  18.     /** 
  19.      * The number of words in the logical size of this BitSet. 
  20.      */  
  21.     private transient int wordsInUse = 0;  
  22.   
  23.     /** 
  24.      * Whether the size of "words" is user-specified.  If so, we assume 
  25.      * the user knows what he's doing and try harder to preserve it. 
  26.      */  
  27.     private transient boolean sizeIsSticky = false;  

从bit的角度看,words 应该是一个 二维的bit数据, bit [ ] [64] word, 当然 JDK中没有 bit 这个基本的数据类型。但是JDK提供了丰富的位运算符。每个bit 只有两个值 0 和1(ture 和false)。

bit-map的典型应用场景(伪码表示):

有一个 bit数组 bit [ ] bArray = new bit [ 1024 ]。 要对若干非负整数进行排序,例如:{ 2, 5, 78, 58, 11}。使用bit-map的做法是:

  1. bArray[2] = 1;  
  2. bArray[5] = 1;  
  3. bArray[78] = 1;  
  4. bArray[58] = 1;  
  5. bArray[11] = 1;  

然后顺序遍历bArray就行了。

同样对于BitSet的方法一样,只不过要调用它的set方法,源码如下:

  1. /** 
  2.      * Sets the bit at the specified index to {@code true}. 
  3.      * 
  4.      * @param  bitIndex a bit index 
  5.      * @throws IndexOutOfBoundsException if the specified index is negative 
  6.      * @since  JDK1.0 
  7.      */  
  8.     public void set(int bitIndex) {  
  9.         if (bitIndex < 0)  
  10.             throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);  
  11.   
  12.         int wordIndex = wordIndex(bitIndex);  
  13.         expandTo(wordIndex);  
  14.   
  15.         words[wordIndex] |= (1L << bitIndex); // Restores invariants  
  16.   
  17.         checkInvariants();  
  18.     }  

如果将 long [ ] words 理解成 bit [ ] [ 64 ] words的话 

第一步,先算出一维(wordIndex(int bitIndex) 方法)

  1. /** 
  2.      * Given a bit index, return word index containing it. 
  3.      */  
  4.     private static int wordIndex(int bitIndex) {  
  5.         return bitIndex >> ADDRESS_BITS_PER_WORD;  
  6.     }  

notice: ADDRESS_BITS_PER_WORD = 6.

第二步,使用位运算对对应的bit进行赋值为1, words[ wordIndex ] |= (1L << bitIndex).

BitSet的get方法和Set方法一样,先确定一维,再通过位运算得到二维中对应的值。

是不是感觉很美妙,通过long数组 再加上 位运算 可以模拟出 bit数组。当然,我们也可以使用int数组或者double行数据来构造 bit数组

分享到:
评论

相关推荐

    java.util包

    Java提供日期(Data)类、日历(Calendar)类,随机数(Random)类,堆栈(Stack)、向量(Vector) 、位集合(Bitset)以及哈希表(Hashtable)等类来表示相应的数据结构

    java.util包总结

    Java.util包是Java标准库中的核心包之一,它包含了大量用于日常编程的工具类和接口。这个包在Java 2版本中得到了显著增强,引入了许多重要的数据结构和算法,为Java程序员提供了更丰富的功能。 首先,Java.util包中...

    JBuider第七章:Java.util包.rar

    Java.util包是Java编程语言中的核心包之一,它包含了大量用于日常编程的类和接口,是Java程序员必备的知识点。本教程重点讲解了Java.util包中的主要组件和使用方法,旨在帮助初学者深入理解并熟练运用这个包。 1. *...

    java的.awt包和java.util包的区别

    ### Java的.awt包和.java.util包的区别 #### Java.util包详解 Java.util包是一个非常重要的标准库之一,其中包含了大量有用的类和接口,为开发者提供了丰富的功能。此包中的类和接口可以分为以下几大类别: 1. **...

    实用工具类库java.util

    介绍Java的实用工具类库java.util包。在这个包中,Java提供了一些实用的方法和数据结构。例如,Java提供日期(Data)类、日历(Calendar)类来产生和获取日期及时间,提供随机数(Random)类产生各种类型的随机数,还提供...

    java_util 工具包

    ### Java_util 工具包详解 #### 一、引言 `java.util`包作为Java标准库中的一个重要组成部分,提供了大量的实用工具类和接口,旨在简化开发者在处理数据结构、日期时间、事件处理等方面的工作。这个包包含了如日期...

    Java.util包简介并教您如何开发应用之二

    例如,Java提供日期(Data)类、日历(Calendar)类来产生和获取日期及时间,提供随机数(Random)类产生各种类型的随机数,还提供了堆栈(Stack)、向量(Vector)、位集合(Bitset)以及哈希表(Hashtable)等类来表示相应的数据...

    Java的实用工具类库util包详细讲解

    位集合类 BitSet 是 Java.util 包中一个非常实用的类,提供了一些方法来处理位集合数据结构。 BitSet 类中有两个常用的方法: (1) public BitSet():创建一个位集合对象。 (2) public void set(int bitIndex):...

    java-util包资料

    以上只是`java.util`包中部分关键知识点的概述,实际上,该包还包括其他如排序算法(`Comparator`)、位集(`BitSet`)、事件模型(`EventObject`)等众多内容。熟练掌握这些工具类和接口,对于编写高质量的Java程序...

    java util包使用详解

    Java util包中还提供了许多其它有用的类,例如 BitSet类、 Dictionary类、 EventObject类、 ResourceBundle类、 StringTokenizer类等等。 Java util包提供了许多实用的工具类和数据结构,能够帮助开发者快速地编写...

    JAVA--基础知识[归纳].pdf

    Java编程语言的基础知识涵盖了许多方面,这里我们主要关注的是`java.util`包,这是一个非常重要的工具类库,提供了丰富的数据结构和实用方法。在Java开发中,`java.util`包几乎无处不在,它包含了处理日期时间、...

    浅谈Java BitSet使用场景和代码示例

    在 Java 中,BitSet 的实现位于 java.util 包中。BitSet 的底层实现是使用 long 数组作为内部存储结构的,所以 BitSet 的大小为 long 类型大小(64 位)的整数倍。它有两个构造函数:BitSet() 和 BitSet(int nbits)...

    Z值填充.zip

    bitSet.set(bitSet.size() - 448 + i, ((lengthInBits &gt;&gt; i) & 1) == 1); } // 将BitSet转换回字节数组 ByteBuffer buffer = ByteBuffer.allocate((bitSet.size() + 7) / 8); buffer.put(bitSet.toByteArray...

    java常用类库手册

    JavaUtil包是Java类库中的一个非常重要的组成部分,它提供了许多实用的方法和数据结构。 ##### java.util包基本层次结构 java.util包包含了许多重要的类和接口,如BitSet、Calendar、Date、Dictionary、...

    (java)指定范围的,不重复的随机数

    为了保证生成的随机数不重复,我们可以使用`java.util.HashSet`或`java.util.TreeSet`。这两个集合不允许存储重复元素,因此当我们尝试添加一个已经存在的元素时,它会被自动忽略。 4. **填充集合**: 我们可以先...

    SMS短信平台代码

    JAVA提供了`java.util.BitSet`和`java.nio.charset.CharsetEncoder`类来处理这些操作。 3. **短信协议支持**:SMS平台需要支持SMPP(Short Message Peer-to-Peer)协议,这是短信服务提供商与短信网关之间通信的...

    最最适用的java数据结构全集

    15. **位向量(Bitset)**:`java.util.BitSet`类提供了位操作,用于高效地处理大量的布尔值,节省内存空间。 掌握这些Java数据结构和它们的实现,不仅能够编写更高效的代码,还能帮助你理解和解决复杂的编程问题。...

Global site tag (gtag.js) - Google Analytics