Method and apparatus for reordering entries in a multi probe lookup

摘要

A multi-probe lookup table includes an indication of the congestion level of each addressable location. A key can be stored in one of a plurality of indexed locations in the lookup table. Thrashing is reduced by inserting keys into the lookup table based on the distribution of keys already stored in the lookup table. Insert operations for all keys sharing an indexed location are recorded by modifying a swap count indicating the congestion level of the indexed location each time a key is inserted in one of the indexed locations.