Patent ID: 8880554

Claim:
An apparatus comprising: a storage device comprising a hash table including a plurality of buckets, each bucket having a plurality of entries and being capable of storing a plurality of data items; and a processor configured to: apply at least a first and a second hash function upon receiving a key to generate a first index and a second index, respectively, the first and second indices identifying first and second potential buckets in the hash table for storing a new data item associated with the key; determine whether at least one of the first and second potential buckets have space available in an empty entry to store the new data item; and responsive to determining that at least one of the first and second potential buckets have available space, insert the new data item into one of the first or second potential buckets determined to have available space, responsive to determining that at least one of the first and second potential buckets do not have available space, determining whether at least one alternative bucket has space available to store a data item currently stored in one of the first or second potential buckets, the at least one alternative bucket being selected from a first set of alternative buckets; responsive to determining that an alternative bucket has available space: moving a first data item from the first or second potential bucket to the alternative bucket; and inserting the new data item into the first or second potential bucket from which the first data item was moved; wherein responsive to determining that each of the first set of alternative buckets do not have available space to store data items currently located in the first and second potential buckets, the processor is further configured to determine whether at least one alternative bucket selected from a second set of alternative buckets has space available to store a data item currently stored in an alternative bucket determined not to have available space, and wherein responsive to determining that a first alternative bucket from the second set of alternative buckets has space available, the processor is further configured to: move a first data item from an alternative bucket determined not to have available space into the first alternative bucket; move a second data item currently stored in one of the first or second potential buckets into the alternative bucket from which the first data item was moved; and insert the new data item into the first or second potential bucket from which the second data item was moved.