位图(BitMap)&&布隆过滤器(BloomFilter)
【面试题】给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。
站在用户的角度思考问题,与客户深入沟通,找到岚县网站设计与岚县网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站建设、成都网站设计、企业官网、英文网站、手机端网站、网站推广、国际域名空间、网页空间、企业邮箱。业务覆盖岚县地区。
● 在看到这个题后最先想到的方法是遍历这40亿个数,依次进行判断,但此做法需要的内存很大,大约为15G(4000000000 * 4 ÷(1024*1024*1024)),可见此算法不可取。
● 如果内存够的话,我们可以通过位图实现,位图一个数组每个数据的每个二进制位表示一个数据,每一位用0,1表示当前这个位置上是否存有值,同样是利用哈希存储的方法。此做法可以大大减少内存,对于此题是一个int类型就可以编程32个位,需要的内存空间从15G降到500M。
具体实现如下:
#pragma class BitMap//位图 { public: BitMap() :_size(0) {} BitMap(size_t size)//size表示多少位,不是数据个数 : _size(size) {//调整大小为size / 32 + 1即右移5位加1(加1:需要的大小要包含size,例如10%8=1,大小应为2) _a.resize((size >> 5) + 1); } //位图中,注意1在移位时为左移num不是左移32-num; void Set(size_t x)//存入x位,置1 { size_t index = x >> 5; size_t num = x % 32;//eg:x = 35,num = 3,则在位图中为_a[1]中设为001 ++_size; _a[index] |= 1 << num;//1左移3位,进行|使_a中对应处为 } void Remove(size_t x)//删除x位,置0 { size_t index = x >> 5; size_t num = x % 32;//eg:x = 35,num = 3,则在位图中为_a[1]中设为110 --_size; _a[index] &= (~(1 << num));//1右移3位取反0,进行&使_a中对应处为0 } bool Test(size_t x)//判断是否存在 { size_t index = x >> 5; size_t num = x % 32; if (_a[index] & (1 << num))//如果当前位为1,则存在 { return true; } return false; } void Resize(size_t size)//重置大小 { _a.resize((size >> 5) + 1); } size_t Size()//返回位图的总位数 { return _size; } size_t Capacity()//返回int数据个数 { return _a.size(); } void Print() { for (size_t i = 0; i < _a.size(); i++) { cout << _a[i] << " " << endl; } cout << endl; } private: vector_a; size_t _size; }; void TestBitMap() { BitMap bm(65); bm.Set(3); bm.Set(4); bm.Set(5); bm.Print(); cout << "is 4 EXTST? " << bm.Test(4) << endl; cout << "is 8 EXTST? " << bm.Test(8) << endl; bm.Remove(4); cout << "is 4 EXTST? " << bm.Test(4) << endl; bm.Print(); cout << "size: " << bm.Size() << endl; cout << "capacity: " << bm.Capacity() << endl; bm.Resize(100); cout << "capacity: " << bm.Capacity() << endl; }
● Bloom Filter 是一种空间效率很高的随机数据结构,Bloom filter 可以看做是对 bit-map 的扩展, 它的原理是:
当一个元素被加入集合时,通过 K 个 Hash函数将这个元素映射成一个位阵列(Bit array)中的 K 个点,把它们置为 1。检索时,只要看看这些点是不是都是 1 就知道集合中有没有它了。
1、如果这些点有任何一个 0,则被检索元素一定不在;
2、如果都是 1,则被检索元素可能在。
用了素数表和6个哈希算法:
#pragma size_t _GetNextPrime(size_t size)//素数表:获取下一个素数 { 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 (size_t i = 0; i < _PrimeSize; ++i) { if (_PrimeList[i] > size) { return _PrimeList[i]; } return _PrimeList[i - 1]; } return _PrimeList[_PrimeSize];//如果size大于或等于素数表中数据,就返回表中最大数 } //6种字符串哈希算法 templatesize_t BKDRHash(const T * str) { register size_t hash = 0; while (size_t ch = (size_t)*str++) { hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313.. } return hash; } template size_t SDBMHash(const T *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; } template size_t RSHash(const T *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; } template size_t APHash(const T *str) { register size_t hash = 0; size_t ch; for (long i = 0; ch = (size_t)*str++; i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ ch ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ ch ^ (hash >> 5))); } } return hash; } template size_t JSHash(const T *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; } template size_t DEKHash(const T* 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; } //6个仿函数分别进行6种字符串算法的调用 template struct _HashFunc1 { size_t operator()(const T& str) { return BKDRHash(str.c_str()); } }; template struct _HashFunc2 { size_t operator()(const T& str) { return SDBMHash(str.c_str()); } }; template struct _HashFunc3 { size_t operator()(const T& str) { return RSHash(str.c_str()); } }; template struct _HashFunc4 { size_t operator()(const T& str) { return APHash(str.c_str()); } }; template struct _HashFunc5 { size_t operator()(const T& str) { return JSHash(str.c_str()); } }; template struct _HashFunc6 { size_t operator()(const T& str) { return DEKHash(str.c_str()); } };
布隆过滤器具体实现如下:
#define _CRT_SECURE_NO_WARNINGS 1 template, class HashFunc2 = _HashFunc2 , class HashFunc3 = _HashFunc3 , class HashFunc4 = _HashFunc4 , class HashFunc5 = _HashFunc5 , class HashFunc6 = _HashFunc6 > class BloomFilter { public: BloomFilter(size_t size = 0) { _capacity = _GetNextPrime(size); _bm.Resize(_capacity);//调用BitMap的Resize调整大小 } void Set(const K& key) { size_t index1 = HashFunc1()(key); size_t index2 = HashFunc2()(key); size_t index3 = HashFunc3()(key); size_t index4 = HashFunc4()(key); size_t index5 = HashFunc5()(key); size_t index6 = HashFunc6()(key); _bm.Set(index1 % _capacity);//设置的位为index1 % _capacity,调用BitMap的Set _bm.Set(index2 % _capacity); _bm.Set(index3 % _capacity); _bm.Set(index4 % _capacity); _bm.Set(index5 % _capacity); _bm.Set(index6 % _capacity); } bool Test(const K& key) { //只要存在一个为0就不存在,否则存在 size_t index1 = HashFunc1()(key); if (!_bm.Test(index1 % _capacity)) return false; size_t index2 = HashFunc2()(key); if(!_bm.Test(index2 % _capacity)) return false; size_t index3 = HashFunc3()(key); if(!_bm.Test(index3 % _capacity)) return false; size_t index4 = HashFunc4()(key); if(!_bm.Test(index4 % _capacity)) return false; size_t index5 = HashFunc5()(key); if(!_bm.Test(index5 % _capacity)) return false; size_t index6 = HashFunc6()(key); if(!_bm.Test(index6 % _capacity)) return false; return true; } private: BitMap _bm; size_t _capacity; }; void TestBloomFilter() { BloomFilter<> bf(50); bf.Set("Scen"); bf.Set("斯洛"); bf.Set("https://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773181"); cout << "exist? " << bf.Test("Scen") << endl; cout << "exist? " << bf.Test("Scenluo") << endl; cout << "exist? " << bf.Test("斯洛") << endl; cout << "exist? " << bf.Test("https://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773181") << endl; cout << "exist? " << bf.Test("https://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773131") << endl; }
布隆过滤器的缺陷:
1、误算率(False Positive)是其中之一。
随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。所以我们用多个哈希表去存储一个数据。那么问题又来了,我们是多用一些呢,还是少用一些。如果多用哈希表的话,如上面的题,一个哈希就需要500M,那么放的越多是不是越占内存啊。如果太少的话是不是误算率就高啊,所以取个适中的。我的程序实现是取了六个哈希表。
2、如果当前位置为0肯定不存在,但是为1不一定存在。
一般布隆过滤器只支持设计,不支持删除。可以通过引用计数,但空间浪费较大。
分享标题:位图(BitMap)&&布隆过滤器(BloomFilter)
标题路径:http://myzitong.com/article/pecogs.html