1.. _concurrent_hash_map:
2
3concurrent_hash_map
4===================
5
6
7A ``concurrent_hash_map<Key, T, HashCompare >`` is a hash table that
8permits concurrent accesses. The table is a map from a key to a type
9``T``. The traits type HashCompare defines how to hash a key and how to
10compare two keys.
11
12
13The following example builds a ``concurrent_hash_map`` where the keys
14are strings and the corresponding data is the number of times each
15string occurs in the array ``Data``.
16
17
18::
19
20
21   #include "oneapi/tbb/concurrent_hash_map.h"
22   #include "oneapi/tbb/blocked_range.h"
23   #include "oneapi/tbb/parallel_for.h"
24   #include <string>
25    
26
27   using namespace oneapi::tbb;
28   using namespace std;
29    
30
31   // Structure that defines hashing and comparison operations for user's type.
32   struct MyHashCompare {
33       static size_t hash( const string& x ) {
34           size_t h = 0;
35           for( const char* s = x.c_str(); *s; ++s )
36               h = (h*17)^*s;
37           return h;
38       }
39       //! True if strings are equal
40       static bool equal( const string& x, const string& y ) {
41           return x==y;
42       }
43   };
44    
45
46   // A concurrent hash table that maps strings to ints.
47   typedef concurrent_hash_map<string,int,MyHashCompare> StringTable;
48    
49
50   // Function object for counting occurrences of strings.
51   struct Tally {
52       StringTable& table;
53       Tally( StringTable& table_ ) : table(table_) {}
54       void operator()( const blocked_range<string*> range ) const {
55           for( string* p=range.begin(); p!=range.end(); ++p ) {
56               StringTable::accessor a;
57               table.insert( a, *p );
58               a->second += 1;
59           }
60       }
61   };
62    
63
64   const size_t N = 1000000;
65    
66
67   string Data[N];
68    
69
70   void CountOccurrences() {
71       // Construct empty table.
72       StringTable table;
73    
74
75       // Put occurrences into the table
76       parallel_for( blocked_range<string*>( Data, Data+N, 1000 ),
77                     Tally(table) );
78    
79
80       // Display the occurrences
81       for( StringTable::iterator i=table.begin(); i!=table.end(); ++i )
82           printf("%s %d\n",i->first.c_str(),i->second);
83   }
84
85
86A ``concurrent_hash_map`` acts as a container of elements of type
87``std::pair<const Key,T>``. Typically, when accessing a container
88element, you are interested in either updating it or reading it. The
89template class ``concurrent_hash_map`` supports these two purposes
90respectively with the classes ``accessor`` and ``const_accessor`` that
91act as smart pointers. An *accessor* represents *update* (*write*)
92access. As long as it points to an element, all other attempts to look
93up that key in the table block until the ``accessor`` is done. A
94``const_accessor`` is similar, except that is represents *read-only*
95access. Multiple ``const_accessors`` can point to the same element at
96the same time. This feature can greatly improve concurrency in
97situations where elements are frequently read and infrequently updated.
98
99
100The methods ``find`` and ``insert`` take an ``accessor`` or
101``const_accessor`` as an argument. The choice tells
102``concurrent_hash_map`` whether you are asking for *update* or
103*read-only* access. Once the method returns, the access lasts until the
104``accessor`` or ``const_accessor`` is destroyed. Because having access
105to an element can block other threads, try to shorten the lifetime of
106the ``accessor`` or ``const_accessor``. To do so, declare it in the
107innermost block possible. To release access even sooner than the end of
108the block, use method ``release``. The following example is a rework of
109the loop body that uses ``release`` instead of depending upon
110destruction to end thread lifetime:
111
112
113::
114
115
116           StringTable accessor a;
117           for( string* p=range.begin(); p!=range.end(); ++p ) {
118               table.insert( a, *p );
119               a->second += 1;
120               a.release();
121           }
122
123
124The method ``remove(key)`` can also operate concurrently. It implicitly
125requests write access. Therefore before removing the key, it waits on
126any other extant accesses on ``key``.
127
128.. toctree::
129   :maxdepth: 4
130
131   ../tbb_userguide/More_on_HashCompare