Bloom filter（布隆過濾器）和普通hash表對於碰撞和存儲空間的不同？

01-29

我的理解
1.普通hash表可以生成一個類似快照的數字記錄在一個大表中，可以利用數組下標的方式，方便匹配；
2.布隆過濾也是利用多張hash表，形成一個類似網的多張hash表形成的組來匹配；
請問這與用一張普通hash表（我的理解是一維的），與使用多張hash表的布隆演算法對比，可以從存儲空間和碰撞率分析一下嗎？最好加上通俗易懂的推導公式哈~謝謝。
由布隆過濾器(Bloom Filter)詳解也可以看出布隆中hash表的個數k由表長m與總元素個數n決定。難道說布隆過濾相對hash表其實也只是「將一個大hash表拆成多個小hahs表，方便計算機運算」這樣的優點。

不好意思，之前想表達的是如普通hash，也可以用一個md5表達一個點。應該想了解的是：普通hash表，和布隆過濾的不同
--3.3更新--
我覺得是不是可以這麼來計算：
【以下來自布隆過濾器(Bloom Filter)詳解】
假設 Hash 函數以等概率條件選擇並設置 Bit Array 中的某一位，m 是該位數組的大小，k 是 Hash 函數的個數，那麼位數組中某一特定的位在進行元素插入時的 Hash 操作中沒有被置位的概率是：
$1-frac{1}{m}$
如果我們插入了 n 個元素，那麼某一位仍然為 "0" 的概率是：
$(1-frac{1}{m} )^{kn}$ &<1&>
那麼同理，如果僅僅用一個Hash表，假定我們使用與上面同樣大小的空間，即為一個k*m大小的hash，對應的概率應該是：

沒有被置位的概率：
$1-frac{1}{km}$
重複了n個元素後為：
$(1-frac{1}{km} )^{n}$ &<2&>
如上，比較&<1&>和&<2&>兩個值的大小即可。
但是高數還給大學語文老師的我不知道怎麼算了，求教~

原理是：把哈希值 n 映射到 2**n, 那麼做邏輯或就很少會碰撞了。

不過一般 bloom filter 里說的哈希函數值域為 0和1，那麼你算個 SHA256 就可以得到 256 個哈希函數啦

你說的不是「hash表」而是hash摘要演算法，像crc，md5這種，相當於將較長內容轉換為一個數字，用來做這個內容的標識，可能有碰撞但是概率能控制在可接受的範圍

bloom filter是用來判斷一個元素是否屬於一個集合，但不要求100%準確，比如用一個長度為N的bitmap，然後所有元素都會被轉換成0~N-1的值，若值在集合，則對應bit位為1，於是若一個元素落在bit中為0的位置，則「必定不在」集合中，否則「可能存在於」集合中，這時候可以去集合中具體確認一把，換句話說就是先快速把不在的過濾掉，對於剩下的用較慢的查詢確認到底在不在，如果bit為1的佔比較少且空查詢很多，就有很好的過濾效果了

題主的想法是錯誤的。

BloomFilter並不是用了比單個hash更多的空間，而是用了比單個hash更多的hash函數。

那麼現在的問題就在於：

對於一定的空間（ $m$ bits），一定的插入量（ $n$ 個元素），hash函數的個數為多少時，衝突最少？

假設：hash函數理想，且相互獨立

1個元素通過1次hash插入某個bite不被置1的概率：1- $frac{1}{m}$

1個元素通過k次hash插入某個bite不被置1的概率： $left( 1-frac{1}{m} ight) ^{k}$

n個元素通過k次hash插入某個bite不被置1的概率： $left( 1-frac{1}{m} ight) ^{kn}$

n個元素通過k次hash插入某個bite被置1的概率： $1-left( 1-frac{1}{m} ight) ^{kn}$

發生衝突的概率也即即某個元素不在已經插入的n個元素中，但經過k個hash函數求得的位置上都已經被置1的概率： $left(1-left( 1-frac{1}{m} ight) ^{kn} ight)^{k}approx left( 1-e^{-kn/m} ight) ^{k}$

可以解得： $k=frac{m}{n} ln2approx 0.7frac{m}{n}$ 時發生衝突的概率最小。

因為 $k e 1$ ，所以如果hash次數 $k$ 選取得當BloomFilter比單次hash效果好。

求解 $k$ 的過程，多謝 @高政風

補充一下，大家常用的hash表，會存儲key的值，來解決hash衝突的時候判斷value值對應哪個key的問題；標準的standard bloom filter只存儲點陣圖信息，不支持刪除操作；counting bloom filter可以支持刪除，不過佔用空間比較大，cuckoo filter支持刪除且佔用空間更少https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf；