搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 菜鸟联盟NoobAssn > BitMap、BitSet与Bloom Filter

BitMap、BitSet与Bloom Filter

菜鸟联盟NoobAssn 2019-02-15
举报

推荐阅读时间:5分钟

引言

先来看一个问题,假设现在有范围为 1-10 亿的 11 亿个 int 型整数,如何排除掉其中的重复数字? int 占 4 个字节,可以表示 -2,147,483,648 ~ +2,147,483,647 的数据。 所以一般的思路是会将这 11 亿个数作为 int 型数据存到一个 HashSet 集合中进行去重。 但是,这样会存在一个问题。我们知道 1GB=1024KB=1024 * 1024Byte, 那么 10亿 * 4Byte 将占用接近 4GB 的内存,这将是极大的性能浪费,很可能会影响程序的健康运行。

思路

我们可以考虑用"位映射(BitMap)"来解决这个问题。试想一下,如果我们有一个位数组(bit[n]),那么我们可以用 bit[i] 来表示 0-n 中对应的数字,每个元素有 1 和 0 两个取值,分别代表该数字存在与否。这样一来,我们记录一个数字只需要一个 bit,相对于之前的 int 类型(32 bit),整整缩小了 32 倍的存储大小(4GB/32=125MB)!

扩展一下,当我们需要记录每个数字出现次数是否超过 2 次时,可以使用连续的两位来记录一个数字:一位用来记录是否出现,另一位用来记录是否超过 2 次。

不过,Java 中无法创建 bit 数组,我们可以使用 int 或 long 数组来实现这个目的。建立一个 int 数组 int[n],int[0] 记录了 0-7,int[1] 记录了 8-15 ...... 依此类推。

Java BitSet

Java 中有一个 BitSet 类,从命名就可以看出它是用来存储去重的位元素集合,它还支持 and、or 等位运算。 用来解决文章开头的问题非常合适,方式如下:

 
   
   
 
  1. public class BitSetStudy {

  2.    public static void main(String[] args) {

  3.        BitSet bitSet = new BitSet(1000000000);

  4.        //随机生成 11 亿个数字

  5.        for (int i = 0; i < 1100000000; i++) {

  6.            bitSet.set((int) (Math.random() * 1000000000));

  7.        }

  8.        System.out.println(bitSet.size());

  9.        System.out.println("end");

  10.    }

  11. }

打开 jconsole,可以看到存储了 bitset 对象的老年代所占用的内存稳定在 125MB 左右。

关于 BitSet 的 and、andNot、or、xor 操作:

 
   
   
 
  1. public static void main(String[] args) {

  2.    BitSet bitSet = new BitSet();

  3.    bitSet.set(2, 6);

  4.    BitSet bitSet1 = new BitSet();

  5.    bitSet1.set(4, 8);

  6.    BitSet bitSetAnd = (BitSet) bitSet.clone();

  7.    BitSet bitSetAndNot = (BitSet) bitSet.clone();

  8.    BitSet bitSetOr = (BitSet) bitSet.clone();

  9.    BitSet bitSetXor = (BitSet) bitSet.clone();

  10.    bitSetAnd.and(bitSet1);

  11.    bitSetAndNot.andNot(bitSet1);

  12.    bitSetOr.or(bitSet1);

  13.    bitSetXor.xor(bitSet1);

  14.    System.out.println("bitSet is : " + bitSet + " , and bitSet1 is: " + bitSet1);

  15.    System.out.println("run bitSet.XMethod(bitSet1) , result is : ");

  16.    System.out.println("and:" + bitSetAnd);

  17.    System.out.println("andNot:" + bitSetAndNot);

  18.    System.out.println("or:" + bitSetOr);

  19.    System.out.println("xor:" + bitSetXor);

  20. }

结果如下:

 
   
   
 
  1. bitSet is : {2, 3, 4, 5} , and bitSet1 is: {4, 5, 6, 7}

  2. run bitSet.XMethod(bitSet1) , result is :

  3. and:{4, 5}

  4. andNot:{2, 3}

  5. or:{2, 3, 4, 5, 6, 7}

  6. xor:{2, 3, 6, 7}

自己实现 BitMap

Java 的 BitSet 使用起来存在局限性,我们可以参考 BitSet 实现自己的 BitMap 来扩展应用场景。 核心还是通过 int/long 数组元素的位来记录有序数据,一个实现如下:

 
   
   
 
  1. public class BitMap {

  2.    private int[] words;

  3.    private int size;

  4.    public BitMap(int n) {

  5.        size = n;

  6.        //每个int占32位,数组大小为 n/32+1

  7.        words = new int[(size >> 5) + 1];

  8.    }

  9.    public final void set(int bit) {

  10.        //获得数据所在的数组序号(int),相当于 bit/32

  11.        int i = bit >> 5;

  12.        //获得该int元素中要修改为1的数字,相当于 bit%32

  13.        int j = bit & 31;

  14.        //获得要修改的位

  15.        int k = 1 << j;

  16.        //将该元素相应的二进制位设为1

  17.        words[i] |= k ;

  18.    }

  19.    public final boolean get(int bit) {

  20.        //参考set方法理解

  21.        return (words[bit >> 5] & (1 << (bit & 31))) != 0;

  22.    }

  23. }

实现了核心的存储结构、set 和 get 方法。

布隆过滤器(Bloom Filter)

了解完 BitMap,我们掌握了一种处理大量连续数据的好方法。现在继续扩展一下,现在如果我们要记录的是海量的分布很不均匀的数据,如果继续用 BitMap 的方式,将会浪费大量的存储空间,或者数据量已经大到使用 BitMap 的方式,仍然会浪费大量的内存空间。面对这两种情情况时,我们可以考虑使用布隆过滤器。

布隆过滤器核心是对一个 key 使用多个 hash 函数求出多个值,将这些值散列在一个有限的数组中,这样,当这些 hash 函数求出的值都符合预期就认为该 key 存在;若只要存在 hash 函数的值不符合,就可以确定它不存在。在某些场景下,这种方法效果非常好。图示如下:

BitMap、BitSet与Bloom Filter

可以看出来,这种方法存在一定误差,不过误差几率可以通过增加 hash 函数和散列数组大小来减小。

还有一个问题就是,当某个 key 被删除后,不能直接在散列表中将对应的 value 去掉,因为可能会影响其他 key。针对这个问题,我们可以维护一个黑名单,每次计算 hash 前,先判断 key 是否在黑名单中,有则表示该 key 已删掉。


当前浏览器不支持播放音乐或语音,请在微信或其他浏览器中播放 BitMap、BitSet与Bloom Filter



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《BitMap、BitSet与Bloom Filter》的版权归原作者「菜鸟联盟NoobAssn」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注菜鸟联盟NoobAssn微信公众号

菜鸟联盟NoobAssn微信公众号:NoobAssn

菜鸟联盟NoobAssn

手机扫描上方二维码即可关注菜鸟联盟NoobAssn微信公众号

菜鸟联盟NoobAssn最新文章

精品公众号随机推荐

举报