|
布隆过滤器（Bloom Filter）是用于判断一个元素是否属于一个数据集的数据结构。其基本思想就是用一个或多个hash函数对数据集中的每个成员做映射，映射结果不是存在完整的hash表中，而是一个位向量（bit vector）中。位向量所有位初始都为0，根据hash结果将位向量中相应位置1。对数据集中的所有成员的hash计算完成后，就得到了该数据集的位向量。当需要判断一个元素是否属于该数据集时，也用相同的hash函数对其映射得到它的位向量，然后将其位向量上所有为1的位与数据集位向量上相应位比较，如果发现数据集的位向量上某个位为0的话，可以判断这个元素不属于该数据集，这样的一个结果是肯定的。而如果所有相应位都为1的话，那么该元素可能属于这个数据集。
|
最新文章