Patent ID: 7287131

Claim:
A method for using a hash table that is fully dynamic and lock-free, comprising: performing a lookup into the hash table, wherein the lookup involves, using a hash key to lookup a bucket pointer in a bucket array, following the bucket pointer to a data node within a linked list containing all of the data nodes in the hash table, and searching from the data node through the linked list to locate a node that matches the hash key if one exists; wherein the linked list contains only data nodes and at most a constant number of dummy nodes; and when the average number of data nodes in each bucket exceeds a maximum value: increasing the number of buckets in the bucket array to form a larger bucket array, and using more bits from the hash key to perform lookups in the larger bucket array, wherein the data nodes are stored in the linked list in bit-inverted hash key order, and wherein increasing the number of buckets in the bucket array involves copying the existing bucket array into the top half of the larger bucket array through a single pointer operation.