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.