Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
Bloom filters look really great when you consider you can determine if an Int is in a set with 99% certainty in constant time. But so can hashes, with the only difference that, in a hash, most of the time you are accessing the memory only once. With bloom filters, you need to access them ~7 times per request in completely distant places, so you'd have several cache misses per request.
Am I missing something?
You are missing how the two data structures deal with hash collisions. The bloom filters do not store the actual values, so the required space is the constant size of the designated array. Instead if you use a traditional hash, it tries to store all the values you give it, so it grows with time.
Consider a simplified hash function (for the sake of an example only!) f(x) = x % 2. Now you input the following integers: 2, 3, 4, 5, 6, 7.
Standard Hash: the given values will be hashed, and we end up with a lot of collisions due to f(2) = f(4) = f(6) = 0 and f(3) = f(5) = f(7) = 1. Nevertheless, the hash stores all of these values and it will be able to tell you that 8 is not stored in it. How does it do that? It keeps track of collisions and stores all values with the same hash-value, then when you query it, it additionally compares your query. So let's query the map for 8: f(8) = 0, so it'll look into a bucket where we have already inserted 2, 4, 6 and needs to make 3 comparisons in order to tell you that 8 was not part of the input.
Bloom filter: Normally, each input value is hashed against k different hash functions. Again, for simplicity, let's just assume we only use the single hash function f. We need an array of 2 values then and when we encounter the input 2 it means that due to f(2) = 0 we set the array value at position 0 to the value 1. The same happens for 4 and 6. Similarly, the inputs 3, 5, 7 each set the array position 1 to value 1. Now we query if 8 was part of the input: f(8) = 0 and the array at position 0 is 1, so the bloom filter will falsely claim that 8 was indeed part of the input.
To get a bit more realistic, let's consider that we add a second hash function g(x) = x % 10. With that, the input value 2 leads to two hash values f(2) = 0 and g(2) = 2 and the two corresponding array positions will be set to 1. Of course, the array now should be at least of size 10. But when we query for 8 we will check the array at position 8 due to g(8) = 8, and that position will still be 0. That's why additional hash functions decrease the false positives you'll get.
Comparison: The bloom filter uses k hash functions which means up to k random array positions being accessed. But that figure is exact. The hash instead is only guaranteeing you an amortized constant access time, but may de-generate depending on the nature of your hash function and input data. So it is typically faster, except for the de-generated cases.
However, once you have a hash collision the standard hash will have to check equality of the stored values against the query value. This equality check may be arbitrarily expensive and will never occur with a bloom filter.
In terms of space, the bloom filter is constant, as there is never any need to use more memory than the designated array. On the other hand, the hash grows dynamically and may get much larger due to having to keep track of collisioned values.
Trade-off: Now that you know what is cheap and what not and under which circumstances, you should be able to see the trade-off. Bloom filters are great if you want to very quickly detect that a value has been seen previously, but can live with false positives. On the other hand, you can choose the hash map if you want guaranteed correctness at the price of not being able to exactly judge your runtime, but can accept occassionally degenerated cases which may be much slower than the average.
Similarly, if you are on a limited memory environment you may want to prefer bloom filters for their memory usage guarantee.
The use-cases for bloom filters and hashes are distinct and mostly disjoint, so direct comparison does not make sense. Besides it will depend on technical details of the implementations as there are many ways to handle hash collisions with different trade-offs.
The bloom filter can answer whether element is in a set for huge sets, with reasonable probability, but not exactly, using modest amount of memory. Huge, like, trillions of elements. But they are never exact. You can only reduce the amount of false positives by using more memory or more hash functions.
On the other hand hash tables are exact, but they need to store the set. So trillions of elements would require terrabytes of memory (and that's only american trillions). They can also store extra data for each element, which bloom filters can't.
So bloom filters are used when you have a slow method of getting data for some member (that involves querying server, reads from disk and such) of a large set (that won't fit in memory or it is impractical to transfer it to client or such) and want to avoid running the slow operation for objects that are not in the set.
khashes, you are probably havingkcache misses per read. Hash tables on the other hand guarantee that you will have your answer with 0 cache misses most of the time - collisions are rare, anyway.