Patent ID: 8572140

Claim:
A hashed lookup method comprising: hashing an input lookup key to generate a hashed key; dividing the hashed key into a plurality of strides including a first stride and a second stride; using the first stride to locate a first entry in a first-level stride table; locating a second entry in a second-level stride table using a table pointer in the first entry and the second stride; locating entries in additional stride tables based on the strides in the hashed key; locating a first bucket table using a first final pointer in a final entry; reading first discriminant bits from the input lookup key at bit-positions indicated by a first discriminant bit-position field in the final entry; locating a selected first entry in the first bucket table using the first discriminant bits as an index into the first bucket table; determining that a stored key in the selected first entry matches the input lookup key; and returning a lookup result stored in or pointed to by the selected first entry.