Efficient hash table for use in multi-threaded environments

Abstract

A lockless-lookup hash table for use in a multi-threaded processing system has a memory whose storage locations hold elements. Each memory location is uniquely identified by an index value, and each element includes a key and a value. The target location for storing an input value is determined by generating a hash value from an input key value, and probing storage locations, beginning at the one designated by the generated hash value, until an empty location is found. In accordance with one aspect of the invention, the hash table may be used as a commonly accessed resource in a multi-threaded environment without requiring locks associated with lookup operations. In such environments, incorrect results may be tolerated, so long as the lookup operation is guaranteed never to return a value that had never been stored into the table by one of the threads in the system. This characteristic is provided in the present invention by an insert operation that never writes the value portion of the element into a location last. Instead, the last thing stored by an insert operation is the key, or alternatively any other portion of the element that is utilized by the lookup operation for determining whether a sought-after element has been located. Other aspects of the invention relate to optimizing performance of the hash table during lookup and delete operations, and to reducing the number of erroneous results produced when lockless-lookup operations proceed in a multi-threaded environment.