BitSet&BloomFilter&HyperLogLog_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的工具类，方便大家使用

package cn.hutool.bloomfilter;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.util.BitSet;
 
import cn.hutool.core.io.FileUtil;
import cn.hutool.core.io.IoUtil;
import cn.hutool.core.util.HashUtil;
 
/**
 * BloomFilter实现方式2，此方式使用BitSet存储。<br>
 * Hash算法的使用使用固定顺序，只需指定个数即可
 * @author loolly
 *
 */
public class BitSetBloomFilter implements BloomFilter{
	private static final long serialVersionUID = 1L;
 
   //  省略无关代码.......
	/**
	 * 构造一个布隆过滤器，过滤器的容量为c * n 个bit.
	 * 
	 * @param c 当前过滤器预先开辟的最大包含记录,通常要比预计存入的记录多一倍.
	 * @param n 当前过滤器预计所要包含的记录.
	 * @param k 哈希函数的个数，等同每条记录要占用的bit数.
	 */
	public BitSetBloomFilter(int c, int n, int k) {
		this.hashFunctionNumber = k;
		this.bitSetSize = (int) Math.ceil(c * k);
		this.addedElements = n;
		this.bitSet = new BitSet(this.bitSetSize);
	}
 
	 
	
	@Override
	public boolean add(String str) {
		if (contains(str)) {
			return false;
		}
 
		int[] positions = createHashes(str, hashFunctionNumber);
		for (int i = 0; i < positions.length; i++) {
			int position = Math.abs(positions[i] % bitSetSize);
			bitSet.set(position, true);
		}
		return true;
	}
	
	/**
	 * 判定是否包含指定字符串
	 * @param str 字符串
	 * @return 是否包含，存在误差
	 */
	@Override
	public boolean contains(String str) {
		int[] positions = createHashes(str, hashFunctionNumber);
		for (int i : positions) {
			int position = Math.abs(i % bitSetSize);
			if (!bitSet.get(position)) {
				return false;
			}
		}
		return true;
	}
 
 
	 
}

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 的基本命令：

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

4、对比与总结