Word-Aligned Bloom Filters
Oh, that&#x27;s elegant.<p>If I math right, setting 5 bits in a 64-bit word extends the effective length of the hash function by approximately (5-1) * log_2(64) = (5-1) * 6 = 24 bits. In a simple bloom filter of storage size <i>m</i> bits, the hash functions have length log_2(m). All else being equal, the number of hash functions used -- hence the number of memory reads per lookup -- gets reduced by a factor of log_2(m) &#x2F; [24 + log_2(m)].<p>(But it&#x27;s not exactly equal; the storage size <i>m</i> has to go up by a factor of 1.2 (in the OP parameter set), for constant false-positive rate).