Electrical computers and digital processing systems: memory – Address formation – Hashing
Patent
1998-03-03
2000-09-05
Chan, Eddie P.
Electrical computers and digital processing systems: memory
Address formation
Hashing
707 1, 707200, G06F 1200
Patent
active
06115802&
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.
REFERENCES:
patent: 4996663 (1991-02-01), Nemes
patent: 5109511 (1992-04-01), Nitta et al.
patent: 5121495 (1992-06-01), Nemes
patent: 5287499 (1994-02-01), Nemes
patent: 5339398 (1994-08-01), Shah et al.
patent: 5495609 (1996-02-01), Scott
Tock Theron D.
Wong Thomas K.
Chan Eddie P.
Sun Mircrosystems, Inc.
Verbrugge Kevin
LandOfFree
Efficient hash table for use in multi-threaded environments does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient hash table for use in multi-threaded environments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient hash table for use in multi-threaded environments will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2223508