這篇文章給大家分享的是有關(guān)編程開發(fā)中如何實現(xiàn)布隆過濾器的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

旺蒼ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為成都創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：13518219792（備注：SSL證書合作）期待與您的合作！

  給40億個不重復(fù)的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快速判斷一個數(shù)是否在這40億個數(shù)中。

  拿到這個題目，我們首先想到的是遍歷這40億的數(shù)字，然后一個一個找。顯然是行不通的。因為這40億個數(shù)放到內(nèi)存中，大約需要16G內(nèi)存。

  如果我們把它轉(zhuǎn)換成位圖處理，那么就好處理多了。我們可以把一個×××再細(xì)分一下，一個int類型就可以編程32個位，每一位用0，1表示當(dāng)前這個位置上是否存有值，同樣是利用哈希存儲的方法。只是這樣存儲的話就可以減少很多的空間了，例如上題使用的內(nèi)存就可以從16G降到500M的內(nèi)存?？臻g的使用率減少了不止一點。

   大家可以根據(jù)我這個方法實現(xiàn)上面的代碼，今天我主要介紹的是布隆過濾器，因為布隆過濾器也要用到位圖（bitmap），位圖實現(xiàn)思想：

   1.把一個int類型變成32個bits。

   2.把它們?nèi)砍跏蓟癁?。

   3.如果當(dāng)前位上有值，把0置成1。

下面我給出位圖的實現(xiàn)代碼：

BitMap.h中

#include <vector>

class BitMap
{
public:
	BitMap(size_t size = 0)
		:_size(0)
	{
		//用resize開辟空間，_a中的值會被初始化為0

		//加1為了讓值全部能放到數(shù)組中，假如有36個數(shù)，36/32=1余4，而
		//多開的那個空間就保證了這4個數(shù)能放下

		//_a.resize(size/32+1);和下面的代碼一個性質(zhì)，只不過用移位運算符比除法的效率高
		_a.resize((size >> 5) + 1);
	}
	//插入
	void Set(size_t x)
	{
		size_t index = x >> 5;
		size_t num = x % 32;
		//當(dāng)前位置如果等于0，沒有值，可以插入
		if (!(_a[index] & (1 << num)))
		{
			_a[index] |= (1 << num);//當(dāng)前位置置1
			++_size;
		}
	}
	//刪除
	void Reset(size_t x)
	{
		size_t index = x >> 5;
		size_t num = x % 32;
		//當(dāng)前位置為1，有值，可以刪除
		if (_a[index] & (1 << num))
		{
			_a[index] &= ~(1 << num);//當(dāng)前位置置0
			--_size;
		}
	}
	//判斷是否有值
	bool BitMapTest(size_t x)
	{
		size_t index = x >> 5;
		size_t num = x % 32;
		if (_a[index] & (1 << num))
		{
			return true;
		}
		return false;
	}
	void Resize(size_t size)
	{
		_a.resize(size);
	}
protected:
	vector<size_t> _a;
	size_t _size;
};

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

    Hash面臨的問題就是沖突。假設(shè) Hash 函數(shù)是良好的，如果我們的位陣列長度為 m 個點，那么如果我們想將沖突率降低到例如 1%, 這個散列表就只能容納 m/100 個元素。顯然這就不叫空間有效了（Space-efficient）。解決方法也簡單，就是使用多個 Hash，如果它們有一個說元素不在集合中，那肯定就不在。如果它們都說在，雖然也有一定可能性它們在說謊，不過直覺上判斷這種事情的概率是比較低的。

優(yōu)點

相比于其它的數(shù)據(jù)結(jié)構(gòu)，布隆過濾器在空間和時間方面都有巨大的優(yōu)勢。布隆過濾器存儲空間和插入/查詢時間都是常數(shù)。另外, Hash 函數(shù)相互之間沒有關(guān)系，方便由硬件并行實現(xiàn)。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴(yán)格的場合有優(yōu)勢。

布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能；

k 和 m 相同，使用同一組 Hash 函數(shù)的兩個布隆過濾器的交并差運算可以使用位操作進(jìn)行。

缺點

但是布隆過濾器的缺點和優(yōu)點一樣明顯。誤算率（False Positive）是其中之一。隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素. 我們很容易想到把位列陣變成整數(shù)數(shù)組，每插入一個元素相應(yīng)的計數(shù)器加1, 這樣刪除元素時將計數(shù)器減掉就可以了。然而要保證安全的刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點單憑這個過濾器是無法保證的。另外計數(shù)器回繞也會造成問題。

下面給出布隆過濾器的實現(xiàn)代碼：

仿函數(shù)實現(xiàn)，我用了5個仿函數(shù)，它們的實現(xiàn)我是看http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html這里面實現(xiàn)的，他的實現(xiàn)比較好，能更好的避免哈希沖突。

commom.h中

#pragma once

#include <string>
size_t NewSize(size_t size)
{
	// 使用素數(shù)表對齊做哈希表的容量，降低哈希沖突
	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 (int i = 0; i < _PrimeSize; i++)
	{
		if (_PrimeList[i]>size)
		{
			return _PrimeList[i];//按照素數(shù)表來設(shè)置容量大小
		}
	}
	//當(dāng)需要的容量超過素數(shù)表的大容量，我們就按照大的來擴(kuò)容
	return _PrimeList[_PrimeSize - 1];
}
template <class T>
struct __HashFunc1
{
	size_t BKDRHash(const T *str)
	{
		register size_t hash = 0;
		while (size_t ch = (size_t)*str++)
		{
			hash = hash * 131 + ch;   
		}
		return hash;
	}
	size_t operator()(const T& key)
	{
		return BKDRHash(key.c_str());
	}
};
template <class T>
struct __HashFunc2
{
	size_t SDBMHash(const T *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& key)
	{
		return SDBMHash(key.c_str());
	}
};
template <class T>
struct __HashFunc3
{
	size_t RSHash(const T *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& key)
	{
		return RSHash(key.c_str());
	}
};

template <class T>
struct __HashFunc4
{
	size_t APHash(const T *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& key)
	{
		return APHash(key.c_str());
	}
};
template <class T>
struct __HashFunc5
{
	size_t JSHash(const T *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& key)
	{
		return JSHash(key.c_str());
	}
};

我使用了5個Hash函數(shù)，可以降低哈希沖突。大家視情況而定，自己設(shè)置哈希函數(shù)的個數(shù)。

BoolmFilter.h中

#pragma once

#include<string>
#include "BitMap.h"
#include "common.h"
template<class T = string,
	class HashFunc1=__HashFunc1<T>,
	class HashFunc2 = __HashFunc2<T>,
	class HashFunc3 = __HashFunc3<T>,
	class HashFunc4 = __HashFunc4<T>,
	class HashFunc5 = __HashFunc5<T>
>
class BoolmFilter
{
public:
	BoolmFilter(size_t capatity = 0)
	{
		_capatity = NewSize(capatity);
		_bm.Resize(_capatity);
	}
	void Set(const T& 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%_capatity);
		_bm.Set(index2%_capatity);
		_bm.Set(index3%_capatity);
		_bm.Set(index4%_capatity);
		_bm.Set(index5%_capatity);
	}
	bool Test(const T& key)
	{
		size_t index1 = HashFunc1()(key);
		if (!_bm.BitMapTest(index1%_capatity))
		{
			return false;
		}
		size_t index2 = HashFunc2()(key);
		if (!_bm.BitMapTest(index2%_capatity))
		{
			return false;
		}
		size_t index3 = HashFunc3()(key);
		if (!_bm.BitMapTest(index3%_capatity))
		{
			return false;
		}
		size_t index4 = HashFunc4()(key);
		if (!_bm.BitMapTest(index4%_capatity))
		{
			return false;
		}
		size_t index5 = HashFunc5()(key);
		if (!_bm.BitMapTest(index5%_capatity))
		{
			return false;
		}
		return true;
	}
protected:
	BitMap _bm;
	size_t _capatity;
};

test.cpp中

#include <iostream>
using namespace std;
#include "BoolmFilter.h"

void BoolTest()
{
	BoolmFilter<>bf(100);
	bf.Set("she is girl");
	bf.Set("我是好人");
	bf.Set("chive/2012/05/31/2528153.html");
	cout << bf.Test("she is girl") << endl;
	cout << bf.Test("我是好人") << endl;
	cout << bf.Test("chive/2012/05/31/2528153.html") << endl;
}
int main()
{
	BoolTest();
	system("pause");
	return 0;
}

感謝各位的閱讀！關(guān)于“編程開發(fā)中如何實現(xiàn)布隆過濾器”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！

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

文章名稱：編程開發(fā)中如何實現(xiàn)布隆過濾器-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://aaarwkj.com/article34/dopope.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、網(wǎng)站營銷、商城網(wǎng)站、服務(wù)器托管、做網(wǎng)站、移動網(wǎng)站建設(shè)

廣告

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