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的个数的。

https://www.cnblogs.com/lqminn/archive/2012/08/30/2664122.html

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,047评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,807评论 3 386
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,501评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,839评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,951评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,117评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,188评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,929评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,372评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,679评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,837评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,536评论 4 335
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,168评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,886评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,129评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,665评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,739评论 2 351

推荐阅读更多精彩内容