# Bloom filter and perfect hashing

A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position.

To mitigate the effect of hash collision, multiple functions are used, yielding probabilistic bound if using universal hash.

We can use 10 bits per elements to have 'reasonable' error rate.

If we could directly build a perfect hash function for the set $S + \infty$, where the last element is one not present in $S$, then we could use only 1 bit per element and have perfect recovery.

What are the fundamental reasons why this reasoning is wrong ?

• How large is $S$ and why is 10 bits "reasonable"? – Pål GD Jun 4 '13 at 11:17
• Why would S size come into play ? I might be missing something. – nicolas Jun 4 '13 at 12:29
• Why do you think something is wrong with your reasoning? – JeffE Jun 6 '13 at 0:27
• @JeffE It would be strange to find a huge space saving when bloom filter recognised quality is its parsimony. that said, they rely on universal hash functions so this might not be surprising. I guess to the extreme case the length of the program needed to describe the hash would itself has some kolmogorov (?) bound that limit the effectiveness. similarly, if we found a function that hashed "better" this would probably come provably at some program space cost that offset the gains. but I don't know any of this, hence my question... – nicolas Jun 6 '13 at 14:56
• Your reasoning is perfectly sound. You can get perfect recover using only one bit per element with a perfect hash function. The resulting data structure would be completely useless, because a perfect hash function would take too long to evaluate, but it would save a lot of space! – JeffE Jun 7 '13 at 3:03

The PHFs I know return some answer for any key you apply them to. If the key you supplied is not in your hash set, some value is still supplied. This is fine if you are storing all of the keys that are in your set somewhere and the PHF just gives a pointer, or if you're only using the PHF to look up satellite data of size $O(1)$ on keys you happen to know to be in your structure. However, membership testing is harder.
In particular, storing $n$ distinct elements without error requires $n \log_2 n$ bits of storage.