P
P
polar_winter2018-02-25 02:49:16
Algorithms
polar_winter, 2018-02-25 02:49:16

Why is a Bloom filter needed?

Why is a Bloom filter needed?
What are the advantages of the Bloom filter over such a solution?
1 We start a hash table in slow memory.
2 For each possible hash value, set the corresponding bit in the array of bits in fast memory.
3 1 - there is an element, 0 - there is no element.
Advantages of this solution over the Bloom filter:
1 no uncertainty, but collisions also remain
2 higher bit density 1 to 1
3 calculation of only one hash function
I see no disadvantages.
So why do you need a Bloom filter?
What are the advantages of the Bloom filter over such a solution?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
D
Dmitry Belyaev, 2018-02-25
@polar_winter

advantage in size, the Bloom filter can have an array of bits of an arbitrary size, but the solution you proposed will have an array of bits directly dependent on the size of the hash, for example, crc32 will need 512MB
This is a lot for a structure that does not say anything other than the presence

1 lack of uncertainty, but collisions also remain
since collisions remain, then there is still uncertainty
2 higher bit density 1 to 1
How does this relate to the problem at hand?
3 calculation of only one hash function
calculating 10-15 hashes will be faster than calculating one + reading from a random access disk. And yes, you will have to read the bitmap from the disk, because not a single admin will give so much RAM for the task being solved

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question