文档章节

【转载】BitSet

javahongxi
 javahongxi
发布于 2017/08/25 19:15
字数 1704
阅读 11
收藏 1

本文转载自http://shift-alt-ctrl.iteye.com/blog/2194519

 

JAVA中BitSet就是“位图”数据结构,根据“位图”的语义,数据的存在性可以使用bit位上的1或0来表示;一个bit具有2个值:0和1,正好可以用来表示false和true。对于判断“数据是否存在”的场景,我们通常使用HashMap来存储,不过hashmap这个数据结构KEY和Value的保存需要消耗较多的内存,不适合保存较多的数据,即大数据场景;比如在有10亿条URL中判定一个“www.baidu.com/a”是否存在,如果我们使用常规的hashmap来保存将是不现实的,因为URL本身需要占据较多的内存而无法直接操作。如果我们使用bitset来保存,那么可以对一条URL求hashcode,并将数字映射在bitset上,那么事实上它只需要bitset上的一个bit位即可,即我们1位空间即可表达一个URL字符串的存在性。

 

    所谓“存在性”,就是通过BitSet来检测一个数字是否存在。

 

1、BitSet原理

    JAVA中,一个long型数字占用64位空间,根据上述“位图”的概念,那么一个long型数字就可以保存64个数字的“存在性”状态(无碰撞冲突时)。比如50个数字{0,1,10,...63},判定“15”是否存在,那么我们通常会首先将这些数字使用数组或者hashmap保存,然后再去判定,那么保存这些这些数据需要占用64 * 64位;如果使用位图,那么一个long型数字即可。(如果换成50个字符串,那么其节约的空间可能更大)。

 

    1) BitSet只面向数字比较,比如set(int a,boolean value)方法,将数字a在bitSet中设定为true或者false;此后可以通过get(int a)方法检测结果。对于string类型的数据,如果像使用BitSet,那么可以将其hashcode值映射在bitset中。

    2) 首先我们需要知道:1,1<<64,1<<128,1<<192...等,这些数字的计算结果是相等的(位运算);这也是一个long数字,只能表达连续的(或者无冲突的)64个数字的状态,即如果把数字1在long中用位表示,那么数字64将无法通过同一个long数字中位表示--冲突;BitSet内部,是一个long[]数组,数组的大小由bitSet接收的最大数字决定,这个数组将数字分段表示[0,63],[64,127],[128,191]...。即long[0]用来存储[0,63]这个范围的数字的“存在性”,long[1]用来存储[64,127],依次轮推,这样就避免了位运算导致的冲突。

Java代码   收藏代码
  1. |------------|----------|----------|----------|----------|  
  2. |  
  3. |  数字范围      [0,63]     [64,127]  [128,191]     ...   |  
  4. |------------|----------|----------|----------|----------|  
  5. |  
  6. |long数组索引      0           1          2         ...   |  
  7. |------------|----------|----------|----------|----------|  

 

    3) bitSet内部的long[]数组是基于向量的,即随着set的最大数字而动态扩展。数组的最大长度计算:

Java代码   收藏代码
  1. (maxValue - 1) >> 6  + 1  

 

    4) BitSet中set方法伪代码:

Java代码   收藏代码
  1. public void set(int number) {  
  2.     int index = number >> 6;//找到number需要映射的数组的index。  
  3.     if(index + 1 > length) {  
  4.         ensureCapacity(index + 1);//重新扩展long[]数组  
  5.     }   
  6.     long[index] |= (1L << number);//冲突解决  
  7. }  

 

2、使用BitSet:本例中使用bitSet做String字符串的存在性校验。

Java代码   收藏代码
  1. BitSet bitSet = new BitSet(Integer.MAX_VALUE);//hashcode的值域  
  2.   
  3. //0x7FFFFFFF  
  4. String url = "http://baidu.com/a";  
  5. int hashcode = url.hashCode() & 0x7FFFFFFF;  
  6. bitSet.set(hashcode);  
  7.   
  8. System.out.println(bitSet.cardinality());//着色位的个数  
  9. System.out.println(bitSet.get(hashcode));//检测存在性  
  10. bitSet.clear(hashcode);//清除位数据  

 

3、BitSet与Hashcode冲突

    因为BitSet API只能接收int型的数字,即只能判定int数字是否在bitSet中存在。所以,对于String类型,我们通常使用它的hashcode,但这有一种隐患,java中hashcode存在冲突问题,即不同的String可能得到的hashcode是一样的(即使不重写hashcode方法),如果我们不能很好的解决这个问题,那么就会出现“数据抖动”---不同的hashcode算法、运行环境、bitSet容量,会导致判断的结果有所不同。比如A、B连个字符串,它们的hashcode一样,如果A在BitSet中“着色”(值为true),那么检测B是否在BitSet存在时,也会得到true。

 

    这个问题该如何解决或者缓解呢?

    1)调整hashcode生成算法:我们可以对一个String使用多个hashcode算法,生成多个hashcode,然后在同一个BitSet进行多次“着色”,在判断存在性时,只有所有的着色位为true时,才判定成功。

Java代码   收藏代码
  1. String url = "http://baidu.com/a";  
  2. int hashcode1 = url.hashCode() & 0x7FFFFFFF;  
  3. bitSet.set(hashcode1);  
  4.   
  5. int hashcode2 = (url + "-seed-").hashCode() & 0x7FFFFFFF;  
  6. bitSet.set(hashcode2);  
  7. System.out.println(bitSet.get(hashcode1) && bitSet.get(hashcode2));  

 

    其实我们能够看出,这种方式降低了误判的概率。但是如果BitSet中存储了较多的数字,那么互相覆盖着色,最终数据冲突的可能性会逐渐增加,最终仍然有一定概率的判断失误。所以在hashcode算法的个数与实际String的个数之间有一个权衡,我们建议:  “hashcode算法个数 * String字符串的个数”  < Integer.MAX_VALUE * 0.8

 

    2) 多个BitSet并行保存:

    改良1)中的实现方式,我们仍然使用多个hashcode生成算法,但是每个算法生成的值在不同的BitSet中着色,这样可以保持每个BitSet的稀疏度(降低冲突的几率)。在实际结果上,比1)的误判率更低,但是它需要额外的占用更多的内存,毕竟每个BitSet都需要占用内存。这种方式,通常是缩小hashcode的值域,避免内存过度消耗。

Java代码   收藏代码
  1. BitSet bitSet1 = new BitSet(Integer.MAX_VALUE);//127M  
  2. BitSet bitSet2 = new BitSet(Integer.MAX_VALUE);  
  3.   
  4. String url = "http://baidu.com/a";  
  5. int hashcode1 = url.hashCode() & 0x7FFFFFFF;  
  6. bitSet1.set(hashcode1);  
  7.   
  8. int hashcode2 = (url + "-seed-").hashCode() & 0x7FFFFFFF;  
  9. bitSet2.set(hashcode2);  
  10.   
  11. System.out.println(bitSet1.get(hashcode1) && bitSet2.get(hashcode2));  

 

    3) 是否有必要完全避免误判?

    如果做到100%的正确判断率,在原理上说BitSet是无法做的,BitSet能够保证“如果判定结果为false,那么数据一定是不存在;但是如果结果为true,可能数据存在,也可能不存在(冲突覆盖)”,即“false == YES,true == Maybe”。有人提出将冲突的数据保存在类似于BTree的额外数据结构中,事实上这种方式增加了设计的复杂度,而且最终仍然没有良好的解决内存占用较大的问题。

 

4、BloomFilter(布隆姆过滤器)

    BloomFilter 的设计思想和BitSet有较大的相似性,目的也一致,它的核心思想也是使用多个Hash算法在一个“位图”结构上着色,最终提高“存在性”判断的效率。请参见Guava  BloomFilter。如下为代码样例:

Java代码   收藏代码
  1. Charset charset = Charset.forName("utf-8");  
  2. BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(charset),2<<21);//指定bloomFilter的容量  
  3. String url = "www.baidu.com/a";  
  4. bloomFilter.put(url);  
  5. System.out.println(bloomFilter.mightContain(url));

© 著作权归作者所有

javahongxi
粉丝 168
博文 259
码字总数 779422
作品 0
朝阳
程序员
私信 提问
redis相关知识积累

在学习redis时总结的问题 setbit的作用 参考自: https://www.zhihu.com/question/27672245 作者:Andy 链接:https://www.zhihu.com/question/27672245/answer/123641959 来源:知乎 著作权归......

wangtenfee
2017/05/21
0
0
利用Redis BitMap 统计用户活跃指标

bitMap原理 : 如下: index 从 0 到 9 ,依次对应到一个bit位上,如果index 代表用户id,bit位上的0 1分表 代表用户是否登录; 1 0 1 1 0 1 1 0 1 1 0 1 2 3 4 5 6 7 8 9 redis数据结构中 st...

robin-yao
2015/04/11
1K
2
Java.util包下BitSet的用法

BitSet:是一个字节集合,用它可以表示整数和进行求两个集合的交集、并集等运算。 我们知道,计算机存储的最小单位是比特bit,而我们在java程序中的最小单位是字节Byte,他们之间的换算关系是...

吴小河
2016/07/12
526
2
若只有4KB内存可用,该如何打印数组中所有重复的元素

/** * 功能:给定一个数组,包含1到N的整数,N最大为32000,数组可能含有重复的值,且N的取值不定。 * 若只有4KB内存可用,该如何打印数组中所有重复的元素。 / [java] view plain copy /* ...

一贱书生
2016/11/23
24
0
Elasticsearch结构化搜索_filter执行原理深度剖析(bitset机制与caching机制)

课程大纲 (1)在倒排索引中查找搜索串,获取document list date来举例 到倒排索引中一找,发现2017-02-02对应的document list是doc2,doc3 (2)为每个在倒排索引中搜索到的结果,构建一个b...

小红牛
2018/05/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Netty整合Protobuffer

现在我们都知道,rpc的三要素:IO模型,线程模型,然后就是数据交互模型,即我们说的序列化和反序列化,现在我们来看一下压缩比率最大的二进制序列化方式——Protobuffer,而且该方式是可以跨...

算法之名
32分钟前
16
0
如何用C++实现栈

栈的定义 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压...

BWH_Steven
51分钟前
5
0
编程作业20190210900169

1编写一个程序,提示用户输入名和姓,然后以“名,姓”的格式打印出来。 #include <stdio.h>#include <stdlib.h> int main(){ char firstName[20]; char lastName[20]; print......

1李嘉焘1
今天
12
0
补码的优点及原理分析

只讨论整数 1.计算机内部为什么没有减法器? 减法运算本身其实就是加法,如x - y即x +(-y),所以只需要将负数成功表示出来并可以参加加法运算,那加法器就可同时实现“+”和“-”的运算。这...

清自以敬
今天
76
0
Docker 可视化管理 portainer

官网安装指南: https://portainer.readthedocs.io/en/latest/deployment.html docker-compose.yml 位置,下载地址:https://downloads.portainer.io/docker-compose.yml...

Moks角木
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部