散列表之布隆过滤器

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

布隆过滤器（适用于大数据量中某个元素存在与否的问题）：
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
基本思想：
它可以通过一个Hash函数将一个元素映射成类似数组结构中的一个位阵列（Bit array）中的一个点。如果存在就把这个位阵列中的值置为1.这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

劣势：误判
分析：查询效率高是因为采用hash 等映射的方式基本判断元素存在集合中。误判是因为，不同的值通过一个相同的映射函数可能映射到相同的值。判断元素存在集合中出现误判。

优势：
数据结构选用一个位二进制（1B），可以非常节省空间。以为他的值只存在一个位中所以可以存的值非常多，可以进行大数据量的判断数据存在与否。相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能。

减少误判的方法：
就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，通过另一个hash 函数映射看是否存在这个值。从而减少误判的几率。

下面是多个hash 映射 同一个值的图例