文章目录本质位图的特征位图映射规则如何判断是否存在位图中的数量的代码实现java实现类
在hbase中实现布尔滤波器有疑问吗？ 实际上，布尔滤波器这种存储结构是基于多位图的，其内部存储着多个位图结构。 让我们来看看像位图一样的数据结构。
本质
位图的本质是利用由hash函数所映射的map数据结构。 java的hashmap数据结构的基础仍然是以hash函数映射的数字为key，其value以链表or数组的形式存储数据，我们知道使用hash函数有可能发生hash冲突。
位图的存在，本质上是对hashMap更节省内存的优化，以检测是否存在值为目的，在爬虫结构的url重构功能、是否加载了缓存实现等应用场景中，取决于位图数据结构的应用
位图特征1 .查询效率(o )1)复杂性)2.节省内存) 1亿个不同的密钥(总共需要12.5m米)通过使用hashMap的密钥值，可以使用数据类型，例如integer/long/string
位图图像
在上图中，主要想表达的是位图只有一个大数组(作为数组构建的映射结构)，可以利用数组缓存中连续性的特点高效地进行读取操作。 位图中的key通过散列函数映射到整形值，根据该整形值查找相应数组的位置，将相应数据值中的位数设定为1即可。
位图映射规则位图映射规则具有以下优点：只要将与一系列二进制相对应的位表示为1即可，不像存储在hashmap中的key那样消耗存储器
例如，它存储数组的第一个和第二个字节。
1000000000001000表示位图包含16和4这两个数
判断位图中是否存在某个数的方法在判断位图中是否存在4时，取出该数与位图的文字要素对应的数据，与4自身的二进制位进行合并()运算，其计算结果等于4自身的二进制即可
代码实现github地址
import com.carrotsearch.sizeof.ramusageestimator； classmybitset { privatefinalchar [ ] achar； 定义具有私有文件大小的字符数组； 初始化能够存储publicmybitset(intsize )//size大小的位图(/这里，当size为16时，每个char元素占用16位，因此，如果初始化//1字节的字节数组，则achar=ner=this.size=size； (//I数字公共语音集(inti ) ) /当我们I可以被16整除时，int index=i % 16==0？ i/16 - 1 : i /16； intsplitindex=1(I-index*16-1 )； achar[index]=(char ) (aChar[index] | splitindex )； }publicbooleanget(intI ) { int index=i % 16==0？ i/16 -1 : i /16； intsplitindex=1(I-index*16-1 )； int i1=aChar[index] splitindex； return i1==splitindex； } @Override public String toString () stringbuilder sb=new stringbuilder )； for(intI=0； i aChar.length； I ) sb.append(achar[I]； system.out.println (integer.tobinarystring (achar [ I ] ) )； } return sb.toString (； } publicstaticvoidmain (string [ ] args ) { int size=1234567890； //12亿个数组存储mybitsetmybitset=newmybitset (size )的mybitset.set(1； MyBitset.set(2； MyBitset.set(3； mybitset.set(31； mybitset.set(32； mybitset.set(16； for(intI=1； i=size； I ) booleanb=mybitset.get(I； if(b ) System.out.println(i ) I； } longl=ramusageestimator.sizeof (mybitset )； system.out.println(size: ) l； //size: 154321032 140m数据}通过计算com.carrotsearch.Java-sizeof :0.05包的对象大小的函数，可以将12亿数字存储在位图中
用hashmap的话会有多大？ 我想需要400米左右
因此，位图比hashmap节省了存储数值的内存空间，可以在o(1)的时间复杂度中识别元素，性能也比hashmap好。 因为hashmap在检索值时不仅会检查hashmap指定的key，还会逐个检查链接到key的元素。
java安装类实际上，java中也已经安装了内建的位图
package java.util.BitSet