高效查找的秘密武器二：布隆过滤器
最近学了这个布隆过滤器，所以小编来分享下这个神奇的数据结构
引入：
在我们日常生活中，当然这里特指是编程中时，经常遇到要判断一个元素是否在集合中，比如判断一个单词/词语，是否在已知的字典中；在网络爬虫中，一个网址是否被访问过，最直接的方法就是说将集合中的元素全部放入到计算机中，遇到一个新网址的时候，将它和集合中的元素直接比较即可。
那么，这些情况，一般是使用哈希表来进行存储，毕竟它的好处就是快速准确地查询，缺点嘛，就是浪费存储空间。而且，这里还是涉及一个存储效率的问题，这个哈希表存储集合小的时候，不明显，一旦变得很大了，那么存储效率问题就上来了。
比如说，我们日常使用的邮件一般都具有垃圾邮件过滤功能，比如使用较为广泛的Gmail
如若我们像上述那样记录哪些发来的垃圾邮件地址，然后发送者们又不停创建，我们又要接着存储，一旦达到一个量级，比如几十亿那样的，这些数据放到普通电脑是行不通的，只能放到大量的网络服务器，
此时，Email一般是转换成一个八个字节的信息指纹，加上哈希表存储效率一般只有50%，那么又要16个字节存储这个信息指纹，一亿个，大约需要1.6G
几十亿个，大约需要上百G的内存，除非是超级计算机，否则一般的服务器是存储不下的。
所以我们需要一个新的数据结构来解决下这个问题。
那么就是今天要分享的布隆过滤器。
布隆过滤器，是由布隆在1970年提出的一种紧凑型，比较巧妙的概率型数据结构，其特点就是高效的插入和查找，它可以告诉你一样东西一定不存在，或者可能存在，它是由多个哈希函数通过映射关系到位图中的，大大的节省了存储空间。
那么刚刚讲到，为什么是它可以告诉你一样东西一定不存在，或者可能存在呢？
举个例子：
上述的例子是演示下，是如何存储的，其实是和之前的位图是有些类似的
那么再下来是告诉下是怎么出现可能存在的
就比如这里，这里给到的字符串：百度、字节
然后通过一些哈希函数，确实是出现了重叠，那么此时呢，我们的确也是判断不了百度或者字节是否是一定存在，毕竟它们的对应到的比特位都为1，肉眼看去是这样的，但是呢程序运行起来就带有不确定性了。
所以呢，这个布隆过滤器是带有一定的误判，与之对应的是，误判率也是需要考虑的。
那么接着呢，我们来模拟实现下这个布隆过滤器一些操作
初始化：
那么前面说到，这个要把我们的字符串数据放到位图中，是需要进行哈希的，所以呢，我们要创建几个哈希函数
那么我们单独对这个哈希函数的创建新起一个类，
在这个类里面呢，我们就要进行哈希函数的创建了，那么这个哈希函数呢，又得是不同哈希函数，可不敢一样的，一样的话，那就全部哈希到一个位置了
那么要这个哈希函数的不一样呢，我们可以根据容量和其模拟给定的随机种子来使得最终的哈希函数是不一样的，
class simpleHash{
//这个是代表容量，与哈希有关
public int cap;
//随机值
public int seed;
public simpleHash(int cap,int seed){
this.cap=cap;
this.seed=seed;
}
public int hash(String val){
int h;
//利用源码中的hashMap来模仿hash值
//seed的不同导致哈希函数不一样
return (val == null) ? 0 : (seed*(cap-1))&(h = val.hashCode()) ^ (h >>> 16);
}
}直接上代码来理解下吧
这里定义的cap表示容量，seed表示随机种子。
值得说明是，我们这里是模拟实现，不是特别严格要求的，所以呢，随机种子也不是真的随机，是我们随便输入数字的。
那么接着实现了这个hash方法，这个哈希过程呢，是借鉴了Java中HashMap里一些思路
就是通过控制seed的不同，然后呢就可以确定最终的哈希函数返回的哈希值不同。
当然，还没有完的。
接着我们就真正的开始初始化哈希函数了
代码：
public class MyBloom {
//给定默认的位图大小
public final static int DEFAULT_Size = 1 << 24;
public BitSet bitSet;
public static final int[] seeds = new int[]{3, 7, 9, 11, 17, 21};
public int size;
public simpleHash[] simpleHashes;
public MyBloom() {
bitSet = new BitSet(DEFAULT_Size);
//生成随机函数
simpleHashes=new simpleHash[seeds.length];
for (int i = 0; i < seeds.length; i++) {
simpleHashes[i] = new simpleHash(DEFAULT_Size, seeds[i]);
}
}结合代码来讲解或许会好些
这个布隆过滤器是用到位图的，所以我们索性直接用标准库中的BitSet了
然后呢，创建一个随机的种子数组，并对其初始化
接着再创建一个随机种子数组，然后对其进行初始化，在MyBloom构造方法中
注意这里的new simpleHash第一个参数是指的是位图中的容量，所以我们一开始设置
public final static int DEFAULT_Size = 1 << 24;是代表位图的容量。
我们直接把 DEFAULT_Size这个作为参数给定就好了，
第二个参数嘛，就是作为随机种子，然后去生成一个哈希值。
这一个个simpleHash对象就放到了simpleHashes[]中
所有的初始化完了，那么接着来写add和contains方法吧
add：
这个方法是设置比特位，使其传入的字符串状态标记为存在
思路：
遍历随机哈希数组，即simpleHashes[]，然后调用其hash（）返回的值，作为其关键值，再让位图设置对应比特位
注意，这里是六个随机种子，所以有六个哈希函数，所以要遍历六次
代码：
/**
* 添加数据在布隆过滤器中
* @param val
*/
public void add (String val){
//利用不同的函数来将值放入到布隆过滤器中
for (simpleHash simpleHash : simpleHashes) {
int hashVal = simpleHash.hash(val);
bitSet.set(hashVal);
}
}contains：
这个是查看字符串是否包含在布隆过滤器中
思路：
首先还是得让字符串通过哈希函数，获取一个关键值，然后呢，再让位图的get（）方法判断是否是为1
注意add的时候，是六个哈希函数，那么对应的是六个比特位被设置了，所以检查的时候，也要加检查六个比特位是否都是1，但凡有一个不是，那么这个字符串是不存在的
代码：
public boolean contains (String val){
//要知道这个val在哪，还是得拿到一个哈希值先
for (simpleHash simpleHash : simpleHashes) {
int hashVal = simpleHash.hash(val);
boolean flg = bitSet.get(hashVal);
if (flg) {
return true;
}
}
return false;
}删除：
布隆过滤器中，不能直接支持删除元素，因为删除元素，即是把对应的比特位设置为0，那么某些个比特位也是另外一个元素所以持有的，那么此时就是影响到了其他元素。
不过有这样的一个思路：
将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈 希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删 除操作。
那么回顾一下，布隆过滤器有什么优缺点吧
优点：
1.增加和查询的复杂度为O（k），（k为哈希函数的个数，一般比较小），与数据量大小无关
2.哈希函数相互之间没有关系，方便硬件并行运算
3.布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4.数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
5.使用同一组散列函数的布隆过滤器可以进行交，并，差运算
缺点：
无法确认元素是否真正在布隆过滤器中
最后，简要说明下优点5，如何理解
交集：
交集是指两个集合中同时存在的元素。
假设有两个布隆过滤器，比如A、B
那么A中对应比特位和B中对应的比特位，进行&操作，都为1，意思是一个东西存在两个布隆过滤器中，即交集就是它
并集：
并集是指将两个集合中的所有元素合并，去除重复的元素
假设有两个布隆过滤器，比如A、B
那么A中对应比特位和B中对应的比特位，进行 | 操作，只要A或者B中，存在1，那么表示该位有一个元素存在两者集合中，那么只要保存，其中的结果就是并集了
差集：
差集是指在一个集合中存在，但不在另一个集合中存在的元素。
假设有两个布隆过滤器，比如A、B
那么A中对应比特位和B中对应的比特位，进行 与非 操作，
即先与操作，再取非
此时，如若A中比特位是1，且B中的比特位是2，那么此时说明该元素在A中存在，不在B中。
源码：
class simpleHash{
//这个是代表容量，与哈希有关
public int cap;
//随机值
public int seed;
public simpleHash(int cap,int seed){
this.cap=cap;
this.seed=seed;
}
public int hash(String val){
int h;
//利用源码中的hashMap来模仿hash值
//seed的不同导致哈希函数不一样
return (val == null) ? 0 : (seed*(cap-1))&(h = val.hashCode()) ^ (h >>> 16);
}
}
public class MyBloom {
//给定默认的位图大小
public final static int DEFAULT_Size = 1 << 24;
public BitSet bitSet;
public static final int[] seeds = new int[]{3, 7, 9, 11, 17, 21};
public int size;
public simpleHash[] simpleHashes;
public MyBloom() {
bitSet = new BitSet(DEFAULT_Size);
//生成随机函数
simpleHashes=new simpleHash[seeds.length];
for (int i = 0; i < seeds.length; i++) {
simpleHashes[i] = new simpleHash(DEFAULT_Size, seeds[i]);
}
}
/**
* 添加数据在布隆过滤器中
* @param val
*/
public void add (String val){
//利用不同的函数来将值放入到布隆过滤器中
for (simpleHash simpleHash : simpleHashes) {
int hashVal = simpleHash.hash(val);
bitSet.set(hashVal);
}
}
/**
*
* @param val
*/
public boolean contains (String val){
//要知道这个val在哪，还是得拿到一个哈希值先
for (simpleHash simpleHash : simpleHashes) {
int hashVal = simpleHash.hash(val);
boolean flg = bitSet.get(hashVal);
if (flg) {
return true;
}
}
return false;
}
}原文地址：https://blog.csdn.net/m0_75169015/article/details/144299622
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！