An apparatus comprising a storage device comprising a hash table including a plurality of buckets, each bucket being capable of storing at least one data item, 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 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.