Patent ID: 7827218
Filing Date: 2010-11-02
Classification: G06F

Abstract:
1. A hashed lookup table structure comprising: hardware gates or a processor for executing a lookup operation; a memory for storing data used by the lookup operation; input means for receiving an input key for the lookup operation; key hashing means, receiving the input key, for generating a hashed key that is a compressed hash of the input key; stride table means for locating a final-level entry using strides of bits from the hashed key to index stride tables arranged in multiple levels; a first bucket pointer stored in the final-level entry; a first discriminant bit-position locator stored in the final-level entry; a plurality of bucket tables, each bucket table for storing a plurality of key entries, each key entry for storing a stored key and a result pointer; bucket locator means, receiving the first bucket pointer from the final-level entry, for locating a selected bucket table in the plurality of bucket tables using the first bucket pointer; key-select-bit locator means for locating and reading a key-select bit in the input key located at a bit-position within the input key indicated by the first discriminant bit-position locator stored in the final-level entry; bucket index means for selecting a selected key entry in the selected bucket table pointed to by the first bucket pointer, the bucket index means reading a state of the key-select bit read from the input key by the key-select-bit locator means to determine which key entry in the selected bucket table to select as the selected key entry; and verify means for comparing a selected stored key in the selected key entry to the input key, and for outputting a lookup result generated from a selected result pointer associated with the selected stored key when a match occurs, whereby the selected stored key is indexed using the key-select bit within the selected bucket table pointed to by the final-level entry of the stride tables.