# What degree of hash function independence is needed for Bloom filters?

In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each other key. This contrasts with the sorts of analyses that I've seen done elsewhere. For example, both the count sketch and count-min sketch only require 2-independent hash functions, as does a hash table that resolves collisions via chaining. (However, linear probing hash tables require 5-independence).

Has there been any work done into analyzing Bloom filters under the assumption that the hash functions used are, say, only $$k$$-independent? Or are any lower bounds known on the degree of independence required for Bloom filters to provide reasonable guarantees about false positives?

• A cursory Google search reveals several papers on Bloom filters and hashing with limited independence. Apr 28, 2019 at 20:18
• @ChandraChekuri Perhaps I'm missing something, but the first page of Google search results doesn't seem to have anything along these lines popping up. There are lots of hits talking about having several independent hash functions, but that's separate from the strengths of those hash functions. That said, if I'm searching for the wrong term or simply misread what I'm looking at, please let me know! Apr 28, 2019 at 20:42
• See Propositions 3.9 and 3.10 in eecs.harvard.edu/~michaelm/postscripts/soda2008b.pdf May 1, 2019 at 7:41