C++ 创建线程安全的标准映射

Creating a standard map that is thread safe

提问by MistyD

In my current scenario speed is essential I have a map that is only being read by multiple threads and this works fine. Now a requirement came up that may require writing to the static map once in a while while the maps are being read by other threads. I believe this is a game changer since I would need to lock my maps for thread safety.This poses a problem since I have multiple threads 10-12 threads that are going to be reading the map. If one map takes a lock on the map (since its reading) I believe the lock would be necessary since something might be written to a map. Anyways as I stated earlier that if one map is reading then other maps wont have the parallel reading access to the map like they did earlier. Is there any way by which I can circumvent this issue ?

在我当前的场景中，速度至关重要，我有一个只能由多个线程读取的地图，这很好用。现在出现了一个要求，可能需要在其他线程读取地图时偶尔写入静态地图。我相信这是一个游戏规则改变者，因为我需要锁定我的地图以确保线程安全。这会带来一个问题，因为我有多个线程 10-12 个线程将要读取地图。如果一张地图在地图上锁定（自读取以来），我相信该锁定是必要的，因为可能会向地图写入某些内容。无论如何，正如我之前所说，如果一张地图正在读取，那么其他地图将不会像之前那样具有对地图的并行读取权限。有什么办法可以规避这个问题吗？

采纳答案by Collin Dauphinee

You can use a shared_mutexbeside your map to acquire sharedor uniqueaccess. Generally, a write operation will require unique access, while read operations will require shared access.

您可以使用shared_mutex地图旁边的 来获取共享或唯一访问权限。通常，写操作需要唯一访问，而读操作需要共享访问。

Any number of threads can acquire shared access, as long as no threads are holding unique access. If a thread attempts to acquire unique access, it waits until all shared access is released.

只要没有线程持有唯一访问权限，任何数量的线程都可以获得共享访问权限。如果一个线程试图获取唯一访问权限，它会一直等到所有共享访问权限都被释放。

The standard library and Boost provide shared_lock<T>and unique_lock<T>for scope-bounded acquisition of a shared_mutex.

标准库和 Boost 提供shared_lock<T>和unique_lock<T>用于范围有限的shared_mutex.

Beware that some people claim shared_mutexperforms poorly, though I haven't seen any evidence or strong analysis to support these claims. It may be worth looking into, if it matters to you.

请注意，有些人声称shared_mutex表现不佳，尽管我没有看到任何证据或强有力的分析来支持这些说法。如果它对你很重要，它可能值得研究。

回答by LemonCool

just for your c++ pleasure, read this book, you'll find WAY more worth than the money spent, your concurrency world will get open wide
C++-Concurrency in Action Practical Multithreading
the books deal with all sort of issues and practical solutions between thread's data sharing, how to wake threads, thread pools creation and more...more...and more

只是为了你的 C++ 乐趣，阅读这本书，你会发现比花的钱更有价值，你的并发世界将得到广泛的
C++-Concurrency in Action Practical Multithreading
这些书籍处理线程数据之间的各种问题和实用解决方案共享、如何唤醒线程、线程池创建等等...更多...更多

here an example of sharing data between threads without using atomic or shared_locks

这是一个在线程之间共享数据而不使用 atomic 或 shared_locks 的示例

template<class T>
class TaskQueue
{
public:
    TaskQueue(){}
    TaskQueue& operator = (TaskQueue&) = delete;

    void Push(T value){
        std::lock_guard<std::mutex> lk(mut);
        data.push(value);
        condition.notify_one(); //if you have many threads trying to access the data at same time, this will wake one thread only
    }

    void Get(T& value){
        std::unique_lock<std::mutex> lk(mut);
        condition.wait(lk, [this]{ return !data.empty(); }); // in this case it waits if queue is empty, if not needed  you can remove this line
        value = data.front();
        data.pop();
        lk.unlock();
    }

private:
    std::mutex mut;
    std::queue<T> data; //in your case change this to a std::map
    std::condition_variable condition;
};

回答by Slava

One of the solution could be to keep a pointer to that map, and when you need to modify it - make a copy, modify that copy and then atomically swap the pointer to the new instance. This solution would be more memory consuming, but could be more efficient if you have many reading threads, as this method is lock free.

解决方案之一可能是保留指向该映射的指针，当您需要修改它时 - 制作一个副本，修改该副本，然后将指针自动交换到新实例。此解决方案会消耗更多内存，但如果您有许多读取线程，则效率会更高，因为此方法是无锁的。

In the example below, only one thread can modify the map.This doesn't mean one thread at a time, it means one and same thread for the life of the data structure. Otherwise, modification would need to be done while holding a mutex that protects the entire code in updateMap. The reader threads can access theDataas usual - without any locking.

在下面的示例中，只有一个线程可以修改地图。这并不意味着一次一个线程，而是意味着在数据结构的整个生命周期中只有一个线程。否则，需要在持有保护整个代码的互斥锁的同时进行修改updateMap。读取器线程可以theData像往常一样访问- 无需任何锁定。

typedef std::map<...> Data;

std::atomic<Data *> theData;

void updateMap( ... )
{
   Data *newData = new Data( *theData );
   // modify newData here
   Data *old = theData.exchange( newData );
   delete old;
}

回答by Andrushenko Alexander

Here is my implementation of threadsafe generic resizable hashmap without using stl containers:

这是我在不使用 stl 容器的情况下实现的线程安全通用可调整大小的哈希图：

#pragma once

#include <iomanip>
#include <exception>
#include <mutex>
#include <condition_variable>

/*
*  wrapper for items stored in the map
*/
template<typename K, typename V>
class HashItem {
public:
    HashItem(K key, V value) {
        this->key = key;
        this->value = value;
        this->nextItem = nullptr;
    }

    /*
    * copy constructor
    */
    HashItem(const HashItem & item) {
        this->key = item.getKey();
        this->value = item.getValue();
        this->nextItem = nullptr;
    }

    void setNext(HashItem<K, V> * item) {
        this->nextItem = item;
    }

    HashItem * getNext() {
        return nextItem;
    }

    K getKey() {
        return key;
    }

    V getValue() {
        return value;
    }

    void setValue(V value) {
        this->value = value;
    }

private:
    K key;
    V value;
    HashItem * nextItem;

};

/*
* template HashMap for storing items
* default hash function HF = std::hash<K>
*/
template <typename K, typename V, typename HF = std::hash<K>>
class HashMap {
public:
    /*
    * constructor
    * @mSize specifies the bucket size og the map
    */
    HashMap(std::size_t mSize) {
        // lock initialization for single thread
        std::lock_guard<std::mutex>lock(mtx);
        if (mSize < 1)
            throw std::exception("Number of buckets ust be greater than zero.");

        mapSize = mSize;
        numOfItems = 0;
        // initialize
        hMap = new HashItem<K, V> *[mapSize]();
    }

    /*
    * for simplicity no copy constructor
    * anyway we want test how different threads 
    * use same instance of the map
    */
    HashMap(const HashMap & hmap) = delete;

    /*
    * inserts item
    * replaces old value with the new one when item already exists
    * @key key of the item
    * @value value of the item
    */
    void insert(const K & key, const V & value) {
        std::lock_guard<std::mutex>lock(mtx);
        insertHelper(this->hMap, this->mapSize, numOfItems, key, value);
        condVar.notify_all();
    }

    /*
    * erases item with key when siúch item exists
    * @key of item to erase
    */
    void erase(const K & key) {
        std::lock_guard<std::mutex>lock(mtx);
        // calculate the bucket where item must be inserted
        std::size_t hVal = hashFunc(key) % mapSize;
        HashItem<K, V> * prev = nullptr;
        HashItem<K, V> * item = hMap[hVal];

        while ((item != nullptr) && (item->getKey() != key)) {
            prev = item;
            item = item->getNext();
        }
        // no item found with the given key
        if (item == nullptr) {
            return;
        }
        else {
            if (prev == nullptr) {
                // item found is the first item in the bucket
                hMap[hVal] = item->getNext();
            }
            else {
                // item found in one of the entries in the bucket
                prev->setNext(item->getNext());
            }
            delete item;
            numOfItems--;
        }
        condVar.notify_all();
    }

    /*
    * get element with the given key by reference
    * @key is the key of item that has to be found
    * @value is the holder where the value of item with key will be copied
    */
    bool getItem(const K & key, V & value) const {
        std::lock_guard<std::mutex>lock(mtx);
        // calculate the bucket where item must be inserted
        std::size_t hVal = hashFunc(key) % mapSize;
        HashItem<K, V> * item = hMap[hVal];

        while ((item != nullptr) && (item->getKey() != key))
            item = item->getNext();
        // item not found
        if (item == nullptr) {
            return false;
        }

        value = item->getValue();
        return true;
    }


    /*
    * get element with the given key by reference
    * @key is the key of item that has to be found
    * shows an example of thread waitung for some condition
    * @value is the holder where the value of item with key will be copied
    */
    bool getWithWait(const K & key, V & value) {
        std::unique_lock<std::mutex>ulock(mtxForWait);
        condVar.wait(ulock, [this] {return !this->empty(); });
        // calculate the bucket where item must be inserted
        std::size_t hVal = hashFunc(key) % mapSize;
        HashItem<K, V> * item = hMap[hVal];

        while ((item != nullptr) && (item->getKey() != key))
            item = item->getNext();
        // item not found
        if (item == nullptr) {
            return false;
        }

        value = item->getValue();
        return true;
    }


    /*
    * resizes the map
    * creates new map on heap
    * copies the elements into new map
    * @newSize specifies new bucket size
    */
    void resize(std::size_t newSize) {
        std::lock_guard<std::mutex>lock(mtx);
        if (newSize < 1)
            throw std::exception("Number of buckets must be greater than zero.");

        resizeHelper(newSize);
        condVar.notify_all();
    }

    /*
    * outputs all items of the map
    */
    void outputMap() const {
        std::lock_guard<std::mutex>lock(mtx);
        if (numOfItems == 0) {
            std::cout << "Map is empty." << std::endl << std::endl;
            return;
        }
        std::cout << "Map contains " << numOfItems << " items." << std::endl;
        for (std::size_t i = 0; i < mapSize; i++) {
            HashItem<K, V> * item = hMap[i];
            while (item != nullptr) {
                std::cout << "Bucket: " << std::setw(3) << i << ", key: " << std::setw(3) << item->getKey() << ", value:" << std::setw(3) << item->getValue() << std::endl;
                item = item->getNext();
            }
        }
        std::cout << std::endl;
    }

    /*
    * returns true when map has no items
    */
    bool empty() const {
        std::lock_guard<std::mutex>lock(mtx);
        return numOfItems == 0;
    }

    void clear() {
        std::lock_guard<std::mutex>lock(mtx);
        deleteMap(hMap, mapSize);
        numOfItems = 0;
        hMap = new HashItem<K, V> *[mapSize]();
    }

    /*
    * returns number of items stored in the map
    */
    std::size_t size() const {
        std::lock_guard<std::mutex>lock(mtx);
        return numOfItems;
    }

    /*
    * returns number of buckets
    */
    std::size_t bucket_count() const {
        std::lock_guard<std::mutex>lock(mtx);
        return mapSize;
    }

    /*
    * desctructor
    */
    ~HashMap() {
        std::lock_guard<std::mutex>lock(mtx);
        deleteMap(hMap, mapSize);
    }

private:
    std::size_t mapSize;
    std::size_t numOfItems;
    HF hashFunc;
    HashItem<K, V> ** hMap;
    mutable std::mutex mtx;
    mutable std::mutex mtxForWait;
    std::condition_variable condVar;

    /*
    * help method for inserting key, value item into the map hm
    * mapSize specifies the size of the map, items - the number
    * of stored items, will be incremented when insertion is completed
    * @hm HashMap
    * @mSize specifies number of buckets
    * @items holds the number of items in hm, will be incremented when insertion successful
    * @key - key of item to insert
    * @value - value of item to insert
    */
    void insertHelper(HashItem<K, V> ** hm, const std::size_t & mSize, std::size_t & items, const K & key, const V & value) {
        std::size_t hVal = hashFunc(key) % mSize;
        HashItem<K, V> * prev = nullptr;
        HashItem<K, V> * item = hm[hVal];

        while ((item != nullptr) && (item->getKey() != key)) {
            prev = item;
            item = item->getNext();
        }

        // inserting new item
        if (item == nullptr) {
            item = new HashItem<K, V>(key, value);
            items++;
            if (prev == nullptr) {
                // insert new value as first item in the bucket
                hm[hVal] = item;
            }
            else {
                // append new item on previous in the same bucket
                prev->setNext(item);
            }
        }
        else {
            // replace existing value
            item->setValue(value);
        }
    }

    /*
    * help method to resize the map
    * @newSize specifies new number of buckets
    */
    void resizeHelper(std::size_t newSize) {
        HashItem<K, V> ** newMap = new HashItem<K, V> *[newSize]();
        std::size_t items = 0;
        for (std::size_t i = 0; i < mapSize; i++) {
            HashItem<K, V> * item = hMap[i];
            while (item != nullptr) {
                insertHelper(newMap, newSize, items, item->getKey(), item->getValue());
                item = item->getNext();
            }
        }

        deleteMap(hMap, mapSize);
        hMap = newMap;
        mapSize = newSize;
        numOfItems = items;
        newMap = nullptr;

    }

    /*
    * help function for deleting the map hm
    * @hm HashMap
    * @mSize number of buckets in hm
    */
    void deleteMap(HashItem<K, V> ** hm, std::size_t mSize) {
        // delete all nodes
        for (std::size_t i = 0; i < mSize; ++i) {
            HashItem<K, V> * item = hm[i];
            while (item != nullptr) {
                HashItem<K, V> * prev = item;
                item = item->getNext();
                delete prev;
            }
            hm[i] = nullptr;
        }
        // delete the map
        delete[] hm;
    }
};

回答by inder

What you need is equivalent a ConcurrentHashMap in Java, which allows for concurrent reading and writing to the underlying hash table. This class is part of the java.util.concurrent package and provides for concurrent reading and writing (upto a concurrency level, defaults to 16).

您需要的是等效于 Java 中的 ConcurrentHashMap，它允许对底层哈希表进行并发读取和写入。此类是 java.util.concurrent 包的一部分，提供并发读取和写入（最高并发级别，默认为 16）。

You can find more information in the javadoc. I am quoting the javadoc here:

您可以在javadoc 中找到更多信息。我在这里引用 javadoc：

A hash table supporting full concurrency of retrievals and adjustable expected concurrency for updates. This class obeys the same functional specification as Hashtable, and includes versions of methods corresponding to each method of Hashtable. However, even though all operations are thread-safe, retrieval operations do not entail locking, and there is not any support for locking the entire table in a way that prevents all access. This class is fully interoperable with Hashtable in programs that rely on its thread safety but not on its synchronization details.

一个哈希表，支持检索的完全并发性和可调整的更新预期并发性。该类遵循与Hashtable相同的功能规范，并包含与Hashtable的每个方法对应的方法版本。但是，即使所有操作都是线程安全的，检索操作也不需要锁定，并且不支持以防止所有访问的方式锁定整个表。在依赖其线程安全但不依赖于其同步细节的程序中，此类与 Hashtable 完全可互操作。

回答by tmyklebu

The other two answers are quite fine, but I thought I should add a little bit of colour:

另外两个答案很好，但我想我应该添加一点颜色：

Cliff Click wrote a lock-free concurrent hash map in Java.It would be nontrivial to adapt it to C++ (no GC, different memory model, etc.) but it's the best implementation of a lock-free data structure I've ever seen. If you can use JAva instead of C++, this might be the way to go.

Cliff Click用 Java编写了一个无锁并发哈希映射。让它适应 C++（没有 GC、不同的内存模型等）是很重要的，但它是我见过的无锁数据结构的最佳实现。如果您可以使用 JAva 而不是 C++，这可能是要走的路。

I'm not aware of any lock-free balanced binary tree structures. That doesn't mean they don't exist.

我不知道任何无锁平衡二叉树结构。这并不意味着它们不存在。

It's probably easiest to go with one of the two other answers (bulk copy/atomic swap/something like shared_ptror reader-writer locking) to control access to the mapinstead. One of the two will be faster depending on the relative quantities of reads and writes and the size of the map; you should benchmark to see which one you should use.

使用其他两个答案之一（批量复制/原子交换/类似shared_ptr或读写器锁定）来控制对它的访问可能是最简单的map。两者之一会更快，具体取决于读取和写入的相对数量以及 的大小map；你应该进行基准测试，看看你应该使用哪一个。