4 ms·
Thanks. My only remaining point of confusion is what the 10 hash functions are doing? Does each one set one bit in your vector? Does that mean you need a has
by tocomment 16y ago
Thanks. My only remaining point of confusion is what the 10 hash functions are doing? Does each one set one bit in your vector? Does that mean you need a hash function that takes a string as input and returns 0 or 1?
- kd0amg 16y agoEach hash function indicates a bit to set. If you have an array of 2^n bits, then the hash function must return an n-bit number.
- RiderOfGiraffes 16y agoNo, each hash function tells you a bit to set. Your hash functions each take an input object and return a location in the vector. That location is set to 1. With regards how big to make things, you need to do the math. If you have a vector of 1000 bits in your vector and you have 10 hash functions then there are 1000^10 = 10^30 possible collections of ten bits that can be set. If your plausible collection is only of size a few billion then coincidences won't be common or frequent. 256 bytes is 2048 bits, 16 hash functions, suddenly there are 2048^16 possible combinations, or 2^176 which is about 10^50.
- tocomment 16y agoSo why is this an improvement over an ordinary hash table? Does having more than one hash function help in some way?
- RiderOfGiraffes 16y agoEr, I've just shown that you can store several billion records in a bit vector of length 256 bytes and you ask why it's better than a hash table? There's something that at least one of us isn't understanding ...
- jsarch 16y agoThanks for taking the time to explain this along with the 1000bits and 256bits example. I've known about bloom filters for quite some time, but never quite understood the statistics. In my area of research, sequence alignments (aka. sequence comparisons), pruning the search space is immensely important; the absence of false negatives is a huge win.