其实bloomfilter的问题并不复杂，但是又很多的朋友都不太了解bloomframe科利瑞尔，因此呢，今天小编就来为大家分享bloomfilter的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！
BloomFilter详解(布隆过滤器)
从上式中可以看出，当m增大或n减小时，都会使得误判率减小，这也符合直觉。
现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：
这说明了若想保持某固定误判率不变，布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。
三如何设计bloomfilter
此概率为某bit位在插入n个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使用率需为50%。
bloomfilter的各个参数的错误率
公式推完了，大家可以看看，里面的数学公式基本用到了指数函数对数函数微积分求导法则概率论的知识，大家可以补充看下课本。
个人介绍：杜宝坤，京东联邦学习从0到1构建者，带领团队构建了京东的联邦学习解决方案，实现了电商营销领域支持超大规模的工业化联邦学习解决方案，支持超大规模样本PSI隐私对齐、安全的树模型与神经网络模型等众多模型支持，并且实现了广告侧等业务领域的落地，开创了新的业务增长点，产生了显著的业务经济效益。
个人喜欢研究技术。基于从全链路思考与决策技术规划的考量，研究的领域比较多，从架构、数据到算法与算法框架均有涉及。欢迎喜欢技术的同学和我交流，邮箱： baokun06@163.com
bitcoin bloom filter
20180901
冉小龙（xiaolong.ran）
致谢：齐巍
问题：在大数据场景下，我们如何从海量的数据池中去判断某一个东西是否存在它里面？
思路：要去构建这个海量数据池，我们存储的方案无外乎这几种
一般来讲，计算机中的**是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当**比较小时，这个问题不显著，但是当**巨大时，哈希表存储效率低的问题就显现出来了。关于这个，只需要根据元素的数量和大小简单的计算一下就知道了。虽然可以适用分布式K-V系统（如Redis）来承载，但是成本仍然高昂。布隆过滤器只需要哈希表 1/8到 1/4的大小就能解决同样的问题，以一定的误判率为代价。所需要的内存大小可以通过公式精确的计算出来： Bloom Filter Calculator。
降低误判率
如果哈希函数的个数多，那么在对一个不属于**的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。所以就需要权衡，具体怎么权衡能？不知道
BloomFilter中不允许有删除操作，因为删除后，可能会造成原来存在的元素返回不存在。因为假设两个hash函数hash到同一个位置的时候，看到这个位置为1，就不做处理了，所以，你删除之后，这个位置的标记1也跟着删除了。
把存储数组的每一个元素扩展一下（原来是1b）用来存储该位置被置1的次数。存储是，计数次数加一；删除的时候，计数次数减一。
观察上图，假设某个元素通过hash映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在**中，也可能对应的都是1，这是误判率存在的原因。
比特币中布隆过滤器是在 BIP-0037中提到，主要是提供给spv节点使用,主要是去过滤发送给他们的交易。
Bloom Filter就是一个过滤器，用来过滤不属于钱包的UTXO,通过bloom filter，钱包既能保护用户的隐私，还能节省存储空间和宽带。
规定bloom filter最多允许有50个hash函数，最大是3.5Kb左右
基础结构：
nflag:
序列化操作：
生成不同hash函数的操作：
按照bloom filter的算法对新增的key做几次hash然后修改位数组:
添加操作：
filter具体过滤过程
获取指定blockhash中满足bloom filter的block内容
Proces**essage:
load filter:
add filter:
clear filter
假设目前没有bloom filter，用户A是一个spv节点的用户，他有两个pubKey，那么用户A就只会接收跟我这两个pubKey相关的交易，因为整个网络是明文传输的，我很容易通过监控中心，直接获取到该用户的账户余额等信息；但是加入bloom filter就不一样了，bloom filter的缺点恰好可以用来保护用户的隐私，因为bloom filter的假阳性是可以控制的，我可以适当的增加这个假阳性的概率，进而把不属于我这个pubKey的交易也发到我账户上，真真假假，虚虚实实，混淆有恶意行为的用户的视听。
如何使用bloomfilter构建大型Java缓存系统
在如今的软件当中，缓存是解决很多问题的一个关键概念。应用可能会进行CPU密集型运算。当然不想让这些运算一边又一边的重复执行，相反，可以只执行一次，把这个结果放在内存中作为缓存。有时系统的瓶颈在I/O操作上，比如不想重复的查询数据库，想把结果缓存起来，只在数据发生变化时才去数据查询来更新缓存。
与上面的情况类似，有些场合下需要进行快速的查找来决定如何处理新来的请求。例如，考虑下面这种情况，需要确认一个URL是否指向一个恶意网站，这种需求可能会有很多。如果把所有恶意网站的URL缓存起来，那么会占用很大的空间。或者另一种情况，需要确认用户输入的字符串是包含了美国的地名。像“华盛顿的博物馆”——在这个字符串中，
这就是为什么要跨越基本的数据结构map，在更高级的数据结构像布隆过滤器（bloomfilter）中来寻找答案。可以把布隆过滤器看做Java中的**（collection），可以往里面添加元素，查询某个元素是否存在（就像一个HashSet）。如果布隆过滤器说没有这个元素，那么可以肯定不含有这个元素，但是如果布隆过滤器说有某个元素，那么这个结果可能是错误的。如果在设计布隆过滤器时足够细心，可以把这种出错的概率控制在可接受范围内。
（1）解释
布隆过滤器被设计为一个具有N的元素的位数组A（bit array），初始时所有的位都置为0.
（2）添加元素要添加一个元素，需要提供k个哈希函数。每个函数都能返回一个值，这个值必须能够作为位数组的索引（可以通过对数组长度进行取模得到）。然后，把位数组在这个索引处的值设为1。例如，第一个哈希函数作用于元素I上，返回x。类似的，第二个第三个哈希函数返回y与z，那么：
（3）查找元素通过上面的解释可以知道，如果想设计出一个好的布隆过滤器.必须遵循以下准则：
好的哈希函数能够尽可能的返回宽范围的哈希值。
位数组的大小（用m表示）非常重要：如果太小，那么所有的位很快就都会被赋值为1，这样就增加了误判的几率。
哈希函数的个数（用k表示）对索引值的均匀分配也很重要。
计算m的公式如下：
这里p为可接受的误判率。
计算k的公式如下：
这里k=哈希函数个数，m=位数组个数，n=待检测元素的个数（后面会用到这几个字母）。
（4）哈希算法哈希算法是影响布隆过滤器性能的地方。需要选择一个效率高但不耗时的哈希函数，在论文《更少的哈希函数，相同的性能指标：构造一个更好的布隆过滤器》中，讨论了如何选用2个哈希函数来模拟k个哈希函数。首先需要计算两个哈希函数h1(x)与h2(x)。然后，可以用这两个哈希函数来模仿产生k个哈希函数的效果：
这里i的取值范围是1到k的整数。
Google guava类库使用这个技巧实现了一个布隆过滤器，哈希算法的主要逻辑如下：
（5）应用从数学公式中，可以很明显的知道使用布隆过滤器来解决问题。但是，需要很好地理解布隆过滤器所能解决问题的领域。像可以使用布隆过滤器来存放美国的所有城市，因为城市的数量是可以大概确定的，所以可以确定n（待检测元素的个数）的值。根据需求来修改p（误判概率）的值，在这种情况下，能够设计出一个查询耗时少，内存使用率高的缓存机制。
（6）实现Google Guava类库有一个实现，查看这个类的构造函数，在这里面需要设置待检测元素的个数与误判率。
专题推荐：
