A. 布隆过滤器既然有错误率，为什么还能应用在key-value系统中
bloom filter的特点是会出现误报，但不会漏报，也就是说对于bloom filter验证的一个数据内文件，可能不包含容你查找的数据项，但是包含你查找的数据项的数据文件它一定是会返回的，key-value系统中bloom filter返回的数据文件还是需要查看里面的内容才能知道是否存在所需的数据的，这就保证了执行结果的正确性和完整性。因此key-value系统不会因此而出错的，只是多访问一些数据文件而已。在数据量很大key-value系统中，建立统一的B+树索引的代价是非常大的，维护成本也很高，因此综合起来bloom filter的性能是最好的。
B. 布隆过滤器
[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实现布隆过滤器。需要根据公式，手动计算字节数组的长度和哈希的个数。
实现过程，待完善。。。。。。