布隆过滤器hash

『壹』 布隆过滤器

[TOC]

通过解决方案：

Java中如将数据存储在内存中，最简单的算法结构是HashMap。通过HashMap判断key是否存在，来判断数据是否存在。通过hash算法查找元素，时间复杂度基本是 O(1) （可能存在hash冲突后转换成链表或红黑树的情况，时间复杂度的影响可以忽略）。

使用HashMap速度很快，存储简单，绝大部分场景可以使用。但是HashMap 占用的空间比较大 ：

为什么出现布隆过滤器：

举例：

如1000万个Integer存储在内存中，占用空间为：4x32x10000000位，即1220兆。如布隆过滤器通过4字节存储（布隆过滤器通过多次hash对数据计算后-->几次hash根据数据量指定，得到多个数据， 占用多个位 ），则占用空间为610M。比原有空间少一半。

个人觉得，此比较在字符等的比较中尤为有效。
一个字符串多个字符，根据编码方式，一个字符两个或三个字节，如10个字符，字符串存储占用20个字节，还有相关字符串相关的类信息的内存占用。
位存储，根据数据量的大小，hash的位数，灵活计算。如4个字节，则是原hashMap占用空间的五分之一。

（1）定义字节向量

先定义一个指定长度的字节数组（字节数组，数组内每个元素的值）。

如长度为8（一个字节大小），默认所有元素值均为0，如下：

（2）计算哈希值

将要写入过滤器的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。

如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。

（3）更新字节向量

将计算出的字节向量的索引， 对应的字节向量中的元素值更高为1 （无论之前为0或者为1，均更改为1）。如下：

（1）计算哈希值

将要判断过滤器中是否存在的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。

如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。

注意：哈希函数的判断方式和计算索引的方式，需和写入数据时完全一致。

（2）判断是否存在

如原字节数组中，对应1，3，7中存在的元素的值都为1。则判定为此元素 可能存在 ，但凡有一个元素的值不为1，则判定此元素 一定不存在 。

布隆过滤器，主要需实现的目标是， 在指定的数据个数范围内，满足误判率在设定的范围内 ，误判率太高的话，无法起到过滤数据的情况，误判率不能为0。

因此需要计算两个数据来满足 存储数据的个数 和 误判率 ：

使用布隆过滤器的决定性因素之一，就是此算法插入数据和查询数据的速度必须非常快。因此在对数据进行哈希运算的时候， 需选择计算快的哈希算法 。

而且， 写入数据以及查询数据的哈希算法，顺序和算法都需完全一致 。

待完善。。。。。

可以通过google的 guava ，在内存中轻松实现布隆过滤器。

无需手动计算满足字节数组的长度和哈希个数，只需要输入 拟输入数据的个数 和 期望误判率 即可。

不输入期望误判率的情况下，误判率为0.03，即100个非范围内的数据进行校验时，约三个数据会判定为存在。

多次执行，结果一致，根据结果判定：

内存的存储存在局限性，可以使用redis中的bitMap来实现字节数组的存储。

使用redis实现布隆过滤器。需要根据公式，手动计算字节数组的长度和哈希的个数。

实现过程，待完善。。。。。。

『贰』 布隆过滤器的优点

相比于其它的数抄据结袭构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能；
k和m相同，使用同一组Hash函数的两个布隆过滤器的交并差运算可以使用位操作进行。
布隆过滤器

『叁』 看过的视频让用户不再观看为什么使用布隆过滤器而不是直接使用setBit与getBit进行取值比对呢

不行。

因为布隆过滤器的原理是用多个hash函数对id进行hash后得到一系列值，而在布隆数组中看这些值回对应答的位上是否命中，如果都命中说明这个值重复。
用id不经过hash直接去对比，乍一想好像可以，但是你想想，假如id是10位，并且我们只用数字，那么布隆过滤器的长度只有10位（0123456789）,这个长度的过滤器几乎没法使用，容量太低，误差率太高。即使算上大小写字母，也只有62个，看似62很多，但是这里定死了id必须用这62个字符，而假如中间加一层hash，那id用什么字符和我布隆过滤器用什么字符以及过滤器的长度都可以自由指定，灵活很多。

『肆』 布隆过滤器

布隆过滤器 （英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为，，。

这个时候，布隆过滤器（Bloom Filter）就应运而生。

了解布隆过滤器原理之前，先回顾下 Hash 函数原理。

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：

所有散列函数都有如下基本特性：

但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：

[图片上传失败...(image-303c04-1595324887187)]

当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 ，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。

如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器的典型应用有：

知道了布隆过滤器的原理和使用场景，我们可以自己实现一个简单的布隆过滤器

分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到 Redis，是的，Redis 也实现了布隆过滤器。

当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入OSS、S3这类对象存储中。

Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。

在已安装 Redis 的前提下，安装 RedisBloom，有两种方式

直接编译进行安装

使用Docker进行安装

使用

布隆过滤器基本指令：

我们只有这几个参数，肯定不会有误判，当元素逐渐增多时，就会有一定的误判了，这里就不做这个实验了。

上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。

Redis 还提供了自定义参数的布隆过滤器，bf.reserve 过滤器名 error_rate initial_size

但是这个操作需要在 add 之前显式创建。如果对应的 key 已经存在，bf.reserve 会报错

我是一名 Javaer，肯定还要用 Java 来实现的，Java 的 Redis 客户端比较多，有些还没有提供指令扩展机制，笔者已知的 Redisson 和 lettuce 是可以使用布隆过滤器的，我们这里用 Redisson

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。