Map是一种我们熟知的数据结构，存储键值对的集合，支持find，insert和erase操作。
并发哈希图是一个可以让你调用其中的一些功能，例如允许insert多个线程进行调用且没有互斥。允许另一个线程正在执行时进行调用find，且没有相互排斥，则它是并发映射。传统图（例如std::map）std::unordered_map是不允许这样操作。
本文在这里发布Junction，这是一个C++库，其中包含几个新的并发映射。BSD许可，可以在任何项目中自由使用源代码。（本文末尾会贴上代码地址）
在我电脑Corei7-K上，Junction的两个最快的映射优于其他所有并行映射。
它们有三种特性：
Junction的线性映射类似于不久前发布的简单无锁哈希表，不同之处在于它还支持调整大小，删除条目以及模板化键/值类型。它受CliffClick的Java非阻塞哈希图的启发，但有一些区别。Junction的Leapfrog映射与Linear相似，不同之处在于它宽松地使用了基于跳房子哈希的探测策略。当表被密集的填充时，此策略可提高查找效率。Leapfrog的伸缩性比Linear好，因为Leapfrog修改共享状态的频率要低得多。Junction的Grampa图类似于Leapfrog，不同之处在于，在十分频繁写入时，该地图被分成一组较小的固定大小的Leapfrog表。每当这些表出现溢出时，它就会被拆分为两个新表，而不是调整整个图的大小。Junction旨在支持尽可能多的平台。到目前为止，它已经在Windows，Ubuntu，OSX和iOS上进行了测试。它的主要依赖项是CMake和一个名为Turf的配套库。Turf是POSIX，Win32，Mach，Linux，Boost，C++11以及可能的其他平台API的抽象层。建议可以Turf配置为使用所需的API。
使用交汇图
使用整数或原始指针类型实例化一个类模板。
typedefjunction::ConcurrentMap_Grampaturf::u64,Foo*ConcurrentMap;ConcurrentMapmyMap;每个图开放的功能，例如get，assign，exchange和erase。这些函数相互之间都是原子操作，所以我们可以随时从线程调用它们。它们还隐式提供了释放和使用语义，因此可在线程之间安全地传递非原子信息。
myMap.assign(14,newFoo);Foo*foo=myMap.get(14);foo=myMap.exchange(14,newFoo);deletefoo;foo=myMap.erase(14);deletefoo;在所有可能的键中，必须保留一个空键，而在所有可能的值中，必须保留null和重定向值。默认值为0和1。我们可以通过将自定义KeyTraits和ValueTraits参数传递给模板来覆盖这些默认值。
安全内存回收
所有Junction映射都依赖一种称为QSBR的安全内存回收形式，即基于静态的静态内存回收。QSBR可描述为原始垃圾收集器。
如果在C++中执行垃圾收集似乎很怪，请记住，可伸缩的并发映射在Java中已经很普遍。那不是巧合。垃圾回收使您可以避开锁，尤其是在读取操作期间，这可以大大提高可伸缩性。甚至不需要读写锁。您当然可以在没有垃圾回收的情况下用C++编写并发映射，但是我怀疑它会像Junction映射一样缩放。
为了使QSBR工作，每个线程必须junction::DefaultQSBR.update在该线程处于静止状态时（即不在使用该映射的操作中）定期调用。在游戏引擎中，我们可以在主循环的迭代之间调用它。
动态分配的值
交接图在内部使用QSBR，但仍必须自己管理对象的生存期。图目前是不支持智能指针。
如果要存储动态分配的对象，则通常需要在插入新对象之前检查表中的现有条目。有两种方法可以做到。一种方法是乐观地创建对象，然后使用来检测竞速插入exchangeValue。
ConcurrentMap::Mutatormutator=myMap.insertOrFind(14);Foo*value=mutator.getValue();if(!value){value=newFoo;Foo*oldValue=mutator.exchangeValue(value);if(oldValue)junction::DefaultQSBR.enqueue(Foo::destroy,oldValue);}上面的代码使用Mutator，就像指向图中单条数据的指针一样。首先，insertOrFind创建一条数据。然后，如果两个线程竞相插入相同的键，则第二个线程将对第一个线程创建的对象进行垃圾回收。
另一种方法是完全使用双重检查锁定来防止此类冲突。这种方法可确保为给定密钥仅创建一个对象。
Foo*value=myMap.get(14);if(!value){turf::LockGuardturf::Mutexlock(someMutex);ConcurrentMap::Mutatormutator=myMap.insertOrFind(14);value=mutator.getValue();if(!value){value=newFoo;mutator.assignValue(value);}}传送门