`
jaesonchen
  • 浏览: 309830 次
  • 来自: ...
社区版块
存档分类
最新评论

BitSet的源码研究

 
阅读更多

这几天看Bloom Filter,因为在java中,并不能像C/C++一样直接操纵bit级别的数据,所以只能另想办法替代:

1)使用整数数组来替代;

2)使用BitSet;

BitSet实际是由“二进制位”构成的一个Vector。如果希望高效率地保存大量“开-关”信息,就应使用BitSet。它只有从尺寸的角度看才有意义;如果希望的高效率的访问,那么它的速度会比使用一些固有类型的数组慢一些。

BitSet的大小与实际申请的大小并不一定一样,BitSet的size方法打印出的大小一定是64的倍数,这与它的实际申请代码有关,假设以下面的代码实例化一个BitSet:

BitSet set = new BitSet(129);

我们来看看实际是如何申请的:申请源码如下:

/**
    * Creates a bit set whose initial size is large enough to explicitly
    * represent bits with indices in the range <code>0</code> through
    * <code>nbits-1</code>. All bits are initially <code>false</code>.
    *
    * @param     nbits   the initial size of the bit set.
    * @exception NegativeArraySizeException if the specified initial size
    *               is negative.
    */
   public BitSet(int nbits) {
   // nbits can't be negative; size 0 is OK
   if (nbits < 0)
       throw new NegativeArraySizeException("nbits < 0: " + nbits);
 
   initWords(nbits);
   sizeIsSticky = true;
   }
 
   private void initWords(int nbits) {
   words = new long[wordIndex(nbits-1) + 1];
   }

实际的空间是由initWords方法控制的,在这个方法里面,我们实例化了一个long型数组,那么wordIndex又是干嘛的呢?其源码如下:

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

这里涉及到一个常量ADDRESS_BITS_PER_WORD,先解释一下,源码中的定义如下:

private final static int ADDRESS_BITS_PER_WORD = 6;

那么很明显2^6=64,所以,当我们传进129作为参数的时候,我们会申请一个long[(129-1)>>6+1]也就是long[3]的数组,到此就很明白了,实际上替代办法的1)和2)是很相似的:都是通过一个整数(4个byte或者8个byte)来表示一定的bit位,之后,通过与十六位进制的数进行and,or,~等等操作进行Bit位的操作。

 

接下来讲讲其他比较重要的方法

1)set方法,源码如下:

/**
    * Sets the bit at the specified index to <code>true</code>.
    *
    * @param     bitIndex   a bit index.
    * @exception IndexOutOfBoundsException if the specified index is negative.
    * @since     JDK1.0
    */
   public void set(int bitIndex) {
   if (bitIndex < 0)
       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
 
       int wordIndex = wordIndex(bitIndex);
   expandTo(wordIndex);
 
   words[wordIndex] |= (1L << bitIndex); // Restores invariants
 
   checkInvariants();
   }

这个方法将bitIndex位上的值由false设置为true,解释如下:

我们设置的时候很明显是在改变long数组的某一个元素的值,首先需要确定的是改变哪一个元素,其次需要使用与或操作改变这个元素,在上面的代码中,首先将bitIndex>>6,这样就确定了是修改哪一个元素的值,其次这里涉及到一个expandTo方法,我们先跳过去,直接看代码:

words[wordIndex] |= (1L << bitIndex); // Restores invariants

 这里不是很好理解,要注意:需要注意的是java中的移位操作会模除位数,也就是说,long类型的移位会模除64。例如对long类型的值左移65位,实际是左移了65%64=1位。所以这行代码就等于:

int transderBits = bitIndex % 64;
words[wordsIndex] |= (1L << transferBits);

上面这样写就很清楚了。

与之相对的一个方法是:

 

/**
    * Sets the bit specified by the index to <code>false</code>.
    *
    * @param     bitIndex   the index of the bit to be cleared.
    * @exception IndexOutOfBoundsException if the specified index is negative.
    * @since     JDK1.0
    */
   public void clear(int bitIndex) {
   if (bitIndex < 0)
       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
 
   int wordIndex = wordIndex(bitIndex);
   if (wordIndex >= wordsInUse)
       return;
 
   words[wordIndex] &= ~(1L << bitIndex);
 
   recalculateWordsInUse();
   checkInvariants();
   }

 

这段代码理解上与set大同小异,主要是用来设置某一位上的值为false的。

上面有个方法,顺带着解释一下:

expandTo方法:

/**
     * Ensures that the BitSet can accommodate a given wordIndex,
     * temporarily violating the invariants.  The caller must
     * restore the invariants before returning to the user,
     * possibly using recalculateWordsInUse().
     * @param   wordIndex the index to be accommodated.
     */
    private void expandTo(int wordIndex) {
    int wordsRequired = wordIndex+1;
    if (wordsInUse < wordsRequired) {
        ensureCapacity(wordsRequired);
        wordsInUse = wordsRequired;
    }
    }

这里面又有个参数wordsInUse,定义如下:

/**
 * The number of words in the logical size of this BitSet.
 */
private transient int wordsInUse = 0;

根据其定义解释,这个参数表示的是BitSet中的words的逻辑大小。当我们传进一个wordIndex的时候,首先需要判断这个逻辑大小与wordIndex的大小关系,如果小于它,我们就调用方法ensureCapacity:

private void ensureCapacity(int wordsRequired) {
    if (words.length < wordsRequired) {
        // Allocate larger of doubled size or required size
        int request = Math.max(2 * words.length, wordsRequired);
            words = Arrays.copyOf(words, request);
            sizeIsSticky = false;
        }
    }

也就是说将words的大小变为原来的两倍,复制数组,标志sizeIsSticky为false,这个参数的定义如下:

/**
 * Whether the size of "words" is user-specified.  If so, we assume
 * the user knows what he's doing and try harder to preserve it.
 */
private transient boolean sizeIsSticky = false;

执行完这个方法后,我们可以将wordsInUse设置为wordsRequired。(换句话说,BitSet具有自动扩充的功能)

 

2)get方法:

/**
     * Returns the value of the bit with the specified index. The value
     * is <code>true</code> if the bit with the index <code>bitIndex</code>
     * is currently set in this <code>BitSet</code>; otherwise, the result
     * is <code>false</code>.
     *
     * @param     bitIndex   the bit index.
     * @return    the value of the bit with the specified index.
     * @exception IndexOutOfBoundsException if the specified index is negative.
     */
    public boolean get(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
 
    checkInvariants();
 
    int wordIndex = wordIndex(bitIndex);
    return (wordIndex < wordsInUse)
        && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }

这里主要是最后一个return语句,

 

return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0);

 

只有当wordIndex越界,并且wordIndex上的wordIndex上的bit不为0的时候,我们才说这一位是true.

 

3)size()方法:

 

/**
 * Returns the number of bits of space actually in use by this
 * <code>BitSet</code> to represent bit values.
 * The maximum element in the set is the size - 1st element.
 *
 * @return  the number of bits currently in this bit set.
 */
public int size() {
return words.length * BITS_PER_WORD;
}

 

这里也有一个常量,定义如下:

private final static int ADDRESS_BITS_PER_WORD = 6;
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

很明显,BITS_PER_WORD = 64,这里很重要的一点就是,如果使用size来返回BitSet数组的大小,其值一定是64的倍数,原因就在这里

 

4)与size相似的一个方法:length()源码如下:

 

/**
    * Returns the "logical size" of this <code>BitSet</code>: the index of
    * the highest set bit in the <code>BitSet</code> plus one. Returns zero
    * if the <code>BitSet</code> contains no set bits.
    *
    * @return  the logical size of this <code>BitSet</code>.
    * @since   1.2
    */
   public int length() {
       if (wordsInUse == 0)
           return 0;
 
       return BITS_PER_WORD * (wordsInUse - 1) +
       (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
   }

 

方法虽然短小,却比较难以理解,细细分析一下:根据注释,这个方法法返回的是BitSet的逻辑大小,比如说你声明了一个129位的BitSet,设置了第23,45,67位,那么其逻辑大小就是67,也就是说逻辑大小其实是的是在你设置的所有位里面最高位的Index。

这里有一个方法,Long.numberOfLeadingZeros,网上没有很好的解释,做实验如下:

long test = 1;<br>System.out.println(Long.numberOfLeadingZeros(test<<3));<br>System.out.println(Long.numberOfLeadingZeros(test<<40));<br>System.out.println(Long.numberOfLeadingZeros(test<<40 | test<<4));

打印结果如下:

60
23
23

也就是说,这个方法是输出一个64位二进制字符串前面0的个数的。

  

总结:

其实BitSet的源码并不复杂,只要理解其原理,对整数的移位等操作比较熟悉,细心阅读就可以理解。

分享到:
评论

相关推荐

    java 原生包 BitSet 源码

    在学习BitSet源码时,需要注意以下几个关键的成员方法: - set(int index):将指定索引位置的位设置为true。 - clear(int index):将指定索引位置的位设置为false。 - get(int index):返回指定索引位置的位的值。 -...

    javabitset源码-source-code-jdk-8u211:源代码-jdk-8u211

    bitset源码 JAVA 源码研究 使用版本 [jdk-8u211] [环境 IDEA] 构建步骤 1、创建项目结构 rt/ // rt.jar 反编译源码 rtsrc/ // JDK 源码 src/ // 项目源码 2、导入源码 import jdk source of src.zip import jdk ...

    javabitset源码-montysolr:Solr天体物理数据系统

    在标题提及的 "javabitset源码-montysolr:Solr天体物理数据系统" 中,我们可以推测这个项目可能是在Solr(一个流行的全文搜索引擎)中使用BitSet来处理天体物理数据。下面我们将深入探讨Java BitSet以及它如何应用于...

    Lucene项目的文档和源码

    源码阅读是理解任何软件内部工作原理的最好方式,通过研究Lucene的源码,我们可以深入了解其内部的数据结构、算法实现以及优化技巧。例如,可以学习到如何实现Trie数据结构进行高效查询,或者如何使用BitSet进行布尔...

    Lucene3.5源码jar包

    本压缩包包含的是Lucene 3.5.0版本的全部源码,对于想要深入理解Lucene工作原理、进行二次开发或者进行搜索引擎相关研究的开发者来说,是一份非常宝贵的学习资源。 Lucene 3.5.0是Lucene的一个重要版本,它在3.x...

    LuceneInAction源码

    源码中,可以研究`IndexSearcher`的实现,了解这些过程的细节。 4. **高级特性**: Lucene提供了多种高级特性,如近似搜索、模糊搜索、短语匹配和布尔运算等。源码里,你可以看到`FuzzyQuery`、`PhraseQuery`和`...

    C++标准库第二版及源码

    《C++标准库第二版及源码》是一个深入学习C++编程的重要参考资料,它涵盖了C++标准库的全面内容,并提供了源码供读者研究和学习。C++标准库是C++编程语言不可或缺的一部分,它提供了丰富的类和函数,极大地提高了...

    C++ - SGI 版本 STL源码

    通过研究SGI版STL源码,开发者不仅可以深入理解C++ STL的工作原理,还能学习如何设计高效的数据结构和算法。这对于提升C++编程技能,优化代码性能,以及自定义STL容器和算法都大有裨益。在实际项目中,理解和利用STL...

    hex2bin_hex2bin_C++Redistributable_源码

    在深入研究源码时,可能会发现它使用了C++标准库中的函数,如std::stringstream或std::bitset来实现转换,也可能涉及到对输入字符串的解析和验证。对于有兴趣学习C++或理解十六进制到二进制转换的人来说,这是一个很...

    进制转换,进制转换器,C,C++源码.zip

    进制转换是计算机科学中的基本概念,涉及到二进制、八进制、十进制和...通过深入研究这个压缩包中的源码,学习者不仅可以掌握进制转换的基本原理,还能了解到如何在实际编程中应用这些知识,从而提升自己的编程技能。

    elasticsearch-5.3.2.zip

    **Elasticsearch 5.3.2 源码解析** Elasticsearch 是一个流行的、开源的全文搜索引擎,它基于 Lucene 库构建,提供了一个分布式、...同时,源码研究也有助于开发者理解分布式系统的设计原则,提升软件架构能力。

    JAVA基于纠错码的冗余技术的研究——EVENODD码的设计与实现(源代码+LW).zip

    5. **使用Java实现**:Java提供了丰富的类库支持位操作和数据处理,如`java.util.BitSet`类,可以方便地进行位运算。此外,Java的面向对象特性允许我们将不同的功能封装到独立的类和方法中,提高代码的可读性和可...

    STL Source3.3

    STL(Standard Template Library,标准模板库)是C++编程语言中的一个重要组成部分,它提供了一系列高效、...通过阅读和研究这些源码,我们可以更好地掌握C++编程的核心技术,并为自己的项目选择合适的数据结构和算法。

    Lucene5学习之Filter过滤器

    《深入理解Lucene5:Filter过滤器的奥秘》 在全文搜索引擎的开发过程中,Lucene...在深入研究源码和实践过程中,我们不仅能掌握Lucene的基本原理,还能进一步提升搜索引擎的定制化能力,满足不同场景下的业务需求。

    lucene-3.0.0-src.zip

    《Apache Lucene 3.0.0 源码解析》 ...无论是为了开发自己的搜索应用,还是进行搜索引擎优化,深入研究Lucene都是非常有价值的。通过分析和实践,我们可以更好地应对各种复杂的文本搜索场景,提高应用程序的用户体验。

    Hex2bin 源代码

    通过研究和理解"Hex2bin源代码 VC++ 无64K限制",我们可以学习到如何优化内存管理,提高程序的性能和可扩展性,这对于任何软件开发者来说都是一项宝贵的技能。在实践中不断探索和改进,才能真正掌握这项技术,让我们...

    (超赞)JAVA精华之--深入JAVA API

    - `java.util.BitSet` 用于存储位字段,可以高效地进行位操作。 **1.1.3 Java IO包** - **数据流** - 数据流是 Java 中用于读取和写入数据的基本方式,分为输入流 `InputStream` 和输出流 `OutputStream`。 - *...

    Release.zip

    这涉及到数字转换的算法,例如C++中的`std::stringstream`或`std::bitset`可以用来处理进制转换。 "循环计数"可能指的是程序在计时过程中对特定事件的计数。例如,在连续执行某个任务N次时,程序可以记录已执行的...

    MiniTool_20200424.rar

    在C++中,可以使用`std::stringstream`或`std::bitset`来实现这样的转换。MiniTool通过这些底层机制,提供了直观易用的接口,使得开发者无需深入了解底层细节,也能轻松完成转换。 2. **Base64编码**: Base64是一...

    C++标准模板库(中文)(不好给退货)嘿嘿

    通过深入研究STL的源码,还能了解其内部的数据结构和算法,提升编程能力。在实际开发中,合理利用STL可以避免重复造轮子,使代码更加符合“DRY”(Don't Repeat Yourself)原则,从而提高开发效率。

Global site tag (gtag.js) - Google Analytics