如何理解，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

我們提供的服務(wù)有：成都做網(wǎng)站、網(wǎng)站設(shè)計(jì)、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、長(zhǎng)寧ssl等。為上千企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的長(zhǎng)寧網(wǎng)站制作公司

  布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

    如果想要判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將所有元素保存起來(lái)，然后通過(guò)比較確定。鏈表，樹(shù)等等數(shù)據(jù)結(jié)構(gòu)都是這種思路. 但是隨著集合中元素的增加，我們需要的存儲(chǔ)空間越來(lái)越大，檢索速度也越來(lái)越慢(O(n),O(logn))。不過(guò)世界上還有一種叫作散列表（又叫哈希表，Hash table）的數(shù)據(jù)結(jié)構(gòu)。它可以通過(guò)一個(gè)Hash函數(shù)將一個(gè)元素映射成一個(gè)位陣列（Bit array）中的一個(gè)點(diǎn)。這樣一來(lái)，我們只要看看這個(gè)點(diǎn)是不是1就可以知道集合中有沒(méi)有它了。這就是布隆過(guò)濾器的基本思想。【詳見(jiàn)百度百科】

   總的來(lái)說(shuō)：布隆過(guò)濾器就是利用哈希算法+位圖實(shí)現(xiàn)的。

  所以布隆過(guò)濾器的底層我們就用一個(gè)位圖封裝。

   對(duì)哈希算法不熟悉的可以看博主博客http://helloleex.blog.51cto.com/10728491/1770568

   如果對(duì)位圖不太熟悉的可以查看博主的博客http://helloleex.blog.51cto.com/10728491/1772827

#pragma once
#include<string>
#include"Bit_Map.h"
#include"HashFunc.h"
using namespace std;

//5個(gè)哈希函數(shù)的仿函數(shù)
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)
	{
		//size_t newsize = _GetNextPrime(size);
		//_capacity = newsize;
		//size不一定是素?cái)?shù)，在素?cái)?shù)表中取一個(gè)素?cái)?shù)開(kāi)一個(gè)素?cái)?shù)大的空間
		_capacity = _bm.Resize(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);
		_bm.Set(index1);
		_bm.Set(index2);
		_bm.Set(index3);
		_bm.Set(index4);
		_bm.Set(index5);
	}

	//布隆過(guò)濾器不能執(zhí)行刪除操作，因?yàn)橛胁煌墓Ｋ惴?，可能不同的key
	//標(biāo)記在相同的位上，刪除會(huì)把別人的記錄給刪除了，影響正確性。
	//void Reset(const K& key);

	//測(cè)試存在不一定存在，不存在一定不存在
	bool Test(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);
		if (_bm.Test(index1) || _bm.Test(index2) ||
			_bm.Test(index3) || _bm.Test(index4) ||
			_bm.Test(index5))
			return true;
		else
			return false;
	}
protected:
	BitMap _bm;
	size_t _capacity;
};

HashFunc.h
//5個(gè)高效的哈希算法，都是大神發(fā)明的。
#pragma once
template<class T>
//BKDR Hash Function是一種簡(jiǎn)單快捷的hash算法，
//也是Java目前采用的字符串的Hash算法（累乘因子為31）
struct _HashFunc1
{
	size_t operator()(const T& str)
	{
		register size_t hash = 0;
		const char* tmp = str.c_str();
		while (size_t ch = (size_t)*tmp++)
		{
			hash = hash * 131 + ch;
		}
		return hash;
	}
};
template<class T>
//RS Hash Function。因Robert Sedgwicks在其《Algorithms in C》一書(shū)中展示而得名。
struct _HashFunc2
{
	size_t operator()(const T& str)
	{
		register size_t hash = 0;
		size_t magic = 63689;
		const char* tmp = str.c_str();
		while (size_t ch = (size_t)*tmp++)
		{
			hash = hash * magic + ch;
			magic *= 378551;
		}
		return hash;
	}
}; template<class T>
//AP Hash Function 由Arash Partow發(fā)明的一種hash算法。
struct _HashFunc3
{
	size_t operator()(const T& str)
	{
		register size_t hash = 0;
		size_t ch;
		const char* tmp = str.c_str();
		for (long i = 0; ch = (size_t)*tmp++; i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
}; 

template<class T>
// DJB Hash Function 2。由Daniel J. Bernstein 發(fā)明的另一種hash算法。
struct _HashFunc4
{
	size_t operator()(const T& str)
	{
		const char* tmp = str.c_str();
		if (!*tmp)   // 這是由本人添加，以保證空字符串返回哈希值0  
			return 0;
		register size_t hash = 5381;
		while (size_t ch = (size_t)*tmp++)
		{
			hash = hash * 33 ^ ch;
		}
		return hash;
	}
}; 

template<class T>
//JS Hash Function 。由Justin Sobel發(fā)明的一種hash算法。
struct _HashFunc5
{
	size_t operator()(const T& str)
	{
		const char* tmp = str.c_str();
		if (!*tmp)        // 這是由本人添加，以保證空字符串返回哈希值0  
			return 0;
		register size_t hash = 1315423911;
		while (size_t ch = (size_t)*tmp++)
		{
			hash ^= ((hash << 5) + ch + (hash >> 2));
		}
		return hash;
	}
};

  布隆過(guò)濾器是有誤識(shí)別率的，雖然幾率很低很低，但是如果5個(gè)哈希函數(shù)其中有一兩個(gè)誤識(shí)別了，就會(huì)出現(xiàn)錯(cuò)誤。

   而且布隆過(guò)濾器是不支持刪除Reset的。因?yàn)橛泻軒茁蕰?huì)刪除其他哈希函數(shù)所標(biāo)識(shí)的記錄，誤識(shí)別幾率大大增高。

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)頁(yè)題目：如何理解-創(chuàng)新互聯(lián)
文章鏈接：http://chinadenli.net/article28/didhcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營(yíng)銷型網(wǎng)站建設(shè)、微信小程序、網(wǎng)頁(yè)設(shè)計(jì)公司、云服務(wù)器、響應(yīng)式網(wǎng)站、微信公眾號(hào)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)