| 摘要 |
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 (102) to generate first output values H1(Kn) that access a first store (104). The first store or memory portion (104) can include "leaf" pointer entries (106-2) and "chunk pointer" entries (106-3). A leaf pointer entry (106-2) points at data associated with an applied key value. A chunk pointer entry (106-3) includes pointer data. If a chunk pointer entry (106-3) is accessed, the key value (Kn) is hashed in the second hashing section (108) to generate second output values H2(Kn) that access a second store or memory portion (110). Second hashing section (108) hashes key values (Kn) according to selection data SEL stored in a chunk pointer entry (106-3). 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.
|
