了解布隆过滤器
日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件 中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。 一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。 比如说，一个像Yahoo,Hotmail 和Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。
如果用哈希表，每存储一亿个 email 地址，就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB，即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。
1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
3. 将哈希与位图结合，即布隆过滤器
布隆过滤器的提出
布隆过滤器是由布隆（Burton Howard Bloom）提出，布隆过滤器是一种紧凑型，概率型数据结构，特点是可以高效的插入和查询元素，布隆过滤器可以告诉你“元素可能存在和一定不存在”，通过多种哈希数将元素映射到位图中，此种方式不仅可以提升查询效率，也可以节省大量的空间
布隆过滤器的插入
向布隆过滤器插入:baidu词语
再向布隆过滤器插入：tencent
插入方式：上图的布隆过滤器有三种Hash函数，然后使用三种Hash函数对插入值进行计算，计算出插入值的位图的下标,然后将下标的值改为零。
布隆过滤器的插入思想
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。 所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零， 代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。 比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比 特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。
布隆过滤器的代码实现
public class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap , int seed){
this.cap = cap;
this.seed = seed;
}
public int hash(String value){
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
public class BloomFilter {
// Bitset默认大小
private final static int DEFAULT_SIZE = 1 << 24;
// 创建多个值，用于创建多个hash值
private final static int [] seeds = new int[]{7,18,22,33,45,85};
// 位图由于储存元素信息
private BitSet bitSet;
// 哈希函数所对应类
private SimpleHash[] simpleHashes;
private int size;
public BloomFilter(){
this.bitSet = new BitSet(DEFAULT_SIZE);
this.simpleHashes = new SimpleHash[seeds.length];
for (int i = 0; i < seeds.length; i++) {
simpleHashes[i] = new SimpleHash(DEFAULT_SIZE,seeds[i]);
}
}
public void set(String value){
if (value == null){
return;
}
for(SimpleHash simpleHash : simpleHashes) {
bitSet.set(simpleHash.hash(value));
}
size++;
}
public boolean contains(String value){
if (value == null){
return false;
}
for (SimpleHash f : simpleHashes){
if (!bitSet.get(f.hash(value))){
return false;
}
}
return true;
}
public static void main(String[] args) {
BloomFilter bloomFilter = new BloomFilter();
bloomFilter.set("果粒陈");
System.out.println(bloomFilter.contains("果粒陈"));
System.out.println(bloomFilter.contains("笨蛋果粒橙"));
}
}
布隆过滤器优点
1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
布隆过滤器缺陷
1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白 名单，存储可能会误判的数据) 2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题
得嘞，这篇博客算是唠完啦！希望我这一通“碎碎念”没把你给念烦咯，要是能博您一笑或者让您有点小收获，那我这码字的功夫可就没白费呀。咱下回再接着侃，各位看官，回见咯~
标签：存储,int,元素,布隆,哈希,过滤器 From： https://blog.csdn.net/h3286918168/article/details/143671697