Hash tables, also known as unordered associative maps, are efficient data structures that should be discussed as part of any introductory data structures course or book.Given the importance of parallel programming these days, understanding how to have efficient concurrent use of our data structures is especially relevant.
Intel Threading Building Blocks (TBB) has been a key source for a highly concurrent hash table for this past decade. The TBB open source project’s home is https://www.threadingbuildingblocks.org.
Concurrency and Hash Tables
Like any data structure, when used with parallel programming we need to consider issues related to concurrent access. A simple solution with any data structure is to forbid concurrent access. This is done by having some form of mutual exclusion (usually done with a “lock,” commonly known as a “mutex”). The problem with mutual exclusion is that it tends to limit performance in a parallel program, because it leads to stalling if the data structure is heavily used. Therefore, we need something better than the simple solution.