Pipelined hash table with reduced collisions

A machine-readable medium including instructions that, when executed on a machine cause the machine to:

• receive a key associated with a packet;
• perform a hash function using the key to provide a first hash value and a second hash value;
• select a first bucket record of a plurality of bucket records based on contents of the first hash value;
• and
• provide an indication of a location of a particular entry of a an entry record of a plurality of entry records based on contents of the first bucket record and the second hash value.

A method to generate a mask for colliding hash values, comprising:

• generating a list of mask values, wherein each mask value of the list of mask values has a predetermined number of bits set;
• receiving a set of hash values;
• determining a respective count of collisions for a mask value of the list of mask values using the set of hash values;
• and
• selecting a mask value from the list of mask values having a fewest respective count of collisions.

A device to perform a pipelined hash function having plurality of memories and a processor for packet processing, comprising:

• the plurality of memories;
• and
• the processor configured to:
• receive a packet;
• provide a key based on data included in the packet;
• perform a hash function on the key to generate a hash value;
• provide a pointer to indicate a location of an entry of a particular entry record stored at a first memory of the plurality of memories based on the hash value and contents of a bucket record stored at a second memory of the plurality of memories;
• provide a hit indication in response to a match between a key value stored at the entry of the particular entry record and the key;
• and
• provide, to an output, an action stored at the particular entry of the entry record.