Exact match hash lookup databases in network switch devices

摘要

In a method for populating a forwarding table, a first hash function is applied to a lookup key to generate a first hash value, a second hash function is applied to the lookup key to generate a second hash value, and a third hash function is applied to the lookup key to generate a third hash value. An offset is determined based on the first hash value and the second hash value. A location for inserting the lookup key is determined based on the offset and the third hash value. It is determined whether the lookup key can be inserted into the forwarding table at the determined location without colliding with a key previously stored at the determined location. When it is determined that the lookup key can be inserted, the lookup key and forwarding information associated with the lookup key are inserted at the determined location.