Exact match lookup in network switch devices

摘要

In a method for populating a lookup table, a plurality of hash tables are provided. Each hash table is accessed by a respective hash function. A plurality of hashed values for a key are generated using the hash functions corresponding to the plurality of hash tables. The plurality of hashed values are used to determine whether the key can be inserted into one or more hash tables of the plurality of hash tables without colliding with keys previously stored at respective locations corresponding to the determined hashed values. When it is determined that the key can be inserted into multiple hash tables, it is then determined which one of the multiple hash tables is populated with the greatest number of keys. The hash table that is populated with the greatest number of keys is selected for insertion of the key, and the key is inserted into the selected hash table.

主权项

1. A method for populating a lookup table, the method comprising:
providing a plurality of hash tables, wherein each hash table in the plurality of hash tables is accessed by a respective hash function; generating a plurality of hashed values for a key using the hash functions corresponding to the plurality of hash tables; using the plurality of hashed values to determine whether the key can be inserted into one or more hash tables of the plurality of hash tables without colliding with keys previously stored at respective memory locations corresponding to the determined hashed values; when it is determined that the key can be inserted into multiple hash tables, determining which one of the multiple hash tables is populated with the greatest number of keys; selecting the hash table that is populated with the greatest number of keys; and inserting the key into the selected hash table.