算法技术手册（原书第2 版）

114

｜

第

5

章

The only reason to use a Bloom Filter is that it has a predicable false positive rate,

p

k

, assuming the k hash functions are uniformly random (Bloom, 1970). A reasona‐

bly accurate computation for p

k

is:

p

k

=

1 − 1 −

1

m

kn

k

2

where n is the number of values already added (Bose et al., 2008). We empirically

computed the false positive rate as follows:

1. Randomly remove 2,135 words from the list of 213,557 words (1% of the full

list) and insert the remaining 211,422 words into a Bloom Filter.

2. Count the false positives when searching for the missing 2,135 words.

3. Count the false positives when searching for 2,135 random strings (of between

2 and ...