2 Jun
2008
2 Jun
'08
3:25 p.m.
On Sat, May 31, 2008 at 6:22 PM, Jim Snow
In practice, one might use something like 32 hash tables. This yields a false positive rate of 1/(2^32). Their most obvious application is to store the dictionary for a spell checker in a space-efficient way, though I have a friend who wrote a paper on using them for router caches.
One minor technicality is that you don't actually use k separate hash tables. You use k separate hash functions, and hash using different functions into the same physical table with a goal of having approximately half of the bits in the table set when all of your data is hashed.