Patent ID: 7809701

Claim:
A method of performing exact match searches using multiple hash tables, comprising the steps of: searching in the same hash table, all keys K that it can collide with in a base (first) hash function H 0 ( ); wherein the step of searching for key K further comprises the steps of: computing I 0 =H 0 (K); fetching T=index_tbl[I 0 ]; if T=EMPTY, stopping the search as K is not in the search database, otherwise, computing I T =H T (K); fetching P=hash_tb1[offset(T)+I T ]; and comparing the key value stored in the key_tbl entry at address P to K and if they do not match, stopping, otherwise, extracting the results pointer; storing in the same hash table, all keys that it can collide with in the base (first) hash function H 0 ( ), inserting key K into a search database; when inserting a new key into the search database, using a table_id field in each entry of the base hash table to indicate which of the M hash tables a particular search key can be stored in; computing the base hash function for key K, I 0 =H 0 (K); checking the table_id field value j in the base hash table at index I 0 , j ⊂T 0 [I 0 ]; computing the jth hash function I j =H j (K) (assuming j≠0); comparing the key stored (directly or indirectly) at T j [I j ]; and deleting key K.