1. 哈希表

1.1. 背景

• 问题：
  -- 在开发过程中，我们经常需要判断一个元素是不是在一个集合里；
  -- 比如：我们现在有个爬虫，已经抓了 十亿 个 url，我们在接下来的抓取过程中，需要先判断 url 是否已经被爬过了，如果 url 已经下载过了那我们就不再爬取，那如何实现该逻辑呢？
• 思路：
  -- 一般的思路是将所有元素保存起来，然后将对象和所有元素的集合进行比对，链表、树等等数据结构都是这种思路；
  -- 但是这种思路有个问题，随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也会越来越慢，简言之：资源浪费、性能低下；

试想一下：
-- 假设我们在 redis 中使用指纹完成去重过程，一个去重指纹我们按照 40Bytes 来计算， 8GB（8GB=8589934592Bytes）的内存大约可以存储 214,748,000（2亿）个指纹；
-- 按照这样计算的话，如果我们的 url 数量达到十亿级的话，需要去重的指纹占用空间将达到 40GB，这对于服务器内存来说将是一场灾难；

• 针对上面的问题，我们不禁要问什么样的数据结构，可以解决 元素增加、存储空间增大、检索速度下降 这个问题呢?
• 这里，我们引入一种叫作哈希表（Hash table）的数据结构，它可以通过一个 Hash 函数将一个元素映射成一个位阵列（Bit Array）中的一个点，检索时我们只要看看这个点是不是 1 就知道可以集合中有没有它了；
• 具体来说：
  -- 之前的查找是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等就缩小范围继续查找，经典二叉树查、冒泡查找找其实都是为了尽可能缩小查找对象；
  -- 哈希表是完全另外一种思路：当我知道 key 值以后，我就可以直接计算出这个元素在集合中的位置，然后到这个位置里找到这个元素，不需要像上面那样把所有元素当做潜在查找对象；

• 哈希的核心作用：
  -- 哈希的核心作用，是使元素的存储位置与它的关键码之间能够建立一一映射的关系，在查找时通过该函数可以很快找到该元素；
  -- 举个例子：如果全部数据是由一个个房屋组成的居民区的话，哈希就像是一个 门牌号地址生成器，给每一栋房子生成一个独一无二的 门牌号地址，当想要找某栋房屋的时候，只需要通过它的 门牌号地址 就可以知道这栋房子在什么地方，然后就能快速的找到这栋房子。

1.2. 哈希函数

• 定义：
  -- 给定表 M 存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表 M 为哈希（Hash）表，函数 f(key) 为哈希（Hash）函数；
• 理解：
  -- 哈希表（Hash table），也叫散列表，是根据关键码值（Key value）而直接进行访问的数据结构，也就是说它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
  -- 这个映射函数叫做 哈希函数（散列函数），存放记录的数组叫做 哈希表（散列表）；

11.jpg

• 构造哈希函数的原则是：
  -- 函数本身便于计算；
  -- 计算出来的地址分布均匀，即对任意输入 k、f(k) 对应不同地址的概率相等，目的是尽可能减少冲突；
• 哈希函数构造方法：
  -- 数字分析法，如数值取模；
  -- 平方取中法；
  -- 分段叠加法；
  -- 除留余数法；
  -- 伪随机数法；
• 最典型的哈希函数是 取模法，即 H(key) = key % p，p <= m，（m 为所有元素的个数，另外 p 可以为小于等于 m 的最大素数）；

如欲详细了解，请参阅《https://www.cnblogs.com/zzdbullet/p/10512670.html》文章中 哈希函数的构造方法 相关章节内容，此处不赘述。

1.3. 哈希的散列性

• 哈希表之所以又叫 散列表，是因为哈希函数具有散列性；
• 哈希函数的散列性，指的是不同输入会均匀分布在输出域上；
• 哈希函数的作用，就是努力的把比较大的数据指向相对较小的空间中；

举个栗子：
-- 输入 0-99 的 100 个数字，用哈希函数除 3 取模那输出域就是 0、1、2；
-- 当我们将这 100 个数字通过哈希函数进行映射后，0、1、2 的数量都会接近 33 个，也就是分布比较均匀；

• 哈希散列性的经典应用：
  -- 场景：如果现在有一个超级大的文件，需要统计其中重复的字符串 ，我们要怎么办？
  -- 已知：可以供给1000台计算机；
  -- 思路：可以使用哈希的散列性对这个超大文件分流；
  -- 具体操作：对大文件进行多行读取，每一行都计算哈希值，并取模 1000，则这些字符串均匀分布在 0-999 范围内；
  -- 给电脑编号 0-999，对应分布在一个范围内的一些字符串用同一台电脑进行处理，达到大数据分流的效果；
  -- 每台电脑只统计自己处理的重复字符串，最后将结果进行汇总。

1.4. 哈希函数特点

-- 输入的值范围可以无穷大，比如数据库记录；
-- 输出的值范围却是有限的，比如上面的 0 到 999；

-- 输入相同输出肯定相同；
-- 输入不相同输出也可能相同（哈希冲突）；

1.5. 哈希冲突

• 哈希冲突，简言之就是 输入不同，但有可能得到相同的输出；
• 哈希冲突是 Hash 最大的问题；

1.5.1. 哈希冲突产生的原因

• 为什么会有哈希冲突呢？其实就是因为哈希函数对输入值进行映射的时候，哈希表的位桶的数目远小于输入的关键字的个数，所以对于输入域的关键字来说，很可能会产生这样一种输入不同、输出却相同的情况；
• 用个形象一点的比喻来说，就是饭店来了 100 个客人，但店里却只有 10 个位置，那么每个作为上要安排 10 个人，这 10 个人在一个位子上怎么坐得下呢？这就是哈希冲突的原因。

1.5.2. 哈希冲突的解决方法

• 开放地址法：
  -- 用开放地址处理冲突就是当冲突发生时，形成一个地址序列，沿着这个序列逐个深测，直到找到一个“空”的开放地址，将发生冲突的关键字值存放到该地址中去；

• 链地址法：
  -- 把所有关键字为同义词的记录存储在一个线性链表中，这个链表成为同义词链表，即把具有相同哈希地址的关键字值存放在同义链表中；

• 再哈希法：
  -- 再哈希法其实很简单，就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次哈希，直至不发生冲突位置，但这样有一个缺点，每次冲突都要重新哈希，计算时间可能会增加，而且增幅不可控；

• 公共溢出区法
  -- 公共溢出区法，将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表；

1.6 哈希的空间复杂度太高（内存溢出）

• 前面我们简单介绍哈希冲突以及冲突的解决方法，其实都是在为这个结论做铺垫；
• 哈希表的空间效率不够高，这是由哈希函数和哈希冲突处理的方法决定的，一般来说 哈希冲突越低，哈希的效率越高；
• 如何降低哈希冲突呢？在实际工作中，往往需要采用大于实际存储数据数量的哈希表，本质上来说其实就是 以空间换时间；

关于哈希空间复杂度，网上的解释并不是太多，也不够清晰准确，感兴趣的朋友可以参考《数据结构之------什么是哈希表？(哈希表是一个以空间换取时间的数据结构!!! 加快查找速度！！！)》一文，该文对用开放地址法解决哈希冲突做一个相对来说比较详细的解说。

2. 位图

2.1. 什么是位图算法

• 前面介绍了哈希算法，同时也指出了哈希算法存在的空间复杂度太高问题，那么有没有一种数据结构满足 既能处理大量数据，同时又不占用太多空间 的要求呢？
• 这里我们介绍另一种叫 位图 的数据结构，这里的位图并不真的是图，而是按照集合中最大元素 max 创建一个长度为 max+1 的新数组，在数据存入时扫描原始数组，每当遇到一个数值就把新数组该位置写为 1，比如遇到 5 就给新数组的第 6 个元素置 1，这样下次再遇到 5 时发现新数组的第 6 个元素已经是 1 了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组 初始化时置零其后置一的做法，类似于位图的处理方法故称 位图算法；
• 这段定义文字可能看起来很拗口，我们解读一下他的含义，位图算法的作用是可以用一个 数据位 来存放一种状态（比如 1 和 0），如果我们想知道某个数值是否已经存在，我们只需要找到对应的数据位查看该数据为的状态即可；

2.2. 位图算法的实现

• 假设我们有一个数组 {1,3,7}，我们需要设计一种方法来存储它，有什么方法可以佣金可能小的内存空间把它存储下来呢？
• 我们可以使用使用一个 8 位的地址空间，在从 0 到 7 这 8 个位上，我们按顺序将数值对应的位的值置为 1，得到的结果就是 01010001，如下图所示：

Untitled.png

• 在这样一个 8 位的地址空间上，我们存储了 3 个 0 到 8 之间的数字；

• 那么我们如果想存储的数字介于 0 到 15 之间呢，比如 {1, 2, 5, 7, 11}，其实解决问题的方法和上面是一样的，只不过用于存储的空间需要更长，这里我们申请一个 16 位的地址空间，然后根据位置对应的值依次重置数值；

  
  
  1956855-ad09be445fd67539.png
• 位图最典型的应用，是在一段已知长度的地址空间中，用二进制方式（即 1 和 0）存储数据的状态，而一个数只有存在和不存在两个状态，这里的 1 代表存在，0 代表不存在，当我们查询的时候只需要知道目标位置上是 1 还是 0；
• 当有有多个值需要进行复杂的查询的时候，我们只需要对二进制数组进行 位运算，就可以很快找到我们想要的结果，这也是算法被称为 位图 的原因；

关于位图算法，有一篇很经典的文章，是由 程序员小灰 所写的《漫画：什么是Bitmap算法？》，建议读者朋友去读一读，看完以后对于位图算法的实现和应用将有更加清晰的认识。

2.3. 512M 内存查找 43 亿数据

• 关于位图算法，网上的文章中经常会讲到这个例子，这个例子同时 BAT 的经典算法题之一，我们也用这个例子做个讲解；
• 假设我们现在有 43 条数据，需要判断一个数据是否已经出现过，如果已经出现就丢弃，否则就作为新数据添加到 43 亿条数据中，我们该如何实现这个需求呢？
• 构建数组
  -- 首先，我们需要注意 43 亿这个数字，接触过 32 位系统知识的读者可能已经注意到，2 的 32 次方 等于4294967296，约等于这里的 43 亿；
  -- 结合前面的位图算法相关知识，我们在这里申请一个 32 位的数组，初始状态下每个位都置 0，表示该位上为空（没有数值），当我们拿到一个数字，我们就到对应的位上把值置为 1，表示此位上对应的数值已经被添加；
  -- 按照上面的顺序类推，我们就构建了一个容量为 43 亿的数组，在这个数组中最大可以存储 43 亿个数值的状态；
• 查找数据
  -- 当我们拿到一个新的数值的时候，我们只需要到对应的位上查看该位状态值是否为 1，就知道是否已经存在该数值；
• 内存使用情况
  -- 分析下内存空间，我们申请了 32 位的内存，每个位上只有 1 和 0 两种状态，总计 2 的 32 次方个位的空间，就是 2 的 29 次方个字节，就相当于 500MB；
• 这样，我们就解决了 512M 内存查找 43 亿数据的问题，而解决问题的思路其实就是 位图 算法的思想。

2.4. 位图算法的应用

• 位图算法适用于数据量很大但数据状态又不是很多的情况，通常是用来判断某个数据存不存在的；

• 具体应用：
  -- 快速查找某个数据是否在一个集合中；
  -- 排序；
  -- 求两个集合的交集、并集等；
  -- 操作系统中磁盘块标记；

• 在这里我们就不对这些具体应用展开来讲了，感兴趣的朋友可以自行百度谷歌了解相关知识。

2.5. 位图算法处理不了哈希冲突

• 前面讲的位图算法的内容，都是围绕 数值 展开的，但实际业务场景下要处理的对象很少严格意义的数值，最常见的处理对象其实是 字符串，那么我们该怎样将字符串映射
• 有些人应该想到了，就是我们前面讲的哈希，使用一个哈希函数将字符串对象映到一个数组的位置上，比如我们拿到一个 url 以后，代入哈希函数得到一个数值，然后通过位图算法在数
• 位图更节省空间，但因为处理不了哈希冲突，所以仍不能满足业务需求；

3. 布隆过滤器

3.1. 布隆过滤产生的背景

• 为什么会在位图的基础上产生布隆过滤器呢？
  -- 对于数字的话，位图是可以处理的，因为他们是不存在冲突的，每一个数字对于一个唯一的哈希地址；
  -- 但是对于字符串，位图是没有办法处理的，因为字符串存在哈希冲突。
  -- 因此，我们只能通过我们将一个元素经过多个散列函数映射到多个位上来降低误判的概率，布隆过滤器正是基于这个特点应用而生的。
• 布隆过滤器的基本思想是：通过一个 Hash 函数将一个元素映射成一个位图矩阵中的一个点，我们只需查看这个位置是 1 还是 0 就知道集合中是否存在它，到这里读者朋友应该已经明白了布隆过滤和位图算法之间的关系；
• 但是由于哈希冲突的原因，即不同的元素经过散列函数后可能产生相同的哈希地址，我们很可能导致误判，为了降低误判的概率，我们将一个元素经过多个散列函数映射到多个位上，如果这几个位都为1，我们认为它是存在的；如果有一位为0，我们认为它不存在。

3.2. 布隆过滤的工作原理

• 布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出，由一个很长的二进制向量（位向量）和一系列随机映射函数组成，可以用于检索一个元素是否在一个集合中；
• 其工作过程，是将一个元素用多个哈希函数映射到一个位图中,分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零， 代表该元素一定不在哈希表中，否则可能在哈希表中；

哈希表 的缺点是浪费空间；
位图 的缺点是 不能处理哈希冲突；
将 哈希与位图结合，即是此处要讲的布隆过滤器；
布隆过滤器的基本思想，是在位图中添加多个哈希函数，减小需要开辟的存储空间。

• 具体步骤：
  -- 我们使用 K 个哈希函数，对同一个输入元素进行求哈希值，那会得到 K 个不同的哈希值，我们分别记作 Y1​，Y2​，Y3​，…，YK​；
  -- 我们把这 K 个数字作为位图中的下标，将对应的 BitMap[Y1​]，BitMap[Y2​]，BitMap[Y3​]，…，BitMap[YK​]都设置成 true，也就是说，我们用 K 个二进制位，来表示一个数字的存在；
  -- 当我们要查询某个数字是否存在的时候，我们用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Z1​，Z2​，Z3​，…，ZK​；
  -- 我们看这 K 个哈希值，对应位图中的数值是否都为 true，如果都是 true，则说明这个数字存在，如果有其中任意一个不为 true，那就说明这个数字不存在。

  
  
  image.png

• 误判问题：
  -- 在上面的步骤中有个问题，如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；
  -- 如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在；
  -- 不过，只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。

3.3. 布隆过滤器优点

• 优点是空间效率和查询时间都远远超过一般的算法；
  -- 布隆过滤器存储空间和插入/查询时间都是常数，增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关；
  -- 布隆过滤器的特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函 数，将一个数据映射到位图结构中，此种方式不仅可以提升查询效率，也可以节省大量的内存空间；
• 另外, Hash 函数相互之间没有关系，方便由硬件并行实现；
• 布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势；
• 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能；
• 使用同一组散列函数的布隆过滤器可以进行交、并、差运算；

3.4. 布隆过滤器的误判问题

• 所谓误判，就是要查找的元素并不存在，但是以前插入的数据刚好将 key 经过几个映射函数的 bit 位置为 1，这就造成一种假象，要查找的数据存在；
• 当输入的数据量比较小的时候，这种情况发生的概率还是比较低的，但是当输入的数据量很大的时候，这种错误率就明显上升了；
• 误判率的大小与 seeds 的数量、申请的内存大小、去重对象的数量有关，下面的表格展示了几个元素之间的关系：
  -- m 表示内存大小（多少个位），n 表示去重对象的数量，k 表示 seed 的个数；
  -- 假如代码中申请了 512M 内存，即1<<32（m=2^32=4294967296，约43亿），seed 设置了7个。看 k=7 那一列，当漏失率为 8.56e-05 时，m/n 值为 23。所以 n = 43/23 = 1.86(亿），表示漏失概率为 8.56e-05 时，512M 内存可满足 1.86 亿条字符串的去重；

Bloomfilter算法漏误判率

• 解决布隆过滤器误判方法
  -- TODO

3. 布隆过滤器应用场景

• 在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省；
• 对于爬虫工程师来说，布隆过滤器的典型应用是 高并发爬虫去重，正如文章开始时举的例子，如果爬虫的请求数量达到 亿计、十亿计 这个量级，那么布隆去重将是去重策略的首选；
• 除了爬虫之外，布隆过滤器广泛应用于数据库设计，例如：
  -- Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数；
• 在很多 Key-Value 系统中也使用了布隆过滤器来加快查询过程，如 Hbase，Accumulo，Leveldb，一般而言 Value 保存在磁盘中，访问磁盘需要花费大量时间，然而使用布隆过滤器可以快速判断某个 Key 对应的 Value 是否存在，因此可以避免很多不必要的磁盘IO操作，只是引入布隆过滤器会带来一定的内存消耗；

注意：Bloom Filter 不适合那些 “零错误” 的应用场合；

• 缺点
  -- 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中，接下来会细讲；
  -- 不能获取元素本身；
  -- 一般情况下不能从布隆过滤器中删除元素；
  -- 如果采用计数方式删除，可能会存在计数回绕问题；