有趣的bloom过滤器
设想以下的一个问题：有一个keyword的集合，我们需要快速判定某个keyword是否包含在其中。最简单的方法是遍历，但是效率很差。我们马上想到了hash的方法，因为在Oracle内部，hash无处不在。比如在cache buffer中找到某个block，在shared pool中找到某个SQL等等。我们可以把keyword的集合build成一个hash table，然后根据keyword计算hash值，通过是否落在相应的hash bucket中，这样就可以实现快速查找的目的。这个方法不错，但是当keyword过多时，hash table会占用大量内存，效率也会随之下降。
今天公司的架构师介绍了一个新的方法给我：Bloom Filter。它是一种基于随机数(或Hash)的数据结构，它支持对成员使用较少空间来存储，却能得到较高效率的查询。换句话说：在Bloom Filter 可以用于检索一个元素是否在一个集合中。其原理如下：
建立一个容量为500万的Bit Array结构（Bit Array的大小和keyword的数量决定了误判的几率），将集合中的每个keyword通过32个hash函数分别计算出32个数字，然后对这32个数字分别用500万取模，然后将Bit Array中对应的位置为1，我们将其称为特征值。简单的说就是将每个keyword对应到Bit Array中的32个位置上，见下图：
当需要快速查找某个keyword时，只要将其通过同样的32个hash函数运算，然后映射到Bit Array中的对应位，如果Bit Array中的对应位全部是1，那么说明该keyword匹配成功。
Bloom filter 是一个集合的有损编码，所以它不是一种“保险”的方案，存在一定的误判率。
有人问：这个对DBA有什么用？虽然我们不直接开发应用，但是开阔视野和思路对我们同样重要。难道我们碰到这种问题就只能用like或者in去解决吗？
–EOF–
后记：要深入了解Oracle，hash的原理和实现是必须要掌握的。有一次面试一个技术专家，高精尖的技术谈得头头是道，但是连hash的基本原理都说不清楚。对于一个技术专家来说，不能只懂“高精尖”，没有基础的知识，任何“高精尖”都只是空中楼阁，对于DBA，尤其如此。
