首先先看一下下面這個(gè)騰訊的面試題：
我們提供的服務(wù)有：成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、廣靈ssl等。為千余家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢(xún)和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的廣靈網(wǎng)站制作公司
給40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，沒(méi)排過(guò)序。給一個(gè)無(wú)符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中。 【騰訊】
思路一：
最容易想到的解法就是遍歷所有的40多億個(gè)整數(shù)，然后一個(gè)一個(gè)判斷。但是這個(gè)需要花費(fèi)的內(nèi)存是多大呢？
大家可以去算一下，這里我就直接給出結(jié)果為16G，是不是需要的空間很大啊。如果面試官給出限制條件，要你使用的空間少于多少，遍歷的方法就行不通啦。
思路二：
我們可以把一個(gè)×××再細(xì)分一下，一個(gè)int類(lèi)型就可以編程32個(gè)位，每一位用0，1表示當(dāng)前這個(gè)位置上是否存有值，同樣是利用哈希存儲(chǔ)的方法。只是這樣存儲(chǔ)的話(huà)就可以減少很多的空間了，例如上題使用的內(nèi)存就可以從16G降到500M的內(nèi)存?？臻g的使用率減少了不止一點(diǎn)。
位圖的實(shí)現(xiàn)
#ifndef __BITMAP_H__ #define __BITMAP_H__ #include#include "Common.h" class BitMap { public: BitMap(size_t size = 0) :_size(0) { _a.resize((size>>5)+1); } //插入數(shù)據(jù) void Set(size_t x) { size_t index = x >> 5; size_t num = x % 32; //如果當(dāng)前位置不存在值，直接插入 if (!(_a[index] & (1 << num)))//判斷這個(gè)位上是不是等0的 { ++_size; _a[index] |= (1 << num);//將當(dāng)前位上的值置成1 } } void Reset(size_t x) { size_t index = x >> 5; size_t num = x % 32; //判斷當(dāng)前位上的值是不是等于1，等于1刪除 if (_a[index] & (1 << num)) { --_size; _a[index] &= ~(1 << num);//將當(dāng)前位置成0 } } bool Test(size_t x) { size_t index = x >> 5; size_t num = x % 32; //如果當(dāng)前位等于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 _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__
如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將集合中所有元素保存起來(lái)，然后通過(guò)比較確定。鏈表、樹(shù)、散列表（又叫哈希表，Hash table）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路。但是隨著集合中元素的增加，我們需要的存儲(chǔ)空間越來(lái)越大。同時(shí)檢索速度也越來(lái)越慢。
Bloom Filter 是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，Bloom filter 可以看做是對(duì) bit-map 的擴(kuò)展, 它的原理是：
當(dāng)一個(gè)元素被加入集合時(shí)，通過(guò)K 個(gè)Hash函數(shù)將這個(gè)元素映射成一個(gè)位陣列（Bit array）中的 K 個(gè)點(diǎn)，把它們置為1。檢索時(shí)，我們只要看看這些點(diǎn)是不是都是 1 就（大約）知道集合中有沒(méi)有它了：
如果這些點(diǎn)有任何一個(gè) 0，則被檢索元素一定不在；
如果都是 1，則被檢索元素可能在。
如果只是空洞的說(shuō)這些原理的話(huà)，肯定大家都不知道布隆過(guò)濾器有什么用處。布隆過(guò)濾器對(duì)于單機(jī)來(lái)說(shuō)可能用處不是很大，但對(duì)于分布式來(lái)說(shuō)就比較有用了。
如主從分布：一個(gè)數(shù)組過(guò)來(lái)，我想要知道他是不是在內(nèi)存中，我們是不是需要一個(gè)一個(gè)去訪(fǎng)問(wèn)磁盤(pán)，判斷數(shù)據(jù)是否存在。但是問(wèn)題來(lái)了訪(fǎng)問(wèn)磁盤(pán)的速度是很慢的，所以效率會(huì)很低，如果使用布隆過(guò)濾器，我們就可以先去過(guò)濾器這個(gè)集合里面找一下對(duì)應(yīng)的位置的數(shù)據(jù)是否存在。雖然布隆過(guò)濾器有他的缺陷，但是我們能夠知道的是當(dāng)前位置為0是肯定不存在的，如果都不存在，就不需要去訪(fǎng)問(wèn)了。
下面來(lái)講一下布隆過(guò)濾器的缺陷：
缺陷一：誤算率（False Positive）是其中之一。隨著存入的元素?cái)?shù)量增加，誤算率隨之增加。但是如果元素?cái)?shù)量太少，則使用散列表足矣。所以我們用多個(gè)哈希表去 存儲(chǔ)一個(gè)數(shù)據(jù)。那么問(wèn)題又來(lái)了，我們是多用一些呢，還是少用一些。如果多用哈希表的話(huà)，如上面的題，一個(gè)哈希就需要500M，那么放的越多是不是越占內(nèi)存啊。如果太少的話(huà)是不是誤算率就高啊，所以取個(gè)適中的。下面我的實(shí)現(xiàn)是取了五個(gè)哈希表(沒(méi)有什么根據(jù)，只是把思路展現(xiàn)出來(lái)一下，能夠分析出取多少個(gè)，那都是大牛們弄出來(lái)的算法，我當(dāng)前水平不夠~)
缺陷二：如果當(dāng)前位置為0肯定不存在，但是為1不一定存在
布隆過(guò)濾器的實(shí)現(xiàn)：（用了素?cái)?shù)表和5個(gè)哈希算法）
一、5個(gè)哈希算法的實(shí)現(xiàn)
重慶分公司
重慶分公司
#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
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
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
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
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
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__ 二、布隆過(guò)濾器
