System and method for searching an associative memory utilizing first and second hash functions

Abstract

A system and method form searching an associative memory using input key values and first and second hashing sections. Key values (Kn) can be hashed in the first hashing section ( ) to generate first output values H (Kn) that access a first store ( ). The first store or memory portion ( ) can include “leaf” pointer entries ( - ) and “chunk pointer” entries ( - ). A leaf pointer entry ( - ) points at data associated with an applied key value. A chunk pointer entry ( - ) includes pointer data. If a chunk pointer entry ( - ) is accessed, the key value (Kn) is hashed in the second hashing section ( ) to generate second output values H (Kn) that access a second store or memory portion ( ). Second hashing section ( ) hashes key values (Kn) according to selection data SEL stored in a chunk pointer entry ( - ). The system may also include a first memory portion accessed according to address values from the first hashing section and a second memory portion accessed according to address values that include outputs from the second hash section and a chunk base address value. The hash based associative system allows for the selection of a second hash function that has been precomputed at table build time to be perfect with respect to a small set of colliding key values, provides a deterministic search time independent of the number of table entries or width of the search key, and allows for pipelining to achieve highest search throughput.