13518219792
我们先给出之前我看过的腾讯公司的一道笔试题，引出位图BitMap。
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
这个问题怎么解决呢？
1）将40亿数据保存起来（保存在数组、链表、树中），再和该数判断是否相等。
那我们思考一下需要多少内存：
2）借助位图BitMap解决。
位图（BitMap）
是用一个数组中的每个数据的每个二进制位表示一个数是否存在。1表示存在，0表示不存在。
相当于把数组分成很多块的空间，每一块是32个比特位。
原来32个比特位放一个数据，现在一个位就可以放一个数据。16GB/32=0.5GB=512MB。
位图的实现：
#ifndef __BITMAP_H__ #define __BITMAP_H__ #includeusing namespace std; #include class BitMap { public: BitMap(size_t size = 0) :_size(0) { //_a开辟多一个空间，如size=36/32=1,需要两块空间才能放下 _a.resize((size >> 5) + 1); } void Set(size_t x) { //size_t index = x / 32; size_t index = (x >> 5); size_t num = x % 32; //if(!(_a[index] & (1 << num))表示该二进制位不存在，则该位二进制置成1 if (!(_a[index] & (1 << num))) { _a[index] |= (1 << num); ++_size; } } void Reset(size_t x) { //size_t index = x / 32; size_t index = x >> 5; size_t num = x % 32; //该位存在则将该位二进制置为0 if (_a[index] & (1 << num)) { _a[index] &= ~(1 << num); --_size; } } bool Test(size_t x) { //size_t index = x / 32; size_t index = x >> 5; size_t num = x % 32; if (_a[index] & (1 << num)) { return true; } return false; } void Resize(size_t size) { _a.resize(size); } private: vector _a; size_t _size; }; #endif //__BITMAP_H__
布隆过滤器（BloomFilter）
它是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。那我们可以利用哈希函数计算出它具体的存放位置。
它的优点是空间效率和查询时间都远远超过一般的算法，将这40亿的数据内存由16GB变成500MB,可见其强大。
缺点是有一定的误识别率、不便于删除。布隆过滤器会出现：检测存在，而实际中却不存在。而不会出现：实际中不存在，而检测存在。
代码实现（仿函数实现，选取5个位图）：
#define _CRT_SECURE_NO_WARNINGS 1
#ifndef __COMMON__
#define __COMMON__
size_t _GetnewSize(size_t _size)
{
static const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
for (int i = 0; i < _PrimeSize; i++)
{
if (_PrimeList[i]> _size)
{
return _PrimeList[i];
}
}
return _PrimeList[_PrimeSize - 1];
}
template
struct __HashFunc1
{
size_t BKDRHash(const char *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313..
}
return hash;
}
size_t operator()(const T& key)
{
return BKDRHash(key.c_str());
}
};
template
struct __HashFunc2
{
size_t SDBMHash(const char *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
size_t operator()(const T& key)
{
return SDBMHash(key.c_str());
}
};
template
struct __HashFunc3
{
size_t RSHash(const char *str)
{
register size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
{
hash = hash * magic + ch;
magic *= 378551;
}
return hash;
}
size_t operator()(const T& key)
{
return RSHash(key.c_str());
}
};
template
struct __HashFunc4
{
size_t JSHash(const char *str)
{
if (!*str) // 这是由本人添加，以保证空字符串返回哈希值0
return 0;
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}
size_t operator()(const T& key)
{
return JSHash(key.c_str());
}
};
template
struct __HashFunc5
{
size_t DEKHash(const char* str)
{
if (!*str) // 这是由本人添加，以保证空字符串返回哈希值0
return 0;
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
}
return hash;
}
size_t operator()(const T& key)
{
return DEKHash(key.c_str());
}
};
#endif//__COMMON__ 布隆过滤器代码实现（借助素数表获取下一个素数，选取合适的容量--》hash函数）：：
