位图
位图概述
位图(bit set)中存储位(bit)，每个元素只有两个可能值，1/0 或者 true/false。与bool数组相比，位图的空间开销更小，每个元素占据 1bit 空间，是C++最小内置类型char的八分之一。
位图是哈希思想衍生出的容器，在完成哈希表判断元素存在功能的同时，极大地节省了所需的内存空间。位图的每个位都可以被单独访问，例如给定一个位图bitSet, 则 bitSet[3] 访问的是该位图的第4个位。
位图实现
位图以vector作为底层存储容器，因为在几乎所有的C++容器中不存在空间是 1bit 的数据类型，所以vector在宏观上存储的其实是 int 类型或者 char 类型，在进行操作时，位图内部会通过计算找到对应的 bit 位置，并对其进行操作。位图的大小(容量)是确定的，通过用户由非类型模板参数指定。
template<size_t N>
class bit_map
{
private:
typedef bit_map<N> self;
public:
bit_map()
{
//通过所需bit位数计算实际需要的内存空间，向上取整
_bitMap.resize(N / 32 + 1);
}
self& set(size_t n)
{
int i = n / 32; //目标位处于第i个整型的第j个bit位
int j = n % 32;
_bitMap[i] |= (1 << j); //将目标位 置1
return *this;
}
self& reset(size_t n)
{
int i = n / 32;
int j = n % 32;
_bitMap[i] &= (~(1 << j)); //将目标位 置0
return *this;
}
self& flip(size_t n) //翻转目标位
{
if (test(n)) {
reset(n);
}
else {
set(n);
}
return *this;
}
bool test(size_t n) //检查目标位的状态
{
int i = n / 32;
int j = n % 32;
return (_bitMap[i] & (1 << j));
}
private:
vector<int> _bitMap; //此处以vector<int>作为底层存储容器
};虽然在大端机器和小端机器中，数据的存储方式有所差异，但是在位图的实现中不必考虑这些细节，机器会在底层操作时自行处理。
位图应用
位图用于处理海量数据相关的问题，极简的内存开销是选择它的理由。当以所有32位整型作为位图有效数据的范围(0~4294967295)时，位图所需要的内存空间为 500MB 左右。
位图主要解决下面的问题：
- 海量数据中，判断整型数据是否存在。用一个位图对所有数据进行映射即可。在linux2.6内核的进程调度中，位图用于找到不为空的优先级队列。
- 海量数据中，找出指定出现次数(1次、2次、多次)的整型数据。用两个位图，以两个位图中相同位置的状态 00, 01, 10, 11 可以标识数据出现的次数。
- 海量数据的交集问题。将两个数据集合分别映射到两个位图，对应位进行与运算即可。
位图的局限性
除了不能获取元素本身，位图还有另一大局限性。位图只适用于解决与整型相关的问题，这是因为整型可以轻松地映射到位图中的某个位置，并且不同的值不会造成映射冲突。当目标数据是其他类型，例如字符串、浮点型时，会造成存在误判(假阳性)。例如，当字符串 str1 通过哈希函数计算出的索引为 n 且在位图中存在，且 str2 通过哈希函数映射出的索引也为 n 且在位图中不存在时，就会对 str2 的存在造成误判。这种误判不可避免，但是可以通过布隆过滤器尽量减少误判的概率。
布隆过滤器
布隆过滤器概述
布隆过滤器(bloom filter)可以尽量减少字符串映射到位图后的假阳率。布隆过滤器的做法是，将同一个字符串，通过多个不同的哈希函数映射到多个位置，当进行test时，检查对应的多个位置，如果某一个位置为0，则说明字符串一定不存在；如果都为1，则存在较低的假阳概率。通过控制bit vector的大小和哈希函数的个数，可以将假阳率控制在 1% 以下。
在 jason davies 主页一篇关于 bloom filter 的文章中，可以支持读者与一个可视化的布隆过滤器进行互动：Bloom Filters (jasondavies.com)。
传统的布隆过滤器不支持删除，这是因为某些位可能与字符串存在一对多的关系，一旦进行位的修改，会对其他数据造成影响。布隆过滤器不能获取元素本身。
布隆过滤器实现
传统的布隆过滤器支持两个主要接口: set 和 test。这里使用三个哈希函数进行映射，进行 set 和 test 时，分别对 hashing 出的三个位置进行操作或检查。
///////////////////////////////////////////////////////
//选择三个哈希函数
struct BKDRHash
{
size_t operator()(const string& str)
{
size_t hash = 0;
for(auto& ch : str)
{
hash = hash * 131 + ch;
}
return hash;
}
};
struct APHash
{
size_t operator()(const string& str)
{
size_t hash = 0;
for(size_t i = 0; i < str.size(); ++i)
{
char ch = str[i];
if(ch & 1)
{
hash ^= (~((hash << 11) ^ (str[i++]) ^ (hash >> 5)));
}
else
{
hash ^= ((hash << 7) ^ (str[i++]) ^ (hash >> 3));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& str)
{
size_t hash = 0;
for(size_t i = 0; i < str.size(); ++i)
{
hash += (hash << 5) + (str[i++]);
}
return (hash & 0x7FFFFFFF);
}
};
//////////////////////////////////////////////////////////
template<size_t N, class hash1 = BKDRHash,
class hash2 = APHash, class hash3 = DJBHash>
class bloom_filter
{
private:
typedef bloom_filter<N> Self;
public:
Self& set(const string& str)
{
//对三个位置分别set
_bitSet.set((hash1()(str)) % N);
_bitSet.set((hash2()(str)) % N);
_bitSet.set((hash3()(str)) % N);
}
bool test(const string& str)
{
//同时检查三个位置
//三个位置同时为1时，数据可能存在
//三个位置中某一个位置为0，数据一定不存在
return _bitSet.test(hash1()(str) % N) &&
_bitSet.test(hash2()(str) % N) &&
_bitSet.test(hash3()(str) % N);
}
private:
bitset<N> _bitSet;
};布隆过滤器应用
布隆过滤器适用于一些不需要精确判断的场景。在实际使用中，布隆过滤器往往处在用户与数据库(或其他存储设备)之间，布隆过滤器可以对数据的存在性进行初步判断，如果判定为不存在，则直接返回结果给用户；如果判定为存在，则存在假阳率，进一步去存储设备中确认。
在这种场景中，布隆过滤器真正发挥了它 “过滤” 的功能，大大降低了数据库的负载，提高了判断效率。
误判率与相关因素的大致分析
bit vector的大小是影响布隆过滤器误判率的关键因素。如果bit vector太小，则过滤器会很快被填满，对于每一个输入，都会返回假阳性的结果。所以bit vector的大小是必须要考虑的，较大的bit vector会产生较少的误判，较小的bit vector会产生较多的误判。此外，哈希函数的选择与数量也是一个重要因素，选择的哈希函数越多，过滤器性能相对越低，过滤器越容易被填满；但是如果哈希函数较少，可能会造成更多的误判。
下面的图片描述了bit vector的大小(m)、哈希函数(k)的数量与误判率(p)的关系：
(图片出自 Probabilistic Data structures: Bloom filter by @me_shaon )
可见，当bit vector的大小为100M，哈希函数的数量在3个及以上时，假阳率会大幅下降至 1% 以下。根据实际场景，调整误判率至所需要的程度是个较好的选择。
标签：哈希,布隆,C++,str,过滤器,bit,位图 From： https://blog.51cto.com/158SHI/7661836