page_title: Concurrent hash table
section_title: Phase concurrency
hierarchical_section_title: Concurrent hash table / Contention handling / Phase concurrency
context_page_description: A concurrent hash table is an implementation of hash tables allowing concurrent access by multiple threads using a hash function.
  Concurrent hash tables thus 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.
  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. There exist multiple solutions to mitigate the effects of contention, that each preserve the correctness of operations on the table.
  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.
context_section_description: A phase concurrent hash table groups accesses by creating phases in which only one type of operation is allowed (i.e. a pure write-phase), followed by a synchronization of the table state across all threads. A formally proven algorithm for this is given by Shun and Blelloch.
caption: Concurrent accesses grouped into distinct phases.