Hash table storing reduced search key
View Patent ↗Some embodiments of the invention provide a novel hash table storage that stores smaller portions of the search keys (called reduced search keys), which, in turn allows the storage to have a smaller size and/or to store more search keys. The stored portions of search keys (i.e., the reduced search keys) can be smaller than the search keys because the hash table storage uses the non-stored portions of the search keys to ensure that one storage location cannot be used for two search keys that have the same stored portions but different non-stored portions. For instance, in some embodiments, the storage stores W minus B bits of a search key, where W is the size of the search key and B is the number of search-key bits that the storage uses to ensure that the same storage location is not identified for two search keys that have the same W-B stored bits but different B bits.
1. For hash table that stores a plurality of W-B bit reduced search keys (RSKs) that are associated with a plurality of W-bit search keys, a method of processing a particular search key, the method comprising
generating a B-bit hash address value from the particular search key by using a field matrix that produces a B-bit address value for a W-bit search key, wherein the field matrix comprises a B-by-B sub-matrix that has B linearly independent rows;
outputting an RSK that is stored in the hash table at the generated hash address value, each RSK having a smaller size than the RSK's associated search key, wherein (i) the hash table is a B-bit addressable memory that can store 2 B possible RSKs, (ii) each possible B-bit value translates to only one of the 2 B possible values, and (iii) each one of the 2 B possible values translates to only one possible B-bit value;
comparing the output RSK with an RSK that is extracted from the particular search key to determine whether the two RSKs match; and
when the two RSKs match, outputting data to indicate that the hash table has a record related to the particular search key.
2. The method of claim 1 ,
wherein the generated hash address value is collision free over B bits of each W-bit search key.
3. The method of claim 1 , wherein with each RSK, the hash table stores a set of other bits.
4. The method of claim 3 , wherein the set of other bits includes one validity bit that specifies whether the RSK is valid.
5. The method of claim 3 , wherein the set of other bits includes payload data.
6. The method of claim 1 , wherein the outputted data includes an address in a memory that stores a data tuple that is associated with the outputted RSK.
7. The method of claim 6 , wherein the outputted data further includes a hash table hit value.
8. The method of claim 1 , wherein the outputted data includes a data tuple that the hash table stores for the outputted RSK.
9. The method of claim 1 further comprising retrieving from a memory a data tuple that is stored at the generated address when the outputted data is a hash table hit value.
10. The method of claim 1 further comprising:
when the outputted data is a hash table hit value,
generating another address value from the particular search key;
retrieving from a memory a data tuple that is stored at the other generated address value.
11. The method of claim 1 further comprising when the two RSKs do not match, outputting a hash table miss value.
12. A hash table storage comprising:
a hash generator for producing address values from search keys, wherein (i) the hash generator comprises a field matrix that produces a B-bit address value for a W-bit search key and (ii) the field matrix comprises a B-by-B sub-matrix that has B linearly independent rows; and
a hash memory for (i) storing a plurality of reduced search keys (RSKs) at a plurality of locations that are identifiable based on a plurality of address values, and (ii) outputting a particular RSK for a particular address value that the hash generator produces for a particular search key, each RSK having a smaller size than each search key, wherein the hash memory is a B-bit addressable memory that can store 2 B possible RSKs, each possible B-bit value translates to only one of the 2 B possible values, and each one of the 2 B possible values translates to only one possible B-bit value; and
a comparator for comparing the particular RSK with an RSK that is extracted from the particular search key to determine whether the two RSKs match;
when the two RSKs match, the comparator outputting data to indicate that the hash memory has a record related to the particular search key.
13. The hash table storage of claim 12 further comprising
a second memory for (i) storing a plurality of data tuples for the plurality of reduced search keys stored in the first memory and (ii) outputting a particular data tuple for the particular reduced search key that the first memory outputs when the reduced search matches a corresponding portion of the particular search key.
14. The hash table storage of claim 12 , wherein
each address value is B bits,
each search key is W bits, and
each reduced search key is W-B bits.