Hash在多线程下面怎么做到高效的修改？

lxyscls

一个比较困扰的问题

Hash本身可以做到线程安全的操作（find/insert/remove），但是如果要修改某个item的内容（譬如是一个struct or class reference），如何做到高效的修改？
目前想到的几种方式：
1、lock 或 spin_lock，保护整个写过程
2、摘下来，写好，放回去
3、用一块新的内存去替换原来的，只涉及一个atomic update reference的操作，但是需要分配内存

lxyscls

回复 2# wlmqgzm

不好意思，我讲得不是这个意思，BTW，您的第二种方案其实也就是Java ConcurrentHashMap，先分segment，然后每个segment才算是一个真正的Hash结构
我的问题是：怎么做到高效的修改Hash中的Item内容，譬如每个Item内容是个strcut，怎么能够 原子的 高效修改这些内容

假设有A B两个线程能够同时拿到这个Item，如果让它们同时修改，肯定会出现不一致的情况

其他Hash的基本操作，我都假设它是线程安全的

lxyscls

回复 4# mr_sev

原子的修改指针或者引用是没有问题的，不过这样就意味着新分配内存

lxyscls

回复 6# sxcong

1. strcut {
   
2.     int a;
   
3.     int b;
   
4.     int c;
   
5. }

复制代码

假设每个item是这样的，Hash支持并发的find，多个线程找到这个item之后，肯定需要原子的修改(a,b,c)，否则就冲突了我大概问的就是这个意思，难道说没这种需求？？

lxyscls

回复 11# wlmqgzm

您的方案

一个方式就是: 新得到一个裸指针 new struct data, 拷贝旧数据到新裸指针的结构中 copy from old struct data, 修改数据 modify new struct data, 一次性更新裸指针 change point,

1、如何获取一个裸指针？内存从哪里来？new or malloc？
2、怎么保证old struct data在拷贝过程中一直有效呢？假设还有一个writer完成了修改，这个时候只要它修改了指针，那么这块old data对它来说就没用了，也许就被它给释放掉了
3、您说的这种方案其实是“SPMC”的？“MPMC”怎么弄呢？

PS，您讲的这个跟我最初的某个想法挺相似的，不过当时我也没考虑copy过程中的有效性问题

3、用一块新的内存去替换原来的，只涉及一个atomic update reference的操作，但是需要分配内存

lxyscls

回复 14# wlmqgzm

读锁和写锁，２个锁互不干扰

我再多问一下，如果互不干扰的话，怎么做到“写时不读”和“读时不写”呢？两个锁判断的东西都不一样，一个是mutex，一个是cas retry。或者说两个在底层的还是用到了同一个atomic进行cas操作，只是逻辑不一样？
PS
    两把锁在Intel TBB里面也有，const accessor和accessor，不过Intel的代码实在是稀烂，没有看的欲望，相较Folly的代码整齐多了。

    目前还是想办法找现成的用起来先

lxyscls

回复 16# codechurch

单读单写啦，是没我提的问题
我想知道如果支持“多读后再多写”（不改变位置，算是个“原位操作”）怎么玩？

lxyscls

windoze 发表于 2016-12-01 23:23
用open address hash table，删除用mark deletion，这样增删改只需一个指针的cas。
至于存放元素的内存管 ...

猫哥好晚啊

增删能理解，但是“改”怎么做到一个cas呢？pair(const k, v)，挂上个新的v也算是改了？

也就是说v其实是块新内存（新指针）？read-copy-write？