what is storing data in constant space?

Question

"bloom filter allows us to store data in constant space"

Can someone explain what exactly does that sentence means?

Answer 1

That statement is kinda true, but not really. A Bloom Filter is a data structure that is useful for storing multiple hashes. Generally, you would implement it as an array of bits or ints where each cell in the array maps to a bit position in the binary representation of an integer -- usually, a hash. To see if the hash that you are looking for is stored in the Filter, you look to see if all of its bits are set. There is always a possibility that you will get a false positive, of course, so the use to which you put the Bloom Filter has to be tolerant of that possibility.

The Bloom Filter is always the same size, no matter how many hashes you set in it, but the probability of False Positives increases, too, so its usefulness degrades.

A Bloom Filter isn't a magical bucket into which you can throw as much data as you want and it never gets any bigger. That is called a Bag of Holding and you have to go to a place called Greyhawk to find one.

EDIT: So, a Bloom Filter is an array of bits. When it is new, it will be full of zeros. To add a hash to it, you compute the binary value of that hash and then OR it with the Bloom Filter

0000000000000000 BF start
0010011010010010 Hash that I want to add

0010011010010010 BF state
1001010001010011 Hash that I want to add

1011011011010011 BF state

Now, to test to see if a given hash has been added to the Bloom Filter, I turn it into a binary number and check that each set bit is also set in the BF:

1011011011010011 BF state
0100100100100010 Hash that I am testing
                 Negative! Hash has not been added to the BF

However, false positive are possible:

1011011011010011 BF state
1011011011010011 Hash that I am testing
                 False Positive! Hash checks out, but I never added that value.

This example appears trivial because the filter has only 16 bits, and this is a very simplified version of a Bloom Filter, but the principle is understandable, I hope.

Does that answer your question @Timothy?

Answer 2

I'm not sure about bloom filters, or even the validity of that statement, but I know that in general, "constant space" means that N amount of data requires the same amount of space, no matter what N is.

So, when your source says "a bloom filter allows us to store data in constant space", it means that no matter how much data you have, it will always take the same amount of memory to store it.

An example would be MD5 hashes. An MD5 digest will always contain 128 bits, no matter if you give the hashing algorithm a single character, or all of Wikipedia.

This is similar (and related) to algorithm complexity - looking up a value in a hashmap is always O(1) - constant time, meaning no matter how big the hashmap is, it will always take the same amount of time to find the hash.