ConcurrentMap 并发映射的使用

1. 源码：https://github.com/preshing/junction

使用步骤

1. 生成libjunction.a和libturf.a

git clone https://github.com/preshing/junction.git
git clone https://github.com/preshing/turf.git
cd junction
makdir build
cd build
cmake ..
make

2. 使用静态库

• 1. 新建自己的工程
• 2. 添加libs include 文件夹
• 3. 把libjunction.a 和libturf.a复制到libs里， 把turf/turf 和junction/junction两个文件夹复制到新建的include文件夹中
• 4. 把junction/build/include中的文件和junction/build/turf/include中的文件复制到自己工程的include文件夹中
• 4. 在新建工程的CMakeLists.txt中添加 include_directories(include include/junction include/turf) link_directories(libs) link_libraries(libjunction.a libturf.a pthread)，注意include_directories时要加上include,不然还是一样会报错

ConcurrentMap

1. 为什么使用ConcurrentMap

• ConcurrentMap并发映射，是为了解决高并发性查找map而产生的，即多线程操作，或者服务器客服端模式。
• 然后为什么要用MAP数据结构？map采用key-value键值对结构，具有极快的查找速度。pyhton中有包装好的数据结构。比如说，假设要根据同学的名字查找对应的成绩，用Array实现，需要两个Array,并且速度不快，用结构体数组同样速度也是比较慢。
• hash有个冲突问题，它的解决方法通常有：开放定址法、链地址法、再哈希法等

2. ConcurrentMap库

image.png

• ConcurrentMap_Crude：一种并发HashMap的简陋实现
• junction::ConcurrentMap_Linea：一种受Java non-blocking HashMap启发的简单无锁HashMap
• junction::ConcurrentMap_Leapfrog：类似于Linea，但是使用了跳房子哈希法（Hopscotch Hashing）的松散搜索策略
• junction::ConcurrentMap_Grampa：其与Leapfrog类似，但是在数据量大的时候会拆分成多个更小的、定长的Leapfrog

3. concurrentMap的使用

#include " ConcurrentMap_Grampa.h"
typedef junction::ConcurrentMap_Grampa<int, Student*> ConcurrentMap;
ConcurrentMap myMap;
void testMap{
  myMap.assign(taskId, new Student) // 将id和空间对应
  myMap.get(taskId); // 获取对应的空间
  myMap.erase(taskId); //在map中释放这个空间
  myMap.exchange(taskId, Student* student) //将key的value值换一个
}
总的来说，map它不会分配空间，调用assign函数时，空间都是我们分配好了，然后把指针传过去。因此除了
erase外，我们还需free或者delete相关内存
int main{
// Create QSBR context for the main thread.
    junction::QSBR::Context context = junction::DefaultQSBR.createContext();
 // Run a simple map test.
    testMap();

    // Update the QSBR context for this thread.
    // In a larger application, this should be called periodically, for each thread, at a moment
    // when the thread is quiescent – that is, not in the middle of any operation that uses a
    // Junction data structure.
    junction::DefaultQSBR.update(context);

    // Destroy the QSBR context for the main thread.
    junction::DefaultQSBR.destroyContext(context);
return 0
}

小结

• HashMap采用链地址法解决哈希冲突，多线程访问哈希表的位置并修改映射关系的时候，后执行的线程会覆盖先执行线程的修改，所以不是线程安全的
• Hashtable采用synchronized关键字解决了并发访问的安全性问题，但是效率低
• ConcurrentHashMap使用了线程锁分段技术，每次访问只允许一个线程修改哈希表的映射关系，所以是线程安全的