Patent ID: 7657500
Filing Date: 2010-02-02
Classification: G06F

Abstract:
1. A method of performing concurrent cuckoo hashing on a hash table, wherein a hash table includes a number of locations that may each hold a value, wherein a plurality of processes may concurrently execute on the hash table, and wherein each process comprises a sequence of operations, the method comprising: dividing each sequence of operations into a number of phases, wherein each phase corresponds to one operation in the sequence of operations; providing an overflow buffer for each location in the hash table, wherein each overflow buffer is for holding a value displaced from its corresponding location in the hash table; concurrently executing a plurality of sequences of operations, wherein for each phase in a sequence of operations, the phase executes by: if, upon conclusion of the execution phases, any overflow buffer holds a value, repeating the execution of that phase until all overflow buffers are empty, wherein repeating execution comprises relocating an overflow buffer value to a hash table location.