Non-blocking hashtables with open addressing
Autor: | Chris Purcell, Tim Harris |
---|---|
Rok vydání: | 2005 |
DOI: | 10.48456/tr-639 |
Popis: | We present the first non-blocking hashtable based on open addressing that provides the following benefits: it combines good cache locality, accessing a single cacheline if there are no collisions, with short straight-line code; it needs no storage overhead for pointers and memory allocator schemes, having instead an overhead of two words per bucket; it does not need to periodically reorganise or replicate the table; and it does not need garbage collection, even with arbitrary-sized keys. Open problems include resizing the table and replacing, rather than erasing, entries. The result is a highly-concurrent set algorithm that approaches or outperforms the best externally-chained implementations we tested, with fixed memory costs and no need to select or fine-tune a garbage collector or locking strategy. |
Databáze: | OpenAIRE |
Externí odkaz: |
Pro tento záznam nejsou dostupné žádné jednotky.