Patent ID: 7680806

Claim:
A method comprising: hashing a new entry with a first hash function (FHF), implemented by hardware in a forwarding engine, to generate a first FHF index to a first hash table (FHT); hashing the new entry with a second hash function (SHF), implemented by hardware in the forwarding engine, to generate a first SHF index to a second hash table (SHT), with the first and second hash tables each having a plurality of buckets identified by an index and with each bucket including a plurality of cells for holding entries where the FHF and SHF are different and uncorrelated hash functions; accessing a first FHT bucket with the first FHF index utilizing logic in the forwarding engine; accessing a first SHT bucket with the first SHF index utilizing logic in the forwarding engine; hashing a first FHT entry from a first FHT cell in the first FHT bucket of the first hash table with the second hash function to index a second SHT bucket in the second hash table if the first FHT bucket of the first hash table and the first SHT bucket of the second hash table each hold J entries, where J is a positive integer; moving only the first FHT entry to the second SHT bucket of the second hash table, utilizing logic in the forwarding engine, if the number of entries held in the second SHT bucket is less than J; and storing the new entry in the first FHT cell of the first FHT bucket of the first hash table utilizing logic in the forwarding engine.