Patent ID: 7702628

Claim:
A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing operations on a hash table that is fully dynamic and lock-free, the method comprising: performing a lookup in the hash table; wherein the hash table is stored in a computer system memory; wherein the hash table is implemented as a single linked list that includes a head node at the beginning of the single linked list, a set of data nodes, and a bucket array containing a set of bucket pointers wherein the set of bucket pointers point to respective portions of the single linked list that function as hash buckets, such that each bucket pointer except a first bucket pointer in the bucket array points at a data node immediately preceding the first data node in the corresponding portion of the single linked list, whereas the first bucket pointer points at the head node of the single linked list; wherein the single linked list contains only data nodes and the head node without using dummy nodes at the starts of the corresponding portions of the single linked list, wherein a dummy does not contain data; and wherein performing the lookup involves, using a hash key to lookup a bucket pointer in the bucket array, following the bucket pointer to a data node (or the head node) within the single linked list that precedes nodes in an associated hash bucket; searching through the single linked list from the data node to locate a node that matches the hash key; returning the located data node from the computer system memory if one exists; and reporting the data node is missing if one does not exist.