Computer Laboratory

Technical reports

Non-blocking hashtables with open addressing

Chris Purcell, Tim Harris

September 2005, 23 pages

Abstract

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.

Full text

PDF (0.3 MB)

BibTeX record

@TechReport{UCAM-CL-TR-639,
  author =	 {Purcell, Chris and Harris, Tim},
  title = 	 {{Non-blocking hashtables with open addressing}},
  year = 	 2005,
  month = 	 sep,
  url = 	 {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-639.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-639}
}