布隆過濾器php

① 布隆過濾器和替代演算法

布隆過濾器和替代演算法：但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。

但是包含查找的數據項的數據文件它一定是會返回的，key-value系統中bloom filter返回的數據文件還是需要查看裡面的內容才能知道是否存在所需的數據的，這就保證了執行結果的正確性和完整性。

只是多訪問一些數據文件而已。在數據量很大key-value系統中，建立統一的B+樹索引的代價是非常大的，維護成本也很高，因此綜合起來bloom filter的性能是最好的。

缺點：

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。常見的補救辦法是建立一個小的白名單，存儲那些可能被誤判的元素。但是如果元素數量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位列陣變成整數數組，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。

② 布隆過濾器用的多少個hash函數

相比於其它的抄數據結構，布隆襲過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數。另外, Hash函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

③ 看過的視頻讓用戶不再觀看為什麼使用布隆過濾器而不是直接使用setBit與getBit進行取值比對呢

不行。

因為布隆過濾器的原理是用多個hash函數對id進行hash後得到一系列值，而在布隆數組中看這些值回對應答的位上是否命中，如果都命中說明這個值重復。
用id不經過hash直接去對比，乍一想好像可以，但是你想想，假如id是10位，並且我們只用數字，那麼布隆過濾器的長度只有10位（0123456789）,這個長度的過濾器幾乎沒法使用，容量太低，誤差率太高。即使算上大小寫字母，也只有62個，看似62很多，但是這里定死了id必須用這62個字元，而假如中間加一層hash，那id用什麼字元和我布隆過濾器用什麼字元以及過濾器的長度都可以自由指定，靈活很多。

④ 如何使用bloomfilter構建大型Java緩存系統

在如今的軟體當中，緩存是解決很多問題的一個關鍵概念。你的應用可能會進行CPU密集型運算。你當然不想讓這些運算一邊又一邊的重復執行，相反，你可以只執行一次， 把這個結果放在內存中作為緩存。有時系統的瓶頸在I/O操作上，比如你不想重復的查詢資料庫，你想把結果緩存起來，只在數據發生變化時才去數據查詢來更新緩存。
與上面的情況類似，有些場合下我們需要進行快速的查找來決定如何處理新來的請求。例如，考慮下面這種情況，你需要確認一個URL是否指向一個惡意網站，這種需求可能會有很多。如果我們把所有惡意網站的URL緩存起來，那麼會佔用很大的空間。或者另一種情況，需要確認用戶輸入的字元串是包含了美國的地名。像「華盛頓的博物館」——在這個字元串中，華盛頓是美國的一個地名。我們應該把美國所有的地名保存在內存中然後再查詢嗎？那樣的話緩存會有多大？是否能在不使用資料庫的前提下來高效地完成？
這就是為什麼我們要跨越基本的數據結構map，在更高級的數據結構像布隆過濾器（bloomfilter）中來尋找答案。你可以把布隆過濾器看做Java中的集合（collection），你可以往它裡面添加元素，查詢某個元素是否存在（就像一個HashSet）。如果布隆過濾器說沒有這個元素，那麼可以肯定不含有這個元素，但是如果布隆過濾器說有某個元素，那麼這個結果可能是錯誤的。如果我們在設計布隆過濾器時足夠細心，我們可以把這種出錯的概率控制在可接受范圍內。
解釋

布隆過濾器被設計為一個具有N的元素的位數組A（bit array），初始時所有的位都置為0.
添加元素
要添加一個元素，我們需要提供k個哈希函數。每個函數都能返回一個值，這個值必須能夠作為位數組的索引（可以通過對數組長度進行取模得到）。然後，我們把位數組在這個索引處的值設為1。例如，第一個哈希函數作用於元素I上，返回x。類似的，第二個第三個哈希函數返回y與z，那麼：
A[x]=A[y]=A[z] = 1

查找元素
查找的過程與上面的過程類似，元素將會被會被不同的哈希函數處理三次，每個哈希函數都返回一個作為位數組索引值的整數，然後我們檢測位數組在x、y與z處的值是否為1。如果有一處不為1，那麼就說明這個元素沒有被添加到這個布隆過濾器中。如果都為1，就說明這個元素在布隆過濾器裡面。當然，會有一定誤判的概率。
演算法優化
通過上面的解釋我們可以知道，如果想設計出一個好的布隆過濾器，我們必須遵循以下准則：
好的哈希函數能夠盡可能的返回寬范圍的哈希值。
位數組的大小（用m表示）非常重要：如果太小，那麼所有的位很快就都會被賦值為1，這樣就增加了誤判的幾率。
哈希函數的個數（用k表示）對索引值的均勻分配也很重要。
計算m的公式如下：
m = - nlog p / (log2)^2;

這里p為可接受的誤判率。
計算k的公式如下：
k = m/n log(2) ;

這里k=哈希函數個數，m=位數組個數，n=待檢測元素的個數（後面會用到這幾個字母）。
哈希演算法
哈希演算法是影響布隆過濾器性能的地方。我們需要選擇一個效率高但不耗時的哈希函數，在論文《更少的哈希函數，相同的性能指標：構造一個更好的布隆過濾器》中，討論了如何選用2個哈希函數來模擬k個哈希函數。首先，我們需要計算兩個哈希函數h1(x)與h2(x)。然後，我們可以用這兩個哈希函數來模仿產生k個哈希函數的效果：
gi(x) = h1(x) + ih2(x);

這里i的取值范圍是1到k的整數。
Google guava類庫使用這個技巧實現了一個布隆過濾器，哈希演算法的主要邏輯如下：

long hash64 = …; //calculate a 64 bit hash function
//split it in two halves of 32 bit hash values
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
//Generate k different hash functions with a simple loop
for (int i = 1; i <= numHashFunctions; i++) {
int nextHash = hash1 + i * hash2;
}

應用
從數學公式中，我們可以很明顯的知道使用布隆過濾器來解決問題。但是，我們需要很好地理解布隆過濾器所能解決問題的領域。像我們可以使用布隆過濾器來存放美國的所有城市，因為城市的數量是可以大概確定的，所以我們可以確定n（待檢測元素的個數）的值。根據需求來修改p（誤判概率）的值，在這種情況下，我們能夠設計出一個查詢耗時少，內存使用率高的緩存機制。
實現
Google Guava類庫有一個實現，查看這個類的構造函數，在這裡面需要設置待檢測元素的個數與誤判率。
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

//Create Bloomfilter
int expectedInsertions = ….;
double fpp = 0.03; // desired false positive probability
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charse

⑤ 布隆過濾器的優點

相比於其它的數抄據結襲構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數。另外, Hash函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
布隆過濾器可以表示全集，其它任何數據結構都不能；
k和m相同，使用同一組Hash函數的兩個布隆過濾器的交並差運算可以使用位操作進行。
布隆過濾器

⑥ 布隆過濾器的缺點

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的專元素數量增加，屬誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。
另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位列陣變成整數數組，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全的刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面. 這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。
在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

⑦ 如何用布隆過濾器去重mysql

在資料庫中創建欄位的UNIQUE屬性
在資料庫中創建一個唯一的索引，在插入數據之前檢查待插入的數據是否存在
使用Set或HashSet保存數據，確保唯一

⑧ 如何用python寫布隆過濾器

下面的是網路上找到的python的布隆過濾器的實現.

#!/usr/local/bin/python2.7
#coding=gbk
'''
Createdon2012-11-7

@author:palydawn
'''
importcmath
fromBitVectorimportBitVector

classBloomFilter(object):
def__init__(self,error_rate,elementNum):
#計算所需要的bit數
self.bit_num=-1*elementNum*cmath.log(error_rate)/(cmath.log(2.0)*cmath.log(2.0))

#四位元組對齊
self.bit_num=self.align_4byte(self.bit_num.real)

#分配內存
self.bit_array=BitVector(size=self.bit_num)

#計算hash函數個數
self.hash_num=cmath.log(2)*self.bit_num/elementNum

self.hash_num=self.hash_num.real

#向上取整
self.hash_num=int(self.hash_num)+1

#產生hash函數種子
self.hash_seeds=self.generate_hashseeds(self.hash_num)

definsert_element(self,element):
forseedinself.hash_seeds:
hash_val=self.hash_element(element,seed)
#取絕對值
hash_val=abs(hash_val)
#取模，防越界
hash_val=hash_val%self.bit_num
#設置相應的比特位
self.bit_array[hash_val]=1

#檢查元素是否存在，存在返回true，否則返回false
defis_element_exist(self,element):
forseedinself.hash_seeds:
hash_val=self.hash_element(element,seed)
#取絕對值
hash_val=abs(hash_val)
#取模，防越界
hash_val=hash_val%self.bit_num

#查看值
ifself.bit_array[hash_val]==0:
returnFalse
returnTrue

#內存對齊
defalign_4byte(self,bit_num):
num=int(bit_num/32)
num=32*(num+1)
returnnum

#產生hash函數種子,hash_num個素數
defgenerate_hashseeds(self,hash_num):
count=0
#連續兩個種子的最小差值
gap=50
#初始化hash種子為0
hash_seeds=[]
forindexinxrange(hash_num):
hash_seeds.append(0)
forindexinxrange(10,10000):
max_num=int(cmath.sqrt(1.0*index).real)
flag=1
fornuminxrange(2,max_num):
ifindex%num==0:
flag=0
break

ifflag==1:
#連續兩個hash種子的差值要大才行
ifcount>0and(index-hash_seeds[count-1])<gap:
continue
hash_seeds[count]=index
count=count+1

ifcount==hash_num:
break
returnhash_seeds

defhash_element(self,element,seed):
hash_val=1
forchinstr(element):
chval=ord(ch)
hash_val=hash_val*seed+chval
returnhash_val
'''
#測試代碼
bf=BloomFilter(0.001,1000000)
element='palydawn'
bf.insert_element(element)
printbf.is_element_exist('palydawn')'''

#其中使用了BitVector庫，python本身的二進制操作看起來很麻煩，這個就簡單多了

如果解決了您的問題請採納！
如果未解決請繼續追問

⑨ 用python安裝布隆過濾器報錯，這怎麼解決

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增回加，誤算率隨之增答加。但是如果元素數量太少，則使用散列表足矣。另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位列陣變成整數數組

⑩ 布隆過濾器既然有錯誤率，為什麼還能應用在key-value系統中

bloom filter的特點是會出現誤報，但不會漏報，也就是說對於bloom filter驗證的一個數據內文件，可能不包含容你查找的數據項，但是包含你查找的數據項的數據文件它一定是會返回的，key-value系統中bloom filter返回的數據文件還是需要查看裡面的內容才能知道是否存在所需的數據的，這就保證了執行結果的正確性和完整性。因此key-value系統不會因此而出錯的，只是多訪問一些數據文件而已。在數據量很大key-value系統中，建立統一的B+樹索引的代價是非常大的，維護成本也很高，因此綜合起來bloom filter的性能是最好的。