=Start=
缘由：
对我来说，在无事可做的时候学一些东西是打发时间的最佳方式。而且这个东西可能还有些实际用处。
正文：
参考解答：
1、Bloom-Filter算法简介
Bloom-Filter，即布隆过滤器，1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中。
Bloom-Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom-Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom-Filter判断元素不在集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。因此，Bloom-Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom-Filter比其他常见的算法（如hash，折半查找）极大节省了空间。
误判——是因为选用的Hash算法存在碰撞的可能。
2、Bloom-Filter算法基本思想
计算某元素x是否在一个集合中，首先能想到的方法就是将所有的已知元素保存起来构成一个集合R，然后用元素x跟这些R中的元素一一比较来判断是否存在于集合R中；我们可以采用链表等数据结构来实现。但是，随着集合R中元素的增加，其占用的内存将越来越大。试想，如果有几千万个不同网页需要下载，所需的内存将足以占用掉整个进程的内存地址空间。即使用MD5，UUID这些方法将URL转成固定的短小的字符串，内存占用也是相当巨大的。
于是，我们会想到用Hash table的数据结构，运用一个足够好的Hash函数将一个URL映射到二进制位数组（位图数组）中的某一位。如果该位已经被置为1，那么表示该URL已经存在。
Hash存在一个冲突（碰撞）的问题，用同一个Hash得到的两个URL的值有可能相同。为了减少冲突，我们可以多引入几个Hash，如果通过其中的一个Hash值我们得出某元素不在集合中，那么该元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时，才能确定该元素存在于集合中。这便是Bloom-Filter的基本思想。
原理要点：一是位数组，二是k个独立hash函数。
参考链接：
- 海量数据处理算法—Bloom Filter
http://en.wikipedia.org/wiki/Bloom_filter - Bloom Filter 算法处理海量数据
- BloomFilter + Redis 大数据去重策略的实现
- BloomFilter（大数据去重）+Redis（持久化）策略
- 基于Redis的布隆过滤器(Python实现)# 可以使用
- Bloom Filter在Python上的实现与优缺点分析
# 完全满足常规使用的版本
https://github.com/jaybaird/python-bloomfilter
# 更快的版本
https://axiak.github.io/pybloomfiltermmap/
https://github.com/axiak/pybloomfiltermmap
=END=
《 “Bloom过滤器学习和使用” 》 有 5 条评论
亿万级数据处理的高效解决方案
https://www.jianshu.com/p/5448f130b94d
`
何谓海量数据处理？
基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。
那解决办法呢?
· 针对时间，我们可以采用巧妙的算法搭配合适的数据结构，如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树
· 针对空间，无非就一个办法：大而化小，分而治之（hash映射），把规模大化为规模小的，各个击破
处理海量数据，不外乎：
· 分而治之/hash映射 + hash统计 + 堆/快速/归并排序
· 双层桶划分
· Bloom filter/Bitmap；
· Trie树/数据库/倒排索引；
· 外排序；
· 分布式处理之Hadoop/Mapreduce。
`
如何判断一个元素在亿级数据中是否存在？
https://crossoverjie.top/2018/11/26/guava/guava-bloom-filter/
https://github.com/crossoverJie/JCSprout
`
1. 前言
2. 常规实现
3. Bloom Filter
4. 自己实现一个布隆过滤
5. Guava 实现
6. 总结
布隆过滤的应用还是蛮多的，比如数据库、爬虫、防缓存击穿等。
特别是需要精确知道某个数据不存在时做点什么事情就非常适合布隆过滤。
`
实战:用Redis快速实现BloomFilter！
https://zhouzhipeng.com/blog/#/articles/implementing-bloomfilter-with-redis
`
背景
方案选型
实现细节
注意事项
`
【译文】理解布隆过滤器
https://www.linuxzen.com/understanding-bloom-filter.html
https://osoco.es/thoughts/2019/05/understanding-bloom-filters-with-pharo-smalltalk/
https://github.com/osoco/PharoPDS
`
布隆过滤器提供了一个替代的数据结构，可以实现在添加元素或检查元素是否是成员上，不管在空间和时间上都可以保证常量级的性能，并且和已经添加到过滤器中的元素数量是无关的。
为了达到如此高效的表现所需要付出的代价是：布隆过滤器是一个概率性的数据结构。Bloom 他在开创性的论文中解释如下：
新的方法打算比传统相关的方法减少一定量哈希码所需要的空间。通过利用某些应用可以容忍少量的误差来减少空间的使用，特别是那些拥有大量的数据参与无法通过传统的方法保留核心哈希区域的应用。
真实世界的例子：
Medium 使用布隆过滤器避免推荐给用户已经读过的文章。
Google Chrome 使用布隆过滤器识别恶意 URL。
Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。
Squid Web 代理使用布隆过滤器处理缓存摘要。
`
用户日活月活怎么统计 – Redis HyperLogLog 详解
https://mp.weixin.qq.com/s/AvPoG8ZZM8v9lKLyuSYnHQ
https://thoughtbot.com/blog/hyperloglogs-in-redis
`
HyperLogLog 是一种概率数据结构，用来估算数据的基数。数据集可以是网站访客的 IP 地址，E-mail 邮箱或者用户 ID。
基数就是指一个集合中不同值的数目，比如 a, b, c, d 的基数就是 4，a, b, c, d, a 的基数还是 4。虽然 a 出现两次，只会被计算一次。
使用 Redis 统计集合的基数一般有三种方法，分别是使用 Redis 的 HashMap，BitMap 和 HyperLogLog。前两个数据结构在集合的数量级增长时，所消耗的内存会大大增加，但是 HyperLogLog 则不会。
Redis 的 HyperLogLog 通过牺牲准确率来减少内存空间的消耗，只需要12K内存，在标准误差0.81%的前提下，能够统计2^64个数据。所以 HyperLogLog 是否适合在比如统计日活月活此类的对精度要不不高的场景。
这是一个很惊人的结果，以如此小的内存来记录如此大数量级的数据基数。下面我们就带大家来深入了解一下 HyperLogLog 的使用，基础原理，源码实现和具体的试验数据分析。
`