Patent ID: 7483426

Claim:
A method in a look-up table for obtaining a data value associated with a key, the method comprising: providing a first table in the look-up table, each table entry in the first table being associated with a look-up address and including one or more key-data value pairs and an expansion pointer field; providing a second table in the look-up table, each table entry in the second table being associated with an expansion address and including one or more key-data value pairs; receiving an input key; applying a hash function to the input key; generating a hash value for use as a look-up address; indexing the first table in the look-up table using the look-up address; identifying a first table entry in the first table associated with the look-up address; determining if the input key matches any key in the one or more key-data value pairs in the first table entry; if a match is found, retrieving the data value associated with the input key; if a match is not found, retrieving a first expansion pointer in the expansion pointer field associated with the first table entry; indexing the second table in the look-up table using the first expansion pointer; identifying a second table entry in the second table associated with the first expansion pointer; and determining if the input key matches any key in the one or more key-data pairs in the second table entry.