Answer the question
In order to leave comments, you need to log in
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
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 remainsince collisions remain, then there is still uncertainty
2 higher bit density 1 to 1How does this relate to the problem at hand?
3 calculation of only one hash functioncalculating 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 questionAsk a Question
731 491 924 answers to any question