位图&布隆过滤器

位图定义：

  利用位的状态来存放一个数是否存在，其实就是把一个数映射成一个简单的数用以标记他是否存在，一般使用情况为查找一个数是否存在。

数据结构：

1/8=0    1%8=1   1<<1(第二个bit位置1)

2/8=0    2%8=2   1<<2(第3个bit位置1)

3/8=0    3%8=3  1<<3(第4个bit位置1)

4/8=0    ....

查找这个数是否存在：

  先算出这个数的存在位置，然后找这个位置是否为1，如果是则存在否则不存在。

缺点：可读性差。

应用：
  1、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中
　　将这40亿个数字存储到bitmap中，然后对于给出的数，判断是否在bitmap中即可。
2、使用位图法判断×××数组是否存在重复
      遍历数组，一个一个放入bitmap，并且检查其是否在bitmap中出现过，如果没出现放入，否则即为重复的元素。
       3、使用位图法进行×××数组排序
      首先遍历数组，得到数组的最大最小值，然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数，都要转化为unsigned int来处理，而且取位的时候，数字要减去最小值。

#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<vector>
class BitMap
{
public:
BitMap(size_t size)
{
_bm.resize(size / 32 + 1);
_size = 0;
}
BitMap()
:_size(0)
{}
void Set(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & 1 << (num % 32)) == 0)
{
_bm[index] |= 1 << (num % 32);
++_size;
}
}
void Reset(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & (1 << (num % 32))) == 1 << (num % 32))
{
_bm[index] &= ~(1 << (num % 32));
--_size;
}
}
bool Test(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & (1 << (num % 32))) == 1 << (num % 32))
{
return true;
}
return false;
}
size_t Size()
{
return _size;
}
private:
vector<unsigned int> _bm;
size_t _size;
};
//
//void test()
//{
//BitMap x(100);
//x.Set(0);
//x.Set(1);
//x.Set(2);
//x.Set(3);
//x.Set(4);
//x.Set(5);
//x.Reset(1);
//x.Reset(3);
//int ret=x.Test(4);
//
//
//}
//int main()
//{
//test();
//system("pause");
//return 0;
//}

利用上述的位图实现布隆过滤器：

仿函数：

   就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

布隆过滤器：

  布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

应用场景：

     字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新 元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来 了。 

优点：

           布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点：

     误算率。随着存入的元素数量增加，误算率随之增加。

#define  _CRT_SECURE_NO_WARNINGS
#include"Map.h"
#include<string>

size_t _GetSize(const 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
};
size_t i = 0;
for (; i < _PrimeSize; i++)
{
if (_PrimeList[i] <= size && i != _PrimeSize - 1)
{
i++;
}
else
{
break;
}
}
return _PrimeList[i];
}


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;    
}
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)
{
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());
}
};


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)
:_bitmap(size),
_capacity(size)
{}
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);
_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)))
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;
}
private:
BitMap _bitmap;
size_t _capacity;
};
void test()
{
BloomFilter<> bf(50);
bf.Set("aaa");
bf.Set("bbb");
bf.Set("ccc");
int ret = bf.Test("acc");
ret = bf.Test("bbb");
ret = bf.Test("aaa");
ret = bf.Test("aaa");
}
int main()
{
test();
system("pause");
return 0;
}