一、位图
1、位图的概念
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
- 遍历，时间复杂度O(N)。
- 排序（O(NlogN)），利用二分查找（logN）
- 位图解决
数据是否在给定的整型数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息。如果二进制比特位为1代表存在，为0代表不存在。比如：
所谓位图，就是用一个比特位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据是否存在。
2、位图的实现
（1）基本结构
template
class BitSet
{
public:
BitSet()//构造函数
{
_bits.resize(N / 32 + 1);//开空间
}
private:
vector _bits;//底层用vector实现
};（2）set函数
将某个比特位的状态设置为1
void set(size_t pos)
{
int i = pos / 32;//获取在数组的哪一个位置
int j = pos % 32;//在第几个比特位
_bits[i] = | (1 （3）reset函数
将某个比特位的状态设置为0
void reset(size_t pos)
{
int i = pos / 32;//获取在数组的哪一个位置
int j = pos % 32;//在第几个比特位
_bits[i] = ~(1 （4）test函数
判断某个比特位的状态
bool test(size_t pos)服务器托管网
{
int i = pos / 32;//获取在数组的哪一个位置
int j = pos % 32;//在第几个比特位
return _bits[i] & (1 二、布隆过滤器
1、布隆过滤器的概念
用位图储存数据有一个缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
将哈希和位图结合就是布隆过滤器。
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效的插入和查询，可以告诉你“某一样东西一定不存在或者可能存在”，他是用多个哈希函数，将一个数据映射到位图中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
所以我们可以得出一个结论：布隆过滤器判断数据不存在是一定准确的，判断数据存在则可能有误判。
这种误判是无法避免的，只能减少误判的概率，如下改变能减小误判率：
2、布隆过滤器的实现
（1）3个哈希函数
这三个哈希函数都是网上找的大佬写的哈希函数
struct BKDRHash
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
return hash;
}
};
struct APHash
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (size_t i = 0; i > 3));
}
else
{
hash ^= (~((hash > 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& key)
{
size_t hash = 5381;
for(auto ch : key)
{
hash += (hash （2）布隆过滤器的基本结构
template
class BloomFilter//布隆过滤器
{
private:
bitset _bits;//底层用STL里的bitset
};（3）set函数
void set(const K& key)
{
size_t hash1 = HashFunc1()(key) % N;
size_t hash2 = HashFunc2()(key) % N;
size_t hash3 = HashFunc3()(key) % N;
_bitset.set(hash1);
_bitset.set(hash3);
_bitset.set(hash2);
}（4）test函数
bool test(const K& key)
{
size_t hash1 = HashFunc1()(key) % N;
size_t hash2 = HashFunc2()(key) % N;
size_t hash3 = HashFunc3()(key) % N;
return _bitset.test(hash1)
&& _bitset.test(hash3)
&& _bitset.test(hash2);
}（5）reset函数
布隆过滤器一般不支持reset，因为reset一个数据时，可能影响其他的数据。
3、布隆过滤服务器托管网器的优缺点
优点：
- 增加和查询元素的时间复杂度为O(K)（K为哈希函数的个数，一般比较小），与数据量大小无关。
- 哈希函数相互之间没有关系，方便硬件进行运算。
- 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
- 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势 。
- 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能 。
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 。
缺点：
- 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
- 如果采用计数方式删除，可能会存在计数回绕问题
完结。。。。。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: 插上u盘显示格式化怎么办？U盘数据恢复可以这样做
U盘以其体积小巧、存储容量大、读写速度快的特点，在各种工作和个人使用场合中得到了广泛应用，因此深得用户好评。然而，在日常使用U盘的过程中，经常会遇到一些问题和挑战。当我需要转移一些资料文件时，总是喜欢使用U盘，相信有很多朋友也是这样。但是在使用U盘的过程中，也…
