哈希函数
又见哈希
首先回顾下一般计算机课程都会学到的哈希函数
在查询存储在线性表或是树形结构或是数据库类中的数据时候，在这类结构中查找记录时如果是通过比较关键字的大小，那用这种方式就会可能经过多次比较，查询是非常耗时的。
于是就有提出一种通过直接映射方式提升效率的哈希函数法，又称为散列函数，直接通过一定的函数关系称为哈希函数将查询关键字映射到指定的地址值，从而快速查找。一般是有个连续存储空间哈希表。将数据元素的关键字K作为自变量，通过哈希函数，计算出的值，即为该元素的存储地址。
常用的哈希函数比如平方取中法、折叠法、随机数法、除留余数法等。
哈希函数有以下一些特性：
输入的关键值范围无穷大或者就是无法预期的大小，比如数据库记录，
输出的范围有限，比如0到500，
输入一个样输出肯定一样，这是函数性质，
当输入不一样输出也可能一样（哈希碰撞），也是函数性质导致，
不同输入会均匀分布在输出域上（哈希函数的散列性）。比如输入的是0-99 等100个数字，用哈希函数除3取模那输出域就是0,1,2，当我们将这100个数字通过哈希函数进行映射后，0,1,2的数量都会接近33个，也就是分布比较均匀。
哈希的应用
在实际哈希表应用中，它的查询速度近乎 O(1)，就是线性复杂度内，这是因为通过 key 计算 hashcode 的时间是常数项时间，而数组寻址的时间也是常数时间。在实际应用中，每个位置的链表长度不会太长，当到达一定长度后，哈希表会经历一次扩容，这就意味着遍历链表的时间也是常数时间。所以我们增删改查哈希表中的一条记录也是常数时间。开发中我们就会比较多考虑使用它
比如在大数据中的应用，这也是面试中会问到的问题，当然主要是学会应用一些基础方法思想到设计应用过程中。
比如，我们有一个 10TB 的大文件存在分布式文件系统上，存的是 100 亿行字符串，并且字符串无序排列，现在我们要统计该文件中重复的字符串。
我们可以调用 100 台机器来计算该文件，需要将这一百台机器分别从 0-99 标好号，然后在分布式文件系统中一行行读取文件，这时候多台机器是并行的，通过哈希函数计算 hashcode，将计算出的 hashcode 模100 ，根据模出来的值，将该行存入对应的机器中。
这样相同的字符串会存入相同的机器中，再并行 100 台机器，各自分别计算相应的数据，加快统计的速度。
哈希在大数据场景下的不足
但是在大数据场景中，我们其实很难直接使用哈希函数，因为哈希函数需要有限的哈希表存在内存里，而我们如果是PB 、TB级别的数据下，即使用哈希也没足够的内存空间可以使用。例如在黑名单过滤当中，我们有 100 亿的网站黑名单 url 需要过滤，假设一个 url 是 64bytes。如果我们用 hash 表来做，那么我们至少需要 6400 亿字节即 640G 的内存空间（实际所需空间还远大于此），空间消耗巨大，必须要多个服务器来同时分摊内存。
这就又引出了我们的主角，BloomFIlter 布隆过滤器。它的核心思想是充分利用字符串位数组二进制码的表示范围，它充分利用了空间时间的同时，又引入概率思维。
让我们看下什么是BloomFilter
布隆过滤器
布隆过滤器原理
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。可以用于检索一个元素是否在一个集合中。
首先有一个很长的位数组，类似哈希表，在我们将数据插入集合的时候，通过多个互不相关的哈希函数映射到数组多个位置，将算出的位置设为1, 在查询数据是否在集合中时候，通过同样的K个哈希函数看各个对应的位置是否都为1，如果是在集合中，不然就不在集合中。但是这里在也是可能出错，也就可能其实不在。它可以更好利用空间同时加大效率，使用k个哈希函数对应k个bit位。
简单说bloom filter的规则就是不在的一定是不在，在的则不一定在。这也是布隆过滤器的不足，查找成功是有概率的，有一定的错误概率。因此，Bloom Filter不适合那些“零错误”的应用场合。
另一个不足就是不好删除数据，删除的时候不能简单的直接把对应的1置为0，可能会影响其他元素的判断。可以采用[Counting Bloom Filter]
比如a 、b、c是集合S内的元素，通过h1，h2、h3三个哈希函数进行计算
Bloom Filter 实现
接下来问题来了，面的具体问题，我们怎么设置数组长度和哈希函数呢，多少个函数比较好。
这就要计算机科学家去分析证明最优解了，可以看出这个算法提出在70年代，到了大数据时代是大放光彩，科技的魅力可见于此有时候一个基础看似很小的改变可以经久不衰改变世界，敬佩这么多科学家工程师们。
原理和具体证明可以查看论文或是： https://blog.csdn.net/jiaomeng/article/details/1495500
主要的思想是从考虑那个错误率开始，如果我们可以知道误判的概率，那么设计的目标就是尽可能小的组合。
哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考Bloom Filters - the math，Bloom_filter-wikipedia
由预估集合数据量n以及位数组长度m，可以得到一个哈希函数的个数k为：
失误率的计算为
用这些公式估算，像上面url黑名单的例子，如果100 亿个，那么对比哈希表，原来我们需要 640GB，而现在只需要 23GB，而同时实际失误率约为十万分之六。可以适合工程应用了。
BloomFilter的应用
- 除了黑名单，我们在网络应用中也很多这种场景，比如爬虫爬取的时候判断是否爬过这个网址，已经抓取的url可以用bloom filter过滤。
- 过滤垃圾邮件地址，这个类似黑名单的过滤，
- 还比如我们的HBase中用到bloom filter 来进行分配region
HBase 的布隆过滤器
布隆过滤器是 HBase 中的高级功能，它能够减少特定访问模式（get/scan）下的查询时间。不过由于这种模式增加了内存和存储的负担，所以被默认为关闭状态。
HBase 支持如下类型的布隆过滤器：
1、NONE 不使用布隆过滤器
2、ROW 行键使用布隆过滤器
3、ROWCOL 列键使用布隆过滤器
其中 ROWCOL 是粒度更细的模式。
我们可以在代码里看到在util中做了自己定义
为何使用布隆过滤器
前面知道HBase在scan或get的时候，先进如MemStore中，再选择在哪个Region ，再进入都具体的HFile，也就是具体存储数据的HDFS文件，HFIle 是由一个个数据块与索引块组成，他们通常默认为 64KB。HBase 是通过块索引来访问这些数据块的。而索引是由每个数据块的第一行数据的 rowkey 组成的。当 HBase 打开一个 HFile 时，块索引信息会优先加载到内存当中。HBase通过这些块索引进行查询。
但是块索引是相当粗粒度的，我们可以简单计算一下。假设一个行占 100bytes 的空间，所以一个数据块 64KB，所包含的行大概有：(64 * 1024)/100 = 655.53 ~= 700 行。而我们只能从索引给出的一个数据块的起始行开始查询。
如果用户随机查找一个行键，则这个行键很可能位于两个开始键（即索引）之间的位置。对于 HBase 来说，它判断这个行键是否真实存在的唯一方法就是加载这个数据块，并且扫描它是否包含这个键。
同时，还存在很多情况使得这种情况更加复杂。
对于一个应用来说，用户通常会以一定的速率进行更新数据，这就将导致内存中的数据被刷写到磁盘中，并且之后系统会将他们合并成更大的存储文件。在 HBase 的合并存储文件的时候，它仅仅会合并最近几个存储文件，直至合并的存储文件到达配置的最大大小。最终系统中会有很多的存储文件，所有的存储文件都是候选文件，其可能包含用户请求行键的单元格，
当我们随机读 get 数据时，如果采用 HBase 的块索引机制，HBase 会加载很多块文件。如果采用布隆过滤器后，它能够准确判断该 HFile 的所有数据块中，是否含有我们查询的数据，从而大大减少不必要的块加载，从而增加 HBase 集群的吞吐率。
采用 ROW 还是 ROWCOL 布隆过滤器？
这取决于用户的使用模式。如果用户只做行扫描，使用更加细粒度的行加列布隆过滤器不会有任何的帮助，这种场景就应该使用行级布隆过滤器。当用户不能批量更新特定的一行，并且最后的使用存储文件都含有改行的一部分时，行加列级的布隆过滤器更加有用。
例如：
ROW 使用场景
假设有 2 个 Hfile 文件 hf1 和 hf2：
hf1 包含 kv1(r1 cf:q1 v)、kv2(r2 cf:q1 v)
hf2 包含 kv3(r3 cf:q1 v)、kv4(r4 cf:q1 v)
如果设置了 CF 属性中的 bloomfilter（布隆过滤器）为 ROW，那么 get(r1) 时就会过滤 hf2，get(r3) 就会过滤 hf1 。
ROWCOL 使用场景
假设有 2 个 Hfile 文件 hf1 和 hf2：
hf1 包含 kv1(r1 cf:q1 v)、kv2(r2 cf:q1 v)
hf2 包含 kv3(r1 cf:q2 v)、kv4(r2 cf:q2 v)
如果设置了 CF 属性中的 bloomfilter 为 ROW，无论 get(r1,q1) 还是 get(r1,q2)，都会读取 hf1+hf2；而如果设置了 CF 属性中的 bloomfilter 为 ROWCOL，那么 get(r1,q1) 就会过滤 hf2，get(r1,q2) 就会过滤 hf1。
思考练习
Bloom Filter（BF）是一种空间效率很高的随机数据结构，下面描述错误的是__
A. 它是一个判断元素是否存在集合的概率算法
B. 判断如果不在,集合肯定不在;如果在,集合有一定的概率判错
C. 它支持从集合中删除一个元素
D. Hash函数的选择会影响到算法的效果
参考
https://www.shiyanlou.com/courses/37
https://blog.csdn.net/jiaomeng/article/details/1495500
http://edu.cda.cn/course/2239
https://www.cnblogs.com/z941030/p/9218356.html
https://developer.aliyun.com/article/683602
http://lxw1234.com/archives/2015/12/580.htm
