Patent ID: 7370054

Claim:
A method for indexing a hash table which is organized as a linked list, comprising: performing a lookup in the hash table in a computer system memory; wherein the hash table is implemented using only one linked list containing data nodes and a bucket array containing bucket pointers, wherein at least one bucket pointer points to a data node that is different from the linked list's head node, and wherein the hash table is resized without re-hashing the data nodes; wherein the bucket pointers point to portions of the linked list that function as hash buckets; wherein data nodes in the linked list are organized in increasing hash key order rather than bit-reversed hash key order, thereby obviating the need for time-consuming bit-reversal operations; wherein performing the lookup involves, using a hash key to lookup a bucket pointer in the bucket array, wherein the bucket pointer points to a first data node within the linked list which is different from the linked list's head node, and wherein the bucket pointer is associated with a hash bucket, following the bucket pointer to the first data node within the linked list which precedes a second data node, wherein the second data node is within a portion of the linked list that is associated with the hash bucket, and wherein the second data node matches the hash key, searching through the linked list starting from the first data node to locate the second data node, and returning the second data node to a user.