"bloom filter allows us to store data in constant space"
Can someone explain what exactly does that sentence means?
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
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:
However, false positive are possible:
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?
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