type
status
date
slug
summary
tags
category
icon
password
Property
标准库定义了
bitset 类，使得位运算的使用更为容易， 并且能够处理超过最长整型类型大小的位集合。bitset类定义在头文件bitset 中给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？
要判断一个数是否在某一堆数中，可能会想到如下方法：
- 将这一堆数进行排序，然后通过二分查找的方法判断该数是否在这一堆数中
- 将这一堆数插入到
unordered_set容器中，然后调用find函数判断该数是否在这一堆数中
但问题是这里有40亿个数，若是要将这些数全部加载到内存当中，那么将会占用16G的空间，空间消耗是很大的。因此从空间消耗来看，上面这两种方法实际都是不可行的。
实际在这个问题当中，只需要判断一个数在或是不在，即只有两种状态，那么可以用一个比特位来表示数据是否存在，如果比特位为1则表示存在，比特位为0则表示不存在。
无符号整数总共有 个，因此记录这些数字就需要个比特位，也就是512M的内存空间，内存消耗大大减少。
常见位图的应用如下：
- 快速查找某个数据是否在一个集合中
- 排序
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
- 内核中信号标志位（信号屏蔽字和未决信号集）
定义和初始化bitset
bitset类是一个类模板， 它类似array类，具有固定的大小 。当定义一个bitset时， 需要声明它包含多少个二进制位。初始化
bitset：
用一个整型值初始化
bitset时，此值被转换为unsigned long long，并被当做位模式处理。bitset中的二进制位是此模式的一个副本：从字符串初始化
bitset，字符直接表示位模式：
bitset操作：
此外，
bitset还支持所有位运算符，作用与用在unsigned上含义相同。置位意思是将该位值置为true。如将最高位
size()-1置位，那么to_string后返回1+n个0。而复位的含义为将该位置为0。C++ 11中bitset引进了成员函数all，所有位都是true时返回true。bitset的count和size方法返回size_t类型值。bitset的下标运算符是被const重载的，非const版本返回的是bitset定义的一个特殊类型的值，可以通过此值操纵指定位的值，而const版本根据是否置位返回true或false：bitset的to_ulong和to_ullong方法返回的值与bitset对象有相同的位模式，只有bitset的大小小于等于对应类型大小时才能使用这两个操作，如bitset中值不能放入指定类型，会抛出overflow_error异常。bitset的IO运算符从输入流读取字符，保存到一个临时string对象中，字符数达到bitset的最大大小或遇到不是01的字符时或遇到文件尾或输入错误时，读取结束，之后，用这个string对象初始化bitset。使用
bitset实现评分程序：布隆过滤器
使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？
- 用哈希表存储用户记录，缺点：浪费空间
- 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。但可以使用一些哈希算法把字符串类型转换成整型，比如BKDR哈希算法，但是这里还存在一个问题。字符串的组合方式太多了，一个字符的取值有256种，一个数字只有10种，所以不可避免会出现哈希冲突
上述法二将哈希与位图结合的方法，即布隆过滤器
布隆过滤器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出，它是一种 space efficient 的概率型数据结构，用于判断一个元素是否在集合中。当布隆过滤器说，某个数据存在时，这个数据可能不存在;当布隆过滤器说，某个数据不存在时，那么这个数据一定不存在。
哈希表也能用于判断元素是否在集合中，但是布隆过滤器只需要哈希表的 1/8 或 1/4 的空间复杂度就能完成同样的问题。布隆过滤器可以插入元素，但不可以删除已有元素。其中的元素越多，false positive rate(误报率)越大，但是 false negative (漏报)是不可能的。
布隆过滤器原理
BloomFilter 的算法是，首先分配一块内存空间做 bit 数组，数组的 bit 位初始值全部设为 0。
加入元素时，采用 k 个相互独立的 Hash 函数计算，然后将元素 Hash 映射的 K 个位置全部设置为 1。
检测 key 是否存在，仍然用这 k 个 Hash 函数计算出 k 个位置，如果位置全部为 1，则表明 key 存在，否则不存在。
如下图所示：
哈希函数会出现碰撞，所以布隆过滤器会存在误判。
这里的误判率是指，BloomFilter 判断某个 key 存在，但它实际不存在的概率，因为它存的是 key 的 Hash 值，而非 key 的值。
所以有概率存在这样的 key，它们内容不同，但多次 Hash 后的 Hash 值都相同。
对于 BloomFilter 判断不存在的 key ，则是 100% 不存在的，反证法，如果这个 key 存在，那它每次 Hash 后对应的 Hash 值位置肯定是 1，而不会是 0。布隆过滤器判断存在不一定真的存在。
为什么不允许删除元素呢?
删除意味着需要将对应的k个bits位置设置为0，其中有可能是其他元素对应的位。因此remove会引入false negative，这是绝对不被允许的。