Hopscotch Hashing Export

@inproceedings{citeulike:3906072, abstract = {We present a new class of resizable sequential and concurrent hash map algorithms directed at both uni-processor and multicore machines. The new hopscotch algorithms are based on a novel hopscotch multi-phased probing and displacement technique that has the flavors of chaining, cuckoo hashing, and linear probing, all put together, yet avoids the limitations and overheads of these former approaches. The resulting algorithms provide tables with very low synchronization overheads and high cache hit ratios.}, address = {Berlin, Heidelberg}, author = {Herlihy, Maurice and Shavit, Nir and Tzafrir, Moran}, booktitle = {DISC '08: Proceedings of the 22nd international symposium on Distributed Computing}, citeulike-article-id = {3906072}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1432316}, citeulike-linkout-1 = {http://dx.doi.org/10.1007/978-3-540-87779-0_24}, citeulike-linkout-2 = {http://www.springerlink.com/content/u710121187m65436}, comment = {http://groups.google.com/group/hopscotch-hashing}, doi = {10.1007/978-3-540-87779-0_24}, isbn = {978-3-540-87778-3}, keywords = {cache\_consicious, concurrent, hashtable}, location = {Arcachon, France}, pages = {350--364}, posted-at = {2009-03-09 17:01:28}, priority = {2}, publisher = {Springer-Verlag}, title = {Hopscotch Hashing}, url = {http://dx.doi.org/10.1007/978-3-540-87779-0_24}, year = {2008} }

TY - CONF ID - citeulike:3906072 L3 - citeulike-article-id:3906072 N2 - We present a new class of resizable sequential and concurrent hash map algorithms directed at both uni-processor and multicore machines. The new hopscotch algorithms are based on a novel hopscotch multi-phased probing and displacement technique that has the flavors of chaining, cuckoo hashing, and linear probing, all put together, yet avoids the limitations and overheads of these former approaches. The resulting algorithms provide tables with very low synchronization overheads and high cache hit ratios. CY - Arcachon, France SN - 978-3-540-87778-3 AD - Berlin, Heidelberg EP - 364 TI - Hopscotch Hashing PB - Springer-Verlag T2 - DISC '08: Proceedings of the 22nd international symposium on Distributed Computing SP - 350 KW - cache_consicious KW - concurrent KW - hashtable N1 - http://groups.google.com/group/hopscotch-hashing AU - Herlihy, Maurice AU - Shavit, Nir AU - Tzafrir, Moran PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-87779-0_24 ER -