位圖&布隆過濾器

位圖定義：

  利用位的狀態來存放一個數是否存在，其實就是把一個數映射成一個簡單的數用以標記他是否存在，一般使用情況為查找一個數是否存在。

數據結構：

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;
}