Most efficient way to check if key exist on a table Imagine a person called Albert. Albert lives in Europe and would love to move to America. One day he got his wish come true. A person called Margareta gave him a key. The value of the key is the same as the address for a house in USA. Albert doesn't have that much money to travel to America to confirm whether the key is a hoax or not, by going to the address of the key. He certainly doesn't have the money for a house in America. If the key turns out to be a hoax, Albert would have a very hard time to make a living in America. It would cost him dearly. One day, a postman who knew all the addresses in America visited Europe. He happened to meet Albert. 

Can the postman carry a certain information that is less than the information of all addresses in America to confirm whether Albert's key is valid or not? Then what is the information and what kind of operations is made to make the confirmation? 

Assume all information is numeric here. 

Background:
I was looking at implementing a hash table for already known keys and I was wondering whether there exists efficient lookups where I don't have to visit a bucket in a hash table(America) to confirm whether a key exist or not.
Using Bloom filters you can store membership of $n$ elements using approximately $-1.44\cdot\log_2(p)\cdot n$ bits, where $p$ is your probability of a false positive (it does not have false negatives).

This is assuming you have perfect independent hash functions (which is a reasonable enough assumption).

So if Albert wants an 0.1% chance of wasting his time the postman needs to carry $\approx 14.4$ bits of information per address, which is definitely less than the amount of bits to uniquely store an address.