【数据结构】位图BitMap、布隆过滤器的算法实现-创新互联
我们先给出之前我看过的腾讯公司的一道笔试题,引出位图BitMap。
我们提供的服务有:网站设计、做网站、微信公众号开发、网站优化、网站认证、铁岭县ssl等。为上1000+企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的铁岭县网站制作公司给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]; } templatestruct __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函数)::
#define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; #include #include "Common.h" #include "BitMap.h" template , class HashFunc2 = __HashFunc2 , class HashFunc3 = __HashFunc3 , class HashFunc4 = __HashFunc4 , class HashFunc5 = __HashFunc5 > class BloomFilter { public: BloomFilter(size_t capacity =0) { _capacity = _GetnewSize(capacity); _bm.Resize(capacity); } void Set(const T& 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); _bm.Set(index1%_capacity); _bm.Set(index2%_capacity); _bm.Set(index3%_capacity); _bm.Set(index4%_capacity); _bm.Set(index5%_capacity); } bool Test(const T& key) { 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; } return true; } private: BitMap _bm; size_t _capacity;//布隆过滤器的容量 }; void TestBloomFilter() { BloomFilter<> bf(100); bf.Set("Just Do IT!"); bf.Set("布隆过滤器"); bf.Set("https://mail.google.com/mail/#inbox"); cout << "Is exist? :" << bf.Test("测试工程师") << endl; cout << "Is exist? :" << bf.Test("开发工程师") << endl; cout << "Is exist? :" << bf.Test("IT") << endl; cout << "Is exist? :" << bf.Test("布隆过滤器") << endl; cout << "Is exist? :" << bf.Test("BloomFilter") << endl; cout << "Is exist? :" << bf.Test("https://mail.google.com/mail/#inbox") << endl; cout << "Is exist? :" << bf.Test("https://mail.google.com/mail/#inbox111111") << endl; } int main() { TestBloomFilter(); system("pause"); return 0; }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
当前文章:【数据结构】位图BitMap、布隆过滤器的算法实现-创新互联
网站链接:http://scyanting.com/article/disees.html