位图
所谓位图，就是用一个bit位来标识数据的状态，通常是用于判断某个数据存不存在。
如果有40亿个不重复的无符号整数，没排过序。再给你一个无符号整数，如何快速判断这个数是否存在于这40亿个数中呢？
位图一般就能很好地处理这种海量数据，且无重复的情景。
// 位图的简单实现
// N 表示有N个数据要标识
template<size_t N>
class bit_set
{
public:
// 构造
bit_set()
{
_bits.resize(N / (8 * sizeof(char)) + 1, 0);
}
// 插入
void set(size_t x)
{
size_t i = x / (8 * sizeof(char));
size_t j = x % (8 * sizeof(char));
_bits[i] |= (1 << j);
}
// 删除
void reset(size_t x)
{
size_t i = x / (8 * sizeof(char));
size_t j = x % (8 * sizeof(char));
_bits[i] &= ~(1 << j);
}
// 查找
bool test(size_t x)
{
size_t i = x / (8 * sizeof(char));
size_t j = x % (8 * sizeof(char));
return _bits[i] & (1 << j);
}
private:
vector<char> _bits;
};
还有一些问题如下：
给定100亿个整数，如何找到只出现一次的整数？
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
这些问题可以考虑使用两个位图来解决。
template<size_t N>
class double_bit_set
{
public:
// 插入
void set(size_t x)
{
bool test1 = _bs1.test(x);
bool test2 = _bs2.test(x);
if (false == test1 && false == test2)
{
_bs2.set(x);
}
else if (false == test1 && true == test2)
{
_bs1.set(x);
_bs2.reset(x);
}
}
private:
bit_set<N> _bs1;
bit_set<N> _bs2;
};
位图除了可以快速查找某个数据是否在一个集合中，还可以用于排序+去重；求两个集合的交集、并集等。
虽然位图的效率高，节省空间；但作用相对局限，只能用于映射处理整形。
布隆过滤器
布隆过滤器是一种紧凑型的，比较巧妙的概率型数据结构。
特点是高效的插入和查找。可以用于确定某个数据的不存在状态，但只能提供其可能存在的状态。
布隆过滤器是一种哈希与位图的结合。它使用多个哈希函数，将一个数据映射到位图结构中。
对于哈希函数个数和布隆过滤器长度之间的关系有如下公式供参考：
k = m n l n 2 k = \frac{m}{n}ln2 k=nmln2
k表示哈希函数个数，m表示布隆过滤器长度，n表示插入的数据个数。
满足上面公式的选择，可以尽量降低布隆过滤器的误判率。
#include <bitset>
class HashBKDR
{
public:
size_t operator()(const string& key)
{
size_t hash = 0;
for (char c : key)
{
hash *= 131;
hash += c;
}
return hash;
}
};
class HashAP
{
public:
size_t operator()(const string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); ++i)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
}
}
return hash;
}
};
class HashDJB
{
public:
size_t operator()(const string& key)
{
size_t hash = 5381;
for (char c : key)
{
hash += (hash << 5) + c;
}
return hash;
}
};
// 这里给出三种字符串哈希算法
template<size_t N,
class K = string,
class Hash1 = HashBKDR,
class Hash2 = HashAP,
class Hash3 = HashDJB>
class BloomFilter
{
public:
// 插入
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio * N);
_bits->set(hash1);
size_t hash2 = Hash2()(key) % (_ratio * N);
_bits->set(hash2);
size_t hash3 = Hash3()(key) % (_ratio * N);
_bits->set(hash3);
}
// 查找
// 布隆过滤器的查找，如果有一个bit映射为0，可以确定这个数据不存在；如果bit映射的都为1，表示这个数据可能存在，即也可能不存在
bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio * N);
if (!_bits->test(hash1))
return false;
size_t hash2 = Hash2()(key) % (_ratio * N);
if (!_bits->test(hash2))
return false;
size_t hash3 = Hash3()(key) % (_ratio * N);
if (!_bits->test(hash3))
return false;
return true; // 可能存在误判
}
private:
const static size_t _ratio = 5; // 由公式大致确定布隆过滤器的长度和插入数据个数的关系
bitset<_ratio*N>* _bits = new bitset<_ratio*N>;
};
传统的布隆过滤器是不支持删除操作的。因为删除一个数据时，其所有bit映射都被置为0，可能会影响其它数据，使其它并未被删除的数据，也连带被删除了。
布隆过滤器的优势与缺陷
- 布隆过滤器的优势：
布隆过滤器增加和查找数据的时间复杂度都为O(K)，K为哈希函数的个数。
布隆过滤器不需要存储具体数据，在某些对保密性要求比较高的场合会有优势。
如果能够承受一定结果的误判，布隆过滤器相比其它数据结构会有更大的空间优势。 - 布隆过滤器的缺陷：
布隆过滤器的缺陷主要在于其存在误判且不可避免。同时一般情况下是不支持删除数据的。