从哈希到布隆过滤器

 从Hash 到布隆过滤器

Hash表

  哈希表是存储集合常用的数据结构。添加元素时，我们将元素通过哈希函数映射到哈希表的某个存储单元上，并把该元素保存在此单元；要判断元素是否属于集合，可以使用相同的哈希函数找到该元素对应的存储单元，如果该单元为空，说明元素还未添加进集合；如果该单元不空，则取出内容与该元素进行比较，只有经过比较相同后才断定该元素属于集合。可以看出，哈希表最消耗空间的部分是将元素保存到存储单元上。因为不同元素通过哈希函数有可能对应相同的单元，所以我们必须将元素保存到单元上，才能保证有足够的信息准确区分对应相同单元的不同元素。

信息指纹

    在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它 是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。我们都需要一种信息来标记我们所查过或者我们被访问过的东西，而且这种信息都是唯一的，区别与其他的一种信息。所以我们将任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的“指纹”。

在爬虫中网址的消重上，需要在哈希表中纪录已经访问过的网址（URL)。假设现在要存储在哈希表中如果以字符串的形式直接存储网址，既费内存空间，又浪费查找时间。为什么会是这样呢？答案如下：

一方面，现在的网址一般都较长，多的达到一百甚至几百个字符。而哈希表的存储效率一般只有 50%（个人理解：为了避免高碰撞，一般哈希存到一半时都翻倍或采取其他策略），所以很费内存；

另一方面，由于比较费空间，假设存储的URL大概有500M，由于哈希的存储效率，实际就需要1G空间存储，即使把这些网址放到了计算机的内存中，由于网址长度不固定，以字符串的形式查找的效率会很低（个人理解：虽然说哈希的查找效率为O(1)，但是由于字符串长度不固定，在查找某个特定串的时候无法根据偏移量直接找到或者找到也应该比较费劲，如果忽略串的长度不固定，采用统一长度的内存存储每个串，那又太费空间了，所以很麻烦）。

        那么怎么办？我们应该想法既让空间节省下来（不直接存储字符串），又能在查找上提高效率？

        这就需要有一种数据结构既能够能将大量的数据的内存存储需要降下来，同时也也能提供也有很高的查询效率，所以就有了布隆过滤器。布隆过滤器中要先了解信息指纹是什么，后面就是我们要介绍的。

       现假定网址的平均长度为一百个字符，那么存贮 200 亿个网址本身至少需要 2 TB，即两千 GB 的容量，考虑到哈希表的存储效率一般只有 50%，实际需要的内存在 4 TB以上，这么大的空间查找起来也怪不容易的。因此如果我们能够找到一个函数，将这 200 亿个网址随机地映射到128 二进位即 16 个字节的整数空间，这样每个网址只需要占用 16 个字节而不是原来的一百个，这就能把存储网址的内存需求量降低到原来的 1/6。这个16 个字节的随机数，就称做该网址的信息指纹（Fingerprint)

Bitmap数据结构

       因为布隆过滤器是位图+哈希表构成的，所以他的基础知识一定要知道，位图是什么？

      位图就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

 unsigned int bit[N];

在这个数组里面，可以存储 N * sizeof(int)个数据，但是最大的数只能是N * sizeof(int) - 1。假如，我们要存储的数据范围为0-15，则我们只需要使得N=1

数据为【5，1，7，15，0，4，6，10】，则存入这个结构中的情况为

 

布隆过滤器（简单的介绍布隆过滤器）

   我们以一个实例来说明他布隆过滤器 是如何构造的;

1 垃圾邮件过滤中的黑白名单

爬虫(Crawler)的网址判重模块

 

下面详细的阐述一个例子，先是插入：

 

1 为了存储一亿个电子邮件地址

2 建立一个含有十六亿二进制比特，也就是两亿字节

3 将十六亿的比特全部设置为0

4 我们用八个不同的哈希函数，以电子邮件地址为键，算出值，有8个（也许不是数字）

5  我们再一个哈希函数，分别以这8个值为键，会得到8个数值（范围为1到十六亿的某个数字）

6  以上一步算出的8个数值为下标，将这8个位置的二进制都设置为1（存储了一个地址）

下一篇会有对布隆过滤器的详细分析以及实现

<!--EndFragment-->