1.Hash函数
Hash （中译为哈希，或者散列）函数在计算机领域，尤其是数据快速查找领域，加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面（这些小的数据集叫做哈希值，或者散列值）。Hash table（散列表，也叫哈希表），是根据哈希值(Key value)而直接进行访问的数据结构。也就是说，它通过把哈希值映射到表中一个位置来访问记录，以加快查找的速度。
下面是一个典型的hash函数/表示意图：
哈希函数有以下两个特点：
如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的。但也可能不同，这种情况称为“散列碰撞”（或者“散列冲突”）。上图中，John Smith和Sandra Dee就存在hash冲突。
Hash一个应用就是对数据集分类，比如上图，Hash值为0的表示可能在A集合中，Hash值为2的表示B集合中，依次类推，值为15的表示F集合中。但Hash冲突会在这里会导致严重的问题，对于一个未知的新值，其可能不属于上面任何一个集合，但由于冲突，其Hash值和上面的某一个相同，导致误报（因为事先我们不可能做一个含有无限多项输入的完整的Hash表，也就是原来的Hash函数不可能是完美的）。并且，hash冲突也会导致查找效率低下。
2.Bloom Filter
Bloom Filter是1970年由Bloom提出的。它实际上是一个很长的二进制向量和一系列随机映射函数（Hash函数）。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。Bloom Filter广泛的应用于各种需要查询的场合中，如Orocle的数据库，Google的BitTable也用了此技术。
如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。
这时候就可以利用哈希表这个数据结构（它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点）。这样一来，我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是Bloom Filter的基本思想。但这时，哈希冲突会是一个问题：假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m/100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们都在说谎，不过直觉上判断这种事情的概率是比较低的。这种多个Hash组成的数据结构就叫Bloom Filter。
一个Bloom Filter是基于一个m位的位向量（b1,…bm），这些位向量的初始值为0。另外，还有一系列的hash函数（h1,…hk），这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图：
上图中，m=18，k=3；插入x是，三个hash函数分别得到蓝线对应的三个值，并将对应的位向量改为1，插入y，z时，类似的，分别将红线，紫线对应的位向量改为1。查找时，当查找x时，三个hash值对应的位向量都为1，因此判断x在此数据集中。y，z也是如此。但是查找w时，w有个hash值对应的位向量为0，因此可以判断不在此集合中。但是，假如w的最后那个hash值比上图中的大1，这是就会认为w在此集合中，而事实上，w可能不在此集合中，因此可能出现误报。显然的，插入数据越多，1的位数越多，误报的概率越大。
Wiki的Bloom Filter词条有关于误报的概率的详细分析：。从分析可以看出，当k比较大时，误报概率还是比较小的，因此这存储还是很空间有效滴。
Bloom Filter特点：
不存在漏报（False Negative），即某个元素在某个集合中，肯定能报出来。
可能存在误报（False Positive），即某个元素不在某个集合中，可能也被爆出来。
确定某个元素是否在某个集合中的代价和总的元素数目无关。
优点：
相比于其它的数据结构，Bloom Filter在空间和时间方面都有巨大的优势。Bloom Filter存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系，方便由硬件并行实现。Bloom Filter不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
缺点：
另外，一般情况下不能从Bloom Filter中删除元素. 我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在Bloom Filter里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
各种字符串Hash函数比较
常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，
PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。
| Hash函数 | 数据1 | 数据2 | 数据3 | 数据4 | 数据1得分 | 数据2得分 | 数据3得分 | 数据4得分 | 平均 |
| BKDRHash | 2 | 0 | 4774 | 481 | 96.55 | 100 | 90.95 | 82.05 | 92.64 |
| APHash | 2 | 3 | 4754 | 493 | 96.55 | 88.46 | 100 | 51.28 | 86.28 |
| DJBHash | 2 | 2 | 4975 | 474 | 96.55 | 92.31 | 0 | 100 | 83.43 |
| JSHash | 1 | 4 | 4761 | 506 | 100 | 84.62 | 96.83 | 17.95 | 81.94 |
| RSHash | 1 | 0 | 4861 | 505 | 100 | 100 | 51.58 | 20.51 | 75.96 |
| SDBMHash | 3 | 2 | 4849 | 504 | 93.1 | 92.31 | 57.01 | 23.08 | 72.41 |
| PJWHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
| ELFHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。
在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。
CmYkRgB123原创，欢迎建议、交流、批评和指正。
附：各种哈希函数的C语言程序代码0x7FFFFFFF()----基本思想是遍历字符串，根据一定关系(加法、乘法、移位等)得到一个无数号数值。
// 1BKDR Hash
unsigned int BKDRHash(char *str){ unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0;while (*str)
{ hash = hash * seed + (*str++); }return (hash & 0x7FFFFFFF);
}// 2AP Hash
unsigned int APHash(char *str){ unsigned int hash = 0; int i;for (i=0; *str; i++)
{ if ((i & 1) == 0) { hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5))); } }return (hash & 0x7FFFFFFF);
}// 3DJB Hash
unsigned int DJBHash(char *str){ unsigned int hash = 5381;while (*str)
{ hash += (hash << 5) + (*str++); }return (hash & 0x7FFFFFFF);
}// 4JS Hash
unsigned int JSHash(char *str){ unsigned int hash = 1315423911;while (*str)
{ hash ^= ((hash << 5) + (*str++) + (hash >> 2)); }return (hash & 0x7FFFFFFF);
}// 5RS Hash
unsigned int RSHash(char *str){ unsigned int b = 378551; unsigned int a = 63689; unsigned int hash = 0;while (*str)
{ hash = hash * a + (*str++); a *= b; }return (hash & 0x7FFFFFFF);
}// 6SDBMHash
unsigned int SDBMHash(char *str){unsigned int hash = 0;
while (*str)
{ // equivalent to: hash = 65599*hash + (*str++); hash = (*str++) + (hash << 6) + (hash << 16) - hash; }return (hash & 0x7FFFFFFF);
}// 7P. J. Weinberger Hash
unsigned int PJWHash(char *str){ unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8); unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * 3) / 4); unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8); unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth); unsigned int hash = 0; unsigned int test = 0;while (*str)
{ hash = (hash << OneEighth) + (*str++); if ((test = hash & HighBits) != 0) { hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits)); } }return (hash & 0x7FFFFFFF);
}// 8ELF Hash
unsigned int ELFHash(char *str){ unsigned int hash = 0; unsigned int x = 0;while (*str)
{ hash = (hash << 4) + (*str++); if ((x = hash & 0xF0000000L) != 0) { hash ^= (x >> 24); hash &= ~x; } }return (hash & 0x7FFFFFFF);
}转自：
一、算法描述
一个empty bloom filter是一个有m bits的bit array，每一个bit位都初始化为0。并且定义有k个不同的hash function，每个都以uniform random distribution将元素hash到m个不同位置中的一个。在下面的介绍中n为元素数，m为布隆过滤器或哈希表的slot数，k为布隆过滤器重hash function数。为了add一个元素，用k个hash function将它hash得到bloom filter中k个bit位，将这k个bit位置1。
为了query一个元素，即判断它是否在集合中，用k个hash function将它hash得到k个bit位。若这k bits全为1，则此元素在集合中；若其中任一位不为1，则此元素比不在集合中（因为如果在，则在add时已经把对应的k个bits位置为1）。不允许remove元素，因为那样的话会把相应的k个bits位置为0，而其中很有可能有其他元素对应的位。因此remove会引入false negative，这是绝对不被允许的。
当k很大时，设计k个独立的hash function是不现实并且困难的。对于一个输出范围很大的hash function（例如MD5产生的128 bits数），如果不同bit位的相关性很小，则可把此输出分割为k份。或者可将k个不同的初始值（例如0,1,2, … ,k-1）结合元素，feed给一个hash function从而产生k个不同的数。
当add的元素过多时，即n/m过大时（n是元素数，m是bloom filter的bits数），会导致false positive过高，此时就需要重新组建filter，但这种情况相对少见。
二. 时间和空间上的优势
当可以承受一些误报时，布隆过滤器比其它表示集合的数据结构有着很大的空间优势。例如self-balance BST, tries, hash table或者array, chain，它们中大多数至少都要存储元素本身，对于小整数需要少量的bits，对于字符串则需要任意多的bits（tries是个例外，因为对于有相同prefixes的元素可以共享存储空间）；而chain结构还需要为存储指针付出额外的代价。对于一个有1%误报率和一个最优k值的布隆过滤器来说，无论元素的类型及大小，每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性，一部分来源于它的概率性。如果你认为1%的误报率太高，那么对每个元素每增加4.8 bits，我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k)，与集合中元素的多少无关，这是其他数据结构都不能完成的。
如果可能元素范围不是很大，并且大多数都在集合中，则使用确定性的bit array远远胜过使用布隆过滤器。因为bit array对于每个可能的元素空间上只需要1 bit，add和query的时间复杂度只有O(1)。注意到这样一个哈希表（bit array）只有在忽略collision并且只存储元素是否在其中的二进制信息时，才会获得空间和时间上的优势，而在此情况下，它就有效地称为了k=1的布隆过滤器。
而当考虑到collision时，对于有m个slot的bit array或者其他哈希表（即k=1的布隆过滤器），如果想要保证1%的误判率，则这个bit array只能存储m/100个元素，因而有大量的空间被浪费，同时也会使得空间复杂度急剧上升，这显然不是space efficient的。解决的方法很简单，使用k>1的布隆过滤器，即k个hash function将每个元素改为对应于k个bits，因为误判度会降低很多，并且如果参数k和m选取得好，一半的m可被置为为1，这充分说明了布隆过滤器的space efficient性。
三. 举例说明
以垃圾邮件过滤中黑白名单为例：现有1亿个email的黑名单，每个都拥有8 bytes的指纹信息，对于bit array来说是根本不可能的范围，而且元素的数量（即email列表）为 10^9，相比于元素范围过于稀疏，而且还没有考虑到哈希表中的collision问题。
若采用哈希表，由于大多数采用open addressing来解决collision，而此时的search时间复杂度为 ：
即若哈希表半满(n/m = 1/2)，则每次search需要probe 2次，因此在保证效率的情况下哈希表的存储效率最好不超过50%。此时每个元素占8 bytes，总空间为：
若采用Perfect hashing（这里可以采用Perfect hashing是因为主要操作是search/query，而并不是add和remove），虽然保证worst-case也只有一次probe，但是空间利用率更低，一般情况下为50%，worst-case时有不到一半的概率为25%。
若采用布隆过滤器，取k=8。因为n为1亿，所以总共需要 被置位为1，又因为在保证误判率低且k和m选取合适时，空间利用率为50%（后面会解释），所以总空间为：
所需空间比上述哈希结构小得多，并且误判率在万分之一以下。
四. 误判概率的证明和计算
假设布隆过滤器中的hash function满足simple uniform hashing假设：每个元素都等概率地hash到m个slot中的任何一个，与其它元素被hash到哪个slot无关。若m为bit数，则对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为：
则k个hash function中没有一个对其置位的概率为：
如果插入了n个元素，但都未将其置位的概率为：
则此位被置位的概率为：
现在考虑query阶段，若对应某个待query元素的k bits全部置位为1，则可判定其在集合中。因此将某元素误判的概率为：
由于 ，并且 当m很大时趋近于0，所以
从上式中可以看出，当m增大或n减小时，都会使得误判率减小，这也符合直觉。
现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：
设 ， 则简化为
，两边取对数
, 两边对k求导
下面求最值
因此，即当 时误判率最低，此时误判率为：
可以看出若要使得误判率≤1/2，则：
这说明了若想保持某固定误判率不变，布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。
五. 设计和应用布隆过滤器的方法
应用时首先要先由用户决定要add的元素数n和希望的误差率P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数，之后的所有参数将由系统计算，并由此建立布隆过滤器。
系统首先要计算需要的内存大小m bits:
再由m，n得到hash function的个数：
至此系统所需的参数已经备齐，接下来add n个元素至布隆过滤器中，再进行query。
根据公式，当k最优时：
因此可验证当P=1%时，存储每个元素需要9.6 bits：
而每当想将误判率降低为原来的1/10，则存储每个元素需要增加4.8 bits：
这里需要特别注意的是，9.6 bits/element不仅包含了被置为1的k位，还把包含了没有被置为1的一些位数。此时的
才是每个元素对应的为1的bit位数。
从而使得P(error)最小时，我们注意到：
中的 ，即
此概率为某bit位在插入n个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使用率需为50%。