Proxy hash table

A non-transitory machine readable medium storing a program that stores a data tuple that is associated with a search key in a hash-addressed memory, the program comprising sets of instructions for:

• using a first hash function to generate a first hash value from the search key;
• using the first hash value to identify an address in the hash-addressed memory;
• using a second hash function to generate a second hash value from the search key;
• and
• storing the second hash value along with the data tuple in the memory at the identified address.

A method of retrieving a data tuple from a hash-addressed memory that stored a plurality of data tuples for a plurality of search keys, the method comprising:

• from a received search key, generating a first hash value and a second hash value;
• retrieving a third hash value from the memory at an address identified by the first hash value, wherein a data tuple is stored at the identified address along with the third hash value;
• comparing the second and third hash values;
• and
• when the second and third hash values have a particular relationship with each other, outputting the data tuple from the memory.

A connection data storage for retrieving a data tuple, the data storage comprising:

• first and second hash generators for generating first and second hash values from a received search key;
• a hash-addressed memory for storing a plurality of data tuples for a plurality of search keys, and outputting a third hash value from a memory address location that is identified by the first hash value;
• and
• a comparator for comparing the second and third hash values, in order to output a data tuple that is stored in the memory at the identified address when the second and third hash values match.