Concurrent hash table

Concurrent accesses to the same hash table.

A concurrent hash table or concurrent hash map is an implementation of hash tables allowing concurrent access by multiple threads using a hash function.[1][2]

Concurrent hash tables represent a key concurrent data structure for use in concurrent computing which allow multiple threads to more efficiently cooperate for a computation among shared data.[1]

Due to the natural problems associated with concurrent access - namely contention - the way and scope in which the table can be concurrently accessed differs depending on the implementation. Furthermore, the resulting speed up might not be linear with the amount of threads used as contention needs to be resolved, producing processing overhead.[1] There exist multiple solutions to mitigate the effects of contention, that each preserve the correctness of operations on the table.[1][2][3][4]

As with their sequential counterpart, concurrent hash tables can be generalized and extended to fit broader applications, such as allowing more complex data types to be used for keys and values. These generalizations can however negatively impact performance and should thus be chosen in accordance to the requirements of the application.[1]

  1. ^ a b c d e Maier, Tobias; Sanders, Peter; Dementiev, Roman (March 2019). "Concurrent Hash Tables: Fast and General(?)!". ACM Transactions on Parallel Computing. 5 (4). New York, NY, USA: ACM. Article 16. doi:10.1145/3309206. ISSN 2329-4949. S2CID 67870641.
  2. ^ a b Shun, Julian; Blelloch, Guy E. (2014). "Phase-concurrent Hash Tables for Determinism". SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures. New York: ACM. pp. 96–107. doi:10.1145/2612669.2612687. ISBN 978-1-4503-2821-0.
  3. ^ Li, Xiaozhou; Andersen, David G.; Kaminsky, Michael; Freedman, Michael J. (2014). "Algorithmic Improvements for Fast Concurrent Cuckoo Hashing". Proceedings of the Ninth European Conference on Computer Systems. EuroSys '14. New York: ACM. Article No. 27. doi:10.1145/2592798.2592820. ISBN 978-1-4503-2704-6.
  4. ^ Triplett, Josh; McKenney, Paul E.; Walpole, Jonathan (2011). "Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming". USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference. Berkeley, CA: USENIX Association. p. 11.