US Patent 10067967 Hash table storing reduced search key

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.