目录
一、面试
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
1、遍历，时间复杂度O(N)
2、排序 NlogN 再利用二分搜索
3、利用位图的思想
由于该题没有明确这四十亿个数的数据大小范围，但是明确了元素类型是无符号整形size_t 32个比特位，就可以使用 2 ^ 32次方个比特位来存储元素是否存在，若存在，该比特位置一，不存在就置0。当判断给定数是否存在可以直接进行查看获取是否元素存在位图中。
若该题目确定了元素大小范围，比如给出20个数，大小都小于50，那么只需要建立一个50个元素大小的位图。
二、bitset容器的简单使用
#include <bitset>
#include <vector>
using namespace std;
int main()
{
bitset<50> bt;
vector<int> nums = { 1,2,4,32,8,9,43,35,34 };
for (auto e : nums)
bt.set(e); // 将对应元素位置置一
cout << bt.count() << endl; // 打印9 将bitset库中当前元素个数打印出来
cout << bt.size() << endl; // 打印50 将bitset库的容量打印出来
if (bt.test(32))
cout << "32 is in bitset" << endl;
else
cout << "32 is not in bitset" << endl;
bt.reset(32);
if (bt.test(32))
cout << "32 is in bitset" << endl;
else
cout << "32 is not in bitset" << endl;
return 0;
}三、位图的模拟实现
set 给第4位置1：将1左移4位，进行取或运算。
unset 给第4位置0，将1左移4位并取反，进行与运算
#pragma once
#include <vector>
#include <assert.h>
namespace bite
{
template<size_t N>
class bitset
{
public:
bitset()
: _bst(N / 8 + 1)
, _size(0)
{
}
// pos比特位置1
bitset<N>& set(size_t pos)
{
assert(pos < N);
if (test(pos))
return *this;
size_t whichByte = pos / 8;
size_t whichBit = pos % 8;
_bst[whichByte] |= (1 << whichBit);
++_size;
return *this;
}
// pos比特位置0
bitset<N>& reset(size_t pos)
{
assert(pos < N);
if (!test(pos))
return *this;
size_t whichByte = pos / 8;
size_t whichBit = pos % 8;
_bst[whichByte] &= ~(1 << whichBit);
--_size;
return *this;
}
bool test(size_t pos)
{
assert(pos < N);
size_t whichByte = pos / 8;
size_t whichBit = pos % 8;
return 0 != (_bst[whichByte] & (1 << whichBit));
}
size_t count()const
{
return _size;
}
size_t size()const
{
return N;
}
private:
std::vector<unsigned char> _bst;
size_t _size; // 表示为1的比特位的个数
};
}
四、利用俩个比特位来存储一个数据信息。
五、布隆过滤器
布隆过滤器是 由布隆（ Burton Howard Bloom ）在 1970 年提出的 一种紧凑型的、比较巧妙的 概
率型数据结构 ，特点是 高效地插入和查询，可以用来告诉你 “ 某样东西一定不存在或者可能存
在 ” ，它是 用多个哈希函数，将一个数据映射到位图结构中 。此种方式 不仅可以提升查询效率，也
可以节省大量的内存空间 。
如上，“baidu”和“tencent”分别通过对应的三种哈希函数映射到2/3/6 和 1/2/5的位置，但是“world”经过映射分别得到了1/2/3的位置，再查询“world”是否存在时，发现它对应的位图都为1，则判定“world”存在，但是这与实际不符，所以布隆过滤器如果说，该数据存在，则是可能存在
但判断“hello"是否存在时，发现HF2映射出来结果为4，但4号位置为0，则表示该数据“hello”一定不存在。
#pragma once
#include "BitSet.hpp"
#include "Common.h"
#include <iostream>
using namespace std;
namespace bite
{
template<class T, size_t N
, class T2Int1 = BKDRHash 代表使用五种不同的映射函数
, class T2Int2 = APHash
, class T2Int3 = DJBHash
, class T2Int4 = SDBMHash
, class T2Int5 = RSHash>
class BloomFilter
{
public:
BloomFilter()
: _size(0)
{}
void Insert(const T& data)
{
size_t totalBitSzie = _bst.size();
size_t pos1 = T2Int1()(data) % totalBitSzie;
size_t pos2 = T2Int2()(data) % totalBitSzie;
size_t pos3 = T2Int3()(data) % totalBitSzie;
size_t pos4 = T2Int4()(data) % totalBitSzie;
size_t pos5 = T2Int5()(data) % totalBitSzie;
_bst.set(pos1); 通过不同的映射函数
_bst.set(pos2); 分别对的得到的映射位置置1
_bst.set(pos3);
_bst.set(pos4);
_bst.set(pos5);
_size++; 插入数据后，给_size++
}
bool Find(const T& data)
{
size_t totalBitSzie = _bst.size();
size_t pos = T2Int1()(data) % totalBitSzie;
if (!_bst.test(pos))
return false;
pos = T2Int2()(data) % totalBitSzie;
if (!_bst.test(pos))
return false;
pos = T2Int3()(data) % totalBitSzie;
if (!_bst.test(pos))
return false;
pos = T2Int4()(data) % totalBitSzie;
if (!_bst.test(pos))
return false;
pos = T2Int5()(data) % totalBitSzie;
if (!_bst.test(pos))
return false;
// 数据可能存在
return true;
}
private:
bitset<N * 5> _bst;
size_t _size;
};
}
void TestBloomFilter()
{
bite::BloomFilter<string, 100> bf;
bf.Insert("欧阳锋");
bf.Insert("欧阳克");
bf.Insert("金轮法王");
bf.Insert("东方不败");
bf.Insert("霍都");
if (bf.Find("欧阳锋"))
{
cout << "欧阳锋可能是坏人" << endl;
}
else
{
cout << "欧阳锋是好人" << endl;
}
if (bf.Find("杨过"))
{
cout << "杨过可能是坏人" << endl;
}
else
{
cout << "杨过是好人" << endl;
}
}#include "Common.h" 里面是五种不同的哈希映射函数。
#pragma once
#include <string>
using std::string;
size_t GetNextPrime(size_t prime);
struct BKDRHash
{
size_t operator()(const string& s)
{
// BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 31;
value += ch;
}
return value;
}
};
struct APHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (size_t i = 0; i < s.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
struct SDBMHash
{
size_t operator()(const string& s)
{
unsigned int hash = 0;
const char* str = s.c_str();
while (*str)
{
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
}
return (hash & 0x7FFFFFFF);
}
};
struct RSHash
{
size_t operator()(const string& s)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;
const char* str = s.c_str();
while (*str)
{
hash = hash * a + (*str++);
a *= b;
}
return (hash & 0x7FFFFFFF);
}
};布隆过滤器的删除
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
比如：删除上图中 "tencent" 元素，如果直接将该元素所对应的二进制比特位置 0 ， “baidu” 元素也
被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给 k 个计
数器 (k 个哈希函数计算出的哈希地址 ) 加一，删除元素时，给 k 个计数器减一，通过多占用几倍存储
空间的代价来增加删除操作。
缺陷：
1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕
布隆过滤器优点
1. 增加和查询元素的时间复杂度为 :O(K), (K 为哈希函数的个数，一般比较小 ) ，与数据量大小无
关
2. 哈希函数相互之间没有关系，方便硬件并行运算 （可执行不同的线程来并行实现哈希计算）
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
布隆过滤器缺陷
1. 有误判率，即存在假阳性 (False Position) ，即不能准确判断元素是否在集合中 ( 补救方法：再
建立一个白名单，存储可能会误判的数据 )
2. 不能获取元素本身（既是好处又是坏处）
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题