Efficient hash table for use in multi-threaded environments
US6115802A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Mar 3, 1998 |
| Grant date | Sep 5, 2000 |
| Priority date | — |
| Expiry date | Mar 3, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99931
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 determi…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.