# concurrent_hash_map Template Class

## Summary

Template class for associative container with concurrent access.

## Syntax

    template < typename Key, typename T,
             typename HashCompare=tbb_hash_compare<Key>,
             typename A=tbb_allocator<std::pair < Key, T> > >
             class concurrent_hash_map;

## Header

    #include "tbb/concurrent_hash_map.h"

## Description

A `concurrent_hash_map` maps keys to values in a way that permits multiple threads to concurrently access values. The keys are unordered. There is at most one element in a `concurrent_hash_map` for each key. The key may have other elements in flight but not in the map, as described in Concurrent Operations. The interface resembles typical STL associative containers, but with some differences critical to supporting concurrent access. It meets the Container Requirements of the ISO C++ standard. Types `Key` and `T` must model the CopyConstructible concept. Type `HashCompare` specifies how keys are hashed and compared for equality. It must model the HashCompare concept in the table below.

HashCompare Concept
Pseudo-Signature | Semantics
--- | ---
`HashCompare::HashCompare( const HashCompare& )` | Copy constructor.
`HashCompare::~HashCompare ()` | Destructor.
`bool HashCompare::equal( const Key& j, const Key& k ) const` | True if keys are equal.
`size_t HashCompare::hash( const Key& k ) const` | Hashcode for key.

### Caution

As for most hash tables, if two keys are equal, they must hash to the same hash code. That is for a given HashCompare h and any two keys `j` and `k`, the following assertion must hold: `"!h.equal(j,k) || h.hash(j)==h.hash(k)"`. The importance of this property is the reason that `concurrent_hash_map` makes key equality and hashing function travel together in a single object instead of being separate objects. The hash code of a key must not change while the hash table is non-empty.

### Caution

Good performance depends on having good pseudo-randomness in the low-order bits of the hash code.

## Example

When keys are pointers, simply casting the pointer to a hash code may cause poor performance because the low-order bits of the hash code will be always zero if the pointer points to a type with alignment restrictions. A way to remove this bias is to divide the casted pointer by the size of the type, as indicated below in `bold italic font`.

               size_t MyHashCompare::hash( Key* key ) const {
                return reinterpret_cast<size_t>(key)/sizeof(Key);
               }

## Members

In the following synopsis, methods shown in `bold font` may be concurrently invoked.

            namespace tbb {
        template<typename Key, typename T, typename HashCompare,
                 typename Alloc=tbb_allocator<std::pair<Key,T> > >
        class concurrent_hash_map {
        public:
            // types
            typedef Key key_type;
            typedef T mapped_type;
            typedef std::pair<const Key,T> value_type;
            typedef size_t size_type;
            typedef ptrdiff_t difference_type;
            typedef value_type* pointer;
            typedef const value_type* const_pointer;
            typedef value_type& reference;
            typedef Alloc allocator_type;

            // whole-table operations
            concurrent_hash_map(
                const allocator_type& a=allocator_type() );
            concurrent_hash_map(
                size_type n,
                const allocator_type &a = allocator_type() );
            concurrent_hash_map(
                const concurrent_hash_map&,
                const allocator_type& a=allocator_type() );
            template<typename InputIterator>
                concurrent_hash_map(
                    InputIterator first, InputIterator last,
                    const allocator_type& a = allocator_type())
            ~concurrent_hash_map();
            concurrent_hash_map operator=(const concurrent_hash_map&);
            void rehash( size_type n=0 );
            void clear();
            allocator_type get_allocator() const;

            // concurrent access
            class const_accessor;
            class accessor;

            // concurrent operations on a table
            bool find( const_accessor& result, const Key& key ) const;
            bool find( accessor& result, const Key& key );
            bool insert( const_accessor& result, const Key& key );
            bool insert( accessor& result, const Key& key );
            bool insert( const_accessor& result, const value_type& value );
            bool insert( accessor& result, const value_type& value );
            bool insert( const value_type& value );
            template<typename I> void insert( I first, I last );
            bool erase( const Key& key );
            bool erase( const_accessor& item_accessor );
            bool erase( accessor& item_accessor );

            // parallel iteration
            typedef implementation-defined range_type;
            typedef implementation-defined const_range_type;
            range_type range( size_t grainsize=1 );
            const_range_type range( size_t grainsize=1 ) const;

            // capacity
            size_type size() const;
            bool empty() const;
            size_type max_size() const;
            size_type bucket_count() const;

            // iterators
            typedef implementation-defined iterator;
            typedef implementation-defined const_iterator;
            iterator begin();
            iterator end();
            const_iterator begin() const;
            const_iterator end() const;
            std::pair<iterator, iterator> equal_range( const Key& key );
            std::pair<const_iterator, const_iterator>
                equal_range( const Key& key ) const;
        };

        template<typename Key, typename T, typename HashCompare,
                 typename A1, typename A2>
        bool operator==(
            const concurrent_hash_map<Key,T,HashCompare,A1> &a,
            const concurrent_hash_map<Key,T,HashCompare,A2> &b);

        template<typename Key, typename T, typename HashCompare,
                 typename A1, typename A2>
        bool operator!=(const
            concurrent_hash_map<Key,T,HashCompare,A1> &a,
            const concurrent_hash_map<Key,T,HashCompare,A2> &b);

        template<typename Key, typename T, typename HashCompare,
                 typename A>
        void swap(concurrent_hash_map<Key,T,HashCompare,A>& a,
                  concurrent_hash_map<Key,T,HashCompare,A>& b)
    }

## Exception Safety

The following functions must not throw exceptions:

- The hash function
- The destructors for types `Key` and `T`.

The following hold true:

- If an exception happens during an insert operation, the operation has no effect.
- If an exception happens during an assignment operation, the container may be in a state where only some of the items were assigned, and methods `size()` and `empty()` may return invalid answers.

Parent topic: Containers Overview

- Whole Table Operations
- Concurrent Access
- Concurrent Operations
- Parallel Iteration
- Capacity
- Iterators
- Global Functions
- tbb_hash_compare Class

## See Also

Concurrent Operations