Concurrent hash 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.

Such a strategy requires managing accesses in a way such that conflicts caused by them do not result in corrupt data, while ideally increasing their efficiency when used in parallel.

A concurrent growing algorithm is described by Maier et al.[1] Mega-KV[7] is a high performance key-value store system, where the cuckoo hashing is used and the KV indexing is massively parallelized in batch mode by GPU.

With further optimizations of GPU acceleration by Nvidia and Oak Ridge National Lab, Mega-KV was pushed to another high record of the throughput in 2018 (up to 888 millions of key-value operations per second).

Operations such as compare-and-swap often present limitations as to what size of data they can handle, meaning that the types of keys and values of a table have to be chosen or converted accordingly.

This can however lead to negative performance impacts,[1][6] in particular when the locks used are too restrictive, thus blocking accesses that would otherwise not contend and could execute without causing any problems.

[3] Maier et al.[1] perform a thorough analysis on a variety of concurrent hash table implementations, giving insight into the effectiveness of each in different situations that are likely to occur in real use-cases.

Ultimately the resulting performance of a concurrent hash table depends on a variety of factors based upon its desired application.