当前位置:   article > 正文

BitSet&BloomFilter&HyperLogLog_bitsetbloomfilter hutool

bitsetbloomfilter hutool

目录

1、BitSet

2、BloomFilter

3、HyperLogLog

4、对比与总结


1、BitSet

              参考文档:Java中BitSet的使用及详解

              使用紧凑的数据结构处理海量数据的去重与排序,达到小马拉大车,四两拨千斤的效果。

面试题1:有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来(百度)。
                遍历这1千万个随机数,使用一个大小为1亿个bit位的BitSet来存储随机数出现的标志,出现设置为1,没有出现就是0,最后输出BitSet中标志位为0的序号。

面试题2:有40亿个数据,大小为1到1亿之间,存在重复,统计出没有出现的数据,并对40亿个数据去重排序。
                 遍历这40亿个数字,使用一个大小为40亿个bit位的BitSet来存储随机数出现的标志,出现设置为1,没有出现就是0,最后输出BitSet中标志位为0的序号【统计出没有出现的数据】
         最后输出BitSet中标志位为1的序号【去重排序】 。

           
            因为在BitSet.clear(bitIndex)与  BitSet.set(bitIndex)过程中,如果当前words[]长度不满足要求,会进行扩容,扩容就存在数组复制会影响性能,所以,最佳实践是,在new BitSet()时,设置
一个初始大小,例如你有知道你的数据空间最多有1亿个数,则BitSet bitSet=new BitSet(1亿); 数据集的大小正在就是bits位数。

2、BloomFilter

        与BitSet相比,BitSet只能处理海量数据的去重与排序针对的是数字类型,而BloomFilter可以处理字符串,利用多个Hash函数将字符串映射到BitSet上。
        缺点:
                 BloomFilter存在FalsePositive问题,所以结果不太准,基本可以忽略这个问题,概率比较低。
                 BloomFilter无法支持删除操作
            参考文档: 深度剖析各种BloomFilter的原理、改进、应用场景
        Hutool已经提供了BloomFilterUtil的工具类,方便大家使用

  1. package cn.hutool.bloomfilter;
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.util.BitSet;
  5. import cn.hutool.core.io.FileUtil;
  6. import cn.hutool.core.io.IoUtil;
  7. import cn.hutool.core.util.HashUtil;
  8. /**
  9. * BloomFilter实现方式2,此方式使用BitSet存储。<br>
  10. * Hash算法的使用使用固定顺序,只需指定个数即可
  11. * @author loolly
  12. *
  13. */
  14. public class BitSetBloomFilter implements BloomFilter{
  15. private static final long serialVersionUID = 1L;
  16. // 省略无关代码.......
  17. /**
  18. * 构造一个布隆过滤器,过滤器的容量为c * n 个bit.
  19. *
  20. * @param c 当前过滤器预先开辟的最大包含记录,通常要比预计存入的记录多一倍.
  21. * @param n 当前过滤器预计所要包含的记录.
  22. * @param k 哈希函数的个数,等同每条记录要占用的bit数.
  23. */
  24. public BitSetBloomFilter(int c, int n, int k) {
  25. this.hashFunctionNumber = k;
  26. this.bitSetSize = (int) Math.ceil(c * k);
  27. this.addedElements = n;
  28. this.bitSet = new BitSet(this.bitSetSize);
  29. }
  30. @Override
  31. public boolean add(String str) {
  32. if (contains(str)) {
  33. return false;
  34. }
  35. int[] positions = createHashes(str, hashFunctionNumber);
  36. for (int i = 0; i < positions.length; i++) {
  37. int position = Math.abs(positions[i] % bitSetSize);
  38. bitSet.set(position, true);
  39. }
  40. return true;
  41. }
  42. /**
  43. * 判定是否包含指定字符串
  44. * @param str 字符串
  45. * @return 是否包含,存在误差
  46. */
  47. @Override
  48. public boolean contains(String str) {
  49. int[] positions = createHashes(str, hashFunctionNumber);
  50. for (int i : positions) {
  51. int position = Math.abs(i % bitSetSize);
  52. if (!bitSet.get(position)) {
  53. return false;
  54. }
  55. }
  56. return true;
  57. }
  58. }

3、HyperLogLog

    参考文档:海量数据处理(Set、BitMap、HyperLogLog、BloomFilter)

在redis的2.8.9版本后出现的新数据结构

Redis HyperLogLog 是用来做基数统计的算法,在输入元素的数量或者体积非常非常大时,计算基数所需的空间总是固定 的、并且是很小的。

在 Redis 里面,每个 HyperLogLog 键只需要花费 12 KB 内存,就可以计算接近 2^64 个不同元素的基 数。这和计算基数时,元素越多耗费内存就越多的集合形成鲜明对比。

但是,因为 HyperLogLog 只会根据输入元素来计算基数,而不会储存输入元素本身,所以 HyperLogLog 不能像集合那样,返回输入的各个元素。

优点:每个hyperloglog只需要12K的空间,并且标准误算率是0.81%,不同的纪录之间可以进行聚合,

也就是可以通过聚合统计出任意时间范围的去重结果,统计单个hyperloglog时时间复杂度为o(1)。

缺点:对于统计结果要求较为精确的场合并不是非常适用

适用场景:在对误算率要求不高的情况下,同bitset。

下表列出了 redis HyperLogLog 的基本命令:

序号

命令及描述

时间复杂度

1PFADD key element [element ...] 
添加指定元素到 HyperLogLog 中。
O(1)添加每个元素。
2PFCOUNT key [key ...] 
返回给定 HyperLogLog 的基数估算值。

 当命令作用于单个 HyperLogLog 时, 复杂度为 O(1) , 并且具有非常低的平均常数时间。

当命令作用于 N 个 HyperLogLog 时, 复杂度为 O(N) , 常数时间也比处理单个 HyperLogLog 时要大得多。

3PFMERGE destkey sourcekey [sourcekey ...] 
将多个 HyperLogLog 合并为一个 HyperLogLog
 O(N) , 其中 N 为被合并的 HyperLogLog 数量, 不过这个命令的常数复杂度比较高。

         HyperLogLog与BitSet相比,空间复杂度更小,也输入元素无关,并且支持字符串的输入,有一定的误差率;

4、对比与总结

 

 优点缺点
Set

1、精确度高,无误差;

2、储存输入元素本身,能返回存储的值

1、非常耗空间

2、当redis存储set的数据量比较大,形成多个大键,对它们进行聚合(sunionstroe)是非常耗时的

3、数量大的话,插入到hashSet的数据有多少,HashSet每次add总要判断hashcode影响效率

BitMap

1、空间复杂度不随原始集合内元素的个数增加而增加

2、节省存储空间(数据位数不大的情况下)

1、不会储存输入元素本身,不能返回存储的值
2、bitSet只适合百万或者千万的用户量来进行去重(空间复杂度随集合内最大元素增大而线性增大)

3、有误差

HyperLogLog1、在输入元素的数量或者体积非常非常大时,计算基数所需的空间总是固定 的、并且是很小的。在 Redis 里面,每个 HyperLogLog 键只需要花费 12 KB 内存,就可以计算接近 2^64 个不同元素的基 数。(节省存储空间)
2、标准误算率是0.81%
1、不会储存输入元素本身,不能返回存储的值(有误差)
BloomFilter

1、能够动态控制精度,确保运算结果不会偏差太多;

2、bloomFilter是用bit计算的,运算时间大大加快,不像set那样,数据量越大时,运行越耗时;
3、计算得到的数据不会添加别的数据,只会加少了。也就是说:如果bloomfilter判断不存在,则一定不存在; 如果bloomfilter判断存在,则可能不存在。

4、节省存储空间

1、不会储存输入元素本身,不能返回存储的值(有误差)


2、错误概率可以降低,但相应的要增加内存的

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/436867
推荐阅读
相关标签
  

闽ICP备14008679号