Single Double Cuckoo Hash

A decision apparatus, comprising:

• a first memory bank, containing a first table of hash composition factors;
• a second memory bank, containing second and third hash tables of associative entries, each of the associative entries comprising a respective entry key and a respective value, the hash tables being accessible in multiple ways including a first way and a second way, the associative entries comprising single size items and double size items;
• a third memory bank containing a stash of associative entries;
• a logic pipeline, which is configured to receive a sequence of data items, and to extract a search key from each data item, and which comprises:
• a pre-hash circuit, configured to compute a first index by applying a first hash function to the search key;
• a first lookup circuit, which is coupled to read a hash composition factor from a location in the first memory bank indicated by the first index;
• a hash circuit, which is configured to compute second and third indices as different combinations, determined by the hash composition factor, of second and third hash functions applied by the hash circuit to the search key;
• a second lookup circuit, which is configured to read the associative entries in the second and third hash tables that are indicated respectively by the second and third indices, and upon finding a match between the search key and the respective entry key in an indicated entry, to output the respective value from the indicated entry;
• and
• a processor, responsively to outputs of the first lookup circuit and the second lookup circuit, configured to insert values of the hash composition factor into the first table and the associative entries into the second and third hash tables in accordance with a single size cuckoo hashing insertion procedure and a double size cuckoo hashing insertion procedure for the single size items and the double size items, respectively.

A method, comprising:

• in a first memory bank of a network element storing a plurality of hash tables of associative entries comprising a respective entry key and a respective value, the hash tables being accessible in multiple ways including a first way and a second way, the associative entries comprising single size items and double size items;
• in a second memory bank storing a stash of associative entries;
• receiving a sequence of data items;
• extracting a search key from each of the data items;
• applying first and second hash functions to the search key to generate first and second indices;
• reading the associative entries in the hash tables that are indicated respectively by the first and second indices
• matching the search key against the associative entries of the hash tables in all the ways, and upon finding a match between the search key and the respective entry key in an indicated associative entry, outputting the respective value from the indicated associative entry;
• and
• responsively to the respective value from the indicated associative entry inserting the associative entries of the stash into the hash tables in accordance with a single size cuckoo hashing insertion procedure and a double size cuckoo hashing insertion procedure for the single size items and the double size items, respectively.

A computer software product, including a non-transitory computer-readable storage medium in which computer program instructions are stored, which instructions, when executed by a computer, cause the computer to perform the steps of:

• in a first memory bank storing a plurality of hash tables of associative entries comprising a respective entry key and a respective value, the hash tables being accessible in multiple ways including a first way and a second way, the associative entries comprising single size items and double size items;
• in a second memory bank storing a stash of associative entries;
• receiving a sequence of data items;
• extracting a search key from each of the data items;
• applying first and second hash functions to the search key to generate first and second indices;
• reading the associative entries in the hash tables that are indicated respectively by the first and second indices
• matching the search key against the associative entries of the hash tables in all the ways, and upon finding a match between the search key and the respective entry key in an indicated associative entry, outputting the respective value from the indicated associative entry;
• and
• responsively to the respective value from the indicated associative entry inserting the associative entries of the stash into the hash tables in accordance with a single size cuckoo hashing insertion procedure and a double size cuckoo hashing insertion procedure for the single size items and the double size items, respectively.