【数据结构】位图BitMap与布隆过滤器BloomFilter-创新互联
首先先看一下下面这个腾讯的面试题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。 【腾讯】
思路一：
最容易想到的解法就是遍历所有的40多亿个整数，然后一个一个判断。但是这个需要花费的内存是多大呢？
大家可以去算一下，这里我就直接给出结果为16G，是不是需要的空间很大啊。如果面试官给出限制条件，要你使用的空间少于多少，遍历的方法就行不通啦。
思路二：
我们可以把一个×××再细分一下，一个int类型就可以编程32个位，每一位用0，1表示当前这个位置上是否存有值，同样是利用哈希存储的方法。只是这样存储的话就可以减少很多的空间了，例如上题使用的内存就可以从16G降到500M的内存。空间的使用率减少了不止一点。
位图的实现
#ifndef __BITMAP_H__
#define __BITMAP_H__
#include <vector>
#include "Common.h"
class BitMap
{
public:
BitMap(size_t size = 0)
:_size(0)
{
_a.resize((size>>5)+1);
}
//插入数据
void Set(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
//如果当前位置不存在值，直接插入
if (!(_a[index] & (1 << num)))//判断这个位上是不是等0的
{
++_size;
_a[index] |= (1 << num);//将当前位上的值置成1
}
}
void Reset(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
//判断当前位上的值是不是等于1，等于1删除
if (_a[index] & (1 << num))
{
--_size;
_a[index] &= ~(1 << num);//将当前位置成0
}
}
bool Test(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
//如果当前位等于1，那么存在
if (_a[index] & (1 << num))
{
return true;
}
return false;
}
void Resize(size_t size)
{
_a.resize((size >> 5) + 1);
}
size_t Size()
{
return _size;
}
private:
vector<size_t> _a;
size_t _size;//位图上插入了多少值
};
void Test()
{
BitMap bm(35);
bm.Set(4);
bm.Set(5);
bm.Set(6);
cout << "is4Exist?->" << bm.Test(4) << endl;
cout <<"is5Exist?->"<< bm.Test(5) << endl;
bm.Reset(5);
cout << "is4Exist?->" << bm.Test(4) << endl;
cout << "is5Exist?->" << bm.Test(5) << endl;
}
#endif //__BITMAP_H__布隆过滤器 Bloom Filter
原理
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢。
Bloom Filter 是一种空间效率很高的随机数据结构，Bloom filter 可以看做是对 bit-map 的扩展, 它的原理是：
当一个元素被加入集合时，通过 K 个 Hash函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：
如果这些点有任何一个 0，则被检索元素一定不在；
如果都是 1，则被检索元素可能在。
如果只是空洞的说这些原理的话，肯定大家都不知道布隆过滤器有什么用处。布隆过滤器对于单机来说可能用处不是很大，但对于分布式来说就比较有用了。
如主从分布：一个数组过来，我想要知道他是不是在内存中，我们是不是需要一个一个去访问磁盘，判断数据是否存在。但是问题来了访问磁盘的速度是很慢的，所以效率会很低，如果使用布隆过滤器，我们就可以先去过滤器这个集合里面找一下对应的位置的数据是否存在。虽然布隆过滤器有他的缺陷，但是我们能够知道的是当前位置为0是肯定不存在的，如果都不存在，就不需要去访问了。
下面来讲一下布隆过滤器的缺陷：
缺陷一：误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。所以我们用多个哈希表去 存储一个数据。那么问题又来了，我们是多用一些呢，还是少用一些。如果多用哈希表的话，如上面的题，一个哈希就需要500M，那么放的越多是不是越占内存啊。如果太少的话是不是误算率就高啊，所以取个适中的。下面我的实现是取了五个哈希表(没有什么根据，只是把思路展现出来一下，能够分析出取多少个，那都是大牛们弄出来的算法，我当前水平不够~)
缺陷二：如果当前位置为0肯定不存在，但是为1不一定存在
布隆过滤器的实现：（用了素数表和5个哈希算法）
一、5个哈希算法的实现
#ifndef __COMMON_H__
#define __COMMON_H__
size_t GetPrimeSize(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 (size_t i = 0; i < _PrimeSize; i++)
{
if (_PrimeList[i] > size)
{
return _PrimeList[i];
}
if (_PrimeList[_PrimeSize] == size)
return _PrimeList[_PrimeSize - 1];
}
return _PrimeList[_PrimeSize - 1];
}
template<class T>
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& str)
{
return BKDRHash(str.c_str());
}
};
template<class T>
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& str)
{
return SDBMHash(str.c_str());
}
};
template<class T>
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& str)
{
return RSHash(str.c_str());
}
};
template<class T>
struct __HashFunc4
{
size_t APHash(const char *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;
}
size_t operator()(const T& str)
{
return APHash(str.c_str());
}
};
template<class T>
struct __HashFunc5
{
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& str)
{
return JSHash(str.c_str());
}
};
#endif //__COMMON_H__二、布隆过滤器
#ifndef __BLOOMFILTER_H__
#define __BLOOMFILTER_H__
#include <iostream>
using namespace std;
#include<string>
#include"BitMap.h"
#include "Common.h"
template<class K = string,
class HashFunc1 = __HashFunc1<K>,
class HashFunc2 = __HashFunc2<K>,
class HashFunc3 = __HashFunc3<K>,
class HashFunc4 = __HashFunc4<K>,
class HashFunc5 = __HashFunc5<K>>
class BloomFilter
{
public:
BloomFilter(size_t size = 0)
{
_capacity = GetPrimeSize(size);
_bitMap.Resize(_capacity);
}
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);
_bitMap.Set(index1%_capacity);//设置为第多少位的数，然后调用位图的Set设置成第几个字节的第几位
_bitMap.Set(index2%_capacity);
_bitMap.Set(index3%_capacity);
_bitMap.Set(index4%_capacity);
_bitMap.Set(index5%_capacity);
}
bool Test(const K& key)
{
size_t index1 = HashFunc1()(key);
if (!(_bitMap.Test(index1%_capacity)))//为1不一定存在，为0肯定不存在
return false;
size_t index2 = HashFunc2()(key);
if (!(_bitMap.Test(index2%_capacity)))
return false;
size_t index3 = HashFunc3()(key);
if (!(_bitMap.Test(index3%_capacity)))
return false;
size_t index4 = HashFunc4()(key);
if (!(_bitMap.Test(index4%_capacity)))
return false;
size_t index5 = HashFunc4()(key);
if (!(_bitMap.Test(index5%_capacity)))
return false;
return true;
}
protected:
BitMap _bitMap;
size_t _capacity;
};
void TestBloomFilter()
{
BloomFilter<> bf(50);
bf.Set("臧");
bf.Set("静");
bf.Set("比特");
bf.Set("peter");
bf.Set("徐");
bf.Set("http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html");
bf.Set("http://www.cnblogs.com/-clq/archive/2012/05/31/2528155.html");
cout << "Exist?->:" << bf.Test("臧") << endl;
cout << "Exist?->:" << bf.Test("静") << endl;
cout << "Exist?->:" << bf.Test("peter") << endl;
cout << "Exist?->:" << bf.Test("徐航") << endl;
cout << "Exist?->:" << bf.Test("http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html") << endl;
cout << "Exist?->:" << bf.Test("http://www.cnblogs.com/-clq/archive/2012/05/31/25288153.html") << endl;
}
#endif //__BLOOMFILTER_H__另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
当前名称：【数据结构】位图BitMap与布隆过滤器BloomFilter-创新互联
转载来于：https://www.cdcxhl.com/article20/hodjo.html
成都网站建设公司_创新互联，为您提供网站收录、移动网站建设、用户体验、微信小程序、品牌网站建设、商城网站
声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联
- 美国云服务器有什么好处 2021-01-30
- 日本云服务器有流量限制吗？ 2022-10-05
- 为什么云服务器比虚拟主机贵？贵在哪？ 2022-10-03
- 境外服务器可以租用吗？境外云服务器租用必须知道的几个问题 2022-10-07
- 外贸建站租用香港云服务器还是美国云服务器好？ 2022-10-02
- 云计算时代，建站选择虚拟主机还是云服务器 2021-02-13
- 免费服务器真的靠谱吗？盘点国内外免费云服务器那些坑 2022-10-08
- 企业适不适合租用云服务器？这七个方面告诉你 2022-10-13
- 日本樱花云服务器免费网站省钱吗？日本樱花服务器的优势是什么？ 2022-10-04
- 云服务器和vps有什么区别吗 2016-10-18
- 云服务器多大带宽合适 2021-11-24
- 为何云服务器如此受欢迎? 2021-03-05