Patent ID: 7043494

Claim:
A look-up method comprising: providing a data structure comprising: (a) a hash table containing up to H cells, each one of said cells having a cell type indicator containing one of a first cell type value and a second cell type value; and (b) an overflow bucket table containing up to B max buckets; wherein: (i) any one of said cells containing said first cell type value in said cell type indicator further comprises: (1) k key storage fields, each one of said k key storage fields for storing one of said keys; (2) k flow index fields, each one of said k flow index fields for storing flow index information for a key stored in a corresponding one of said k key storage fields; (ii) any one of said cells containing said second cell type value in said cell type indicator further comprises: (1) n-1 key bit position fields, each one of said key bit position fields for storing a bit position value representative of a bit position in any one of said keys; (2) n bucket index fields, each one of said bucket index fields for storing an index value representative of an address displacement of a corresponding one of said buckets within said overflow bucket table; (iii) any one of said buckets further comprises: (1) m key storage fields, each one of said m key storage fields for storing one of said keys; (2) m flow index fields, each one of said m flow index fields for storing flow index information for a key stored in a corresponding one of said m key storage fields; (iv) any particular one of said cells having said second cell type value in said type field corresponds to up to n of said buckets organized in a trie having up to n-1 intermediate nodes and up to n leaf nodes, each one of said intermediate nodes corresponding to one of said key bit position fields of said particular one of said cells, said bit position value stored in said corresponding one of said key bit position fields for selecting a binary digit at a corresponding bit position in any one of said keys, said binary digit for determining a branch direction at said intermediate node corresponding to said one of said key bit position fields; (v) each one of said up to n of said buckets organized in said trie corresponds to one of said leaf nodes; and, (vi) H, k, B max , n and m are integers, and determining whether said data structure contains a key which exactly matches an input key K.