历史书太小，装不下一个人的波澜壮阔的一生。
历史书又太大，装下了中华上下五千年时光。

简介

检查一个元素是否存在于另一个集合/容器中，可以说是非常普遍的需求了。

具体实现的方法也是多种多样，像数组、哈希表、布隆过滤器等，都可以满足需求，且都有着各自的亮点、优点、缺点。

而不同的算法、数据结构，都是基于一定需求背景下产生的，我们来学习下他们各自适用于什么场景吧。

数组查找

如何判断一个元素是否在一个集合中，我们最常见的方法其实就是遍历容器对象逐一匹配，可以找到某个元素则称之为命中，不存在于该容器对象中，我们则称之为未命中。

可以看出，遍历查询复杂度为O(n)，想象当一个容器对象足够大，特别是涉及到磁盘IO时，查询性能将非常低下。
以python为例，像我们常见的list、tuple等都是这种数据结构。

但是当数组元素较少时，其实基本不会存在查询问题，因为我们可以基于内存进行查询和比对工作，这也算是一种空间换时间的说法吧。因为当元素超过机器物理内存时，我们将不得不把元素存放到磁盘中。而频繁的遍历磁盘中的元素，往往时性能问题的起因。

哈希表查找

那么有没有一种数据结构，当数据量增加时，查询性能仍然很好呢？
答案就是哈希！我们常见的数据结构，比如哈希表就充分的利用了这一特点。

将哈希表前，需要先说明一个概念，就是稀疏数组。即一个数组中，允许存在大多数空值，我们称之为稀疏数组。而哈希表底层就是一个稀疏数组，此时，数组中的每一个位置，我们称之为哈希桶。也就是说哈希表存放元素，是随机存放到哈希桶中的，而且可能很多哈希桶都是空的，也可能多个元素放到一个哈希桶中。

那么哈希表是如何存放一个元素的呢？
首先，基于存储键，计算哈希值，然后将哈希值与数组长度取余，此时计算结果将命中一个哈希桶，该哈希桶就是此键值得存储位置。
当不同得键计算哈希并取余计算后，命中同一个哈希桶时，我们称这种为哈希冲突。常常得解决方法就是在该哈希桶中拉一条链表，用于存储元素。

所以，我们也可以大致退出如何取查找一个元素了
首先，基于查找键，计算哈希值，然后将哈希值与数组长度取余，此时计算结果将命中一个哈希桶，该哈希桶就是此键值得存储位置。
若存储位置是个链表，则我们还需要遍历该列表完成查找。最终能查询到则命中，否则未命中。

所以我们可以看出，在哈希表这种结构中，无论存储多少值，经过哈希取余这一计算，就可以快速命中某个哈希桶，进而快速的查找命中关系。
但是，也因为其底层是一个稀疏数组，所以在该数据结构中，可能会造成大量的空间浪费。

哈希表充分的利用了空间换时间的思想，当存储元素足够多时，其占用空间资源也是一笔不可忽视的资源。

布隆过滤器查找

布隆过滤器可以用于快速检索一个元素是否在一个集合中，和哈希表不同，它不用存储该元素具体的值，主要由一个较长的二进制向量和一系列哈希函数组成。

由于布隆过滤器不存储实际的值，则是标记该值对应的位图，所以在大量元素的场景下，布隆过滤器在查询速度和空间使用上，都优于哈希表，唯二的缺点就是查询时存在一定的误报、删除困难。

如何存储一个值？
基于存储键，通过多个哈希算法，计算多个哈希值，然后与二进制向量与运算，得到哈希桶的位置，此时仅仅将对应哈希桶位置置为1，就算完成了一次存储。

如何查找一个值？
基于存储键，通过多个哈希算法，计算多个哈希值，然后与二进制向量与运算，得到哈希桶的位置，查看对应的哈希桶位置是否为1，均为1，则表示命中，至少一个不为1，则表示未命中。

我们明显可以看出，当发生哈希碰撞时，不同的键就会命中同一个哈希桶，那么查找值就会存在误报。这其实是一种不太可取的方法，所以需要根据具体的业务来适配误报率。当二进制向量越长，其误报率也就越低。

但反过来想，当查找一个值，未命中时，我们可以放心的说，该元素一定不存在于这个集合中。

所以，布隆过滤器的特点就是，未命中是100%精确的，而命中则存在误报，对于很多场景来说都是十分有价值的一种算法。

简单实现：https://gitee.com/czasg/blmfilter

总结

布隆过滤器是一种基于哈希快速查找的数据结构，他有别于传统的容器/集合对象，也就是说他是一个集合，但却不存储实际的目标值，而是记录目标值对应哈希槽，通过哈希计算匹配的方式，计算目标值是否存在该集合中，所以在空间和时间上都有很强的使用效率，但也是基于这种特点，在命中的结果集中，不可避免的存在一定的误差。