布隆过滤器

1
2
3
4
什么是布隆过滤器
布隆过滤器是一种数据结构，用来判断某个值是否已经存在某个集合中了
优点：空间效率和时间效率极高
缺点：有一定的误识别率，并且随着数据量的增加这个误差的概率会越来越大

布隆过滤器的应用场景

1
2
3
布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等。
当你数据库有大量的数据的时候，你每次进行查询都是很消耗服务器资源的一种行为，并且对数据库的压力也会增大。
这种时候就可以考虑使用布隆过滤器

布隆过滤器原理

1
2
3
4
5
6
当有一个集合，并且集合里面有多个元素时，首先将位数组进行初始化，然后将集合中的数据通过hash函数获得对应的hash编码，这个编码可能对应位数组上的一个点获多个点，然后将位数组上对应的值更改为1.数据越多，对应的位数组上的值被改为1的越多。

位数组:一个很长的二进制向量 

布隆过滤器误判的原因
当你将一个值通过hash函数获得对应的hash编码，可能这个值并没有存储过，但是被判断为已经存在过了。

1030776-20170106143141784-1475031003

哈希函数

1
2
哈希函数是布隆过滤器的基础，布隆过滤器也是根据哈希函数实现的
哈希函数：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码

1030776-20170106142012816-1867044021