允许重复访问节点的有向无环图快速并行遍历无锁实现咨询

完全可以通过原子操作实现你要的无阻塞、无synchronized的已访问集合，以下是两种可落地的实现思路：

方案一：自行实现开放寻址原子哈希集合 #

核心基于CAS操作实现，没有任何互斥锁，不会出现普通HashMap的并发死循环问题，完全匹配你允许延迟感知、容忍少量重复处理的需求：

• 底层存储采用AtomicReferenceArray（Java为例，其他语言对应原生原子数组实现），初始容量设置为2的整数次幂，方便通过位运算快速计算哈希槽位。
• 查询逻辑：对节点ID做哈希计算后定位到对应槽位，线性探测对比槽位值和目标ID，匹配则返回已访问，遍历到空槽则返回未访问。整个过程全程无锁，最多读取到其他线程写入的旧状态，正好符合你允许延迟感知的要求，不会出现非法中间状态。
• 插入逻辑：哈希定位槽位后，循环调用CAS尝试将节点ID写入空槽位，写入成功直接返回；如果探测到相同ID直接返回已存在；如果探测超过阈值则触发无锁扩容（通过CAS将旧数组替换为新的扩容后数组即可）。

方案二：基于现有并发集合优化使用（更稳妥，无需自行处理边界） #

不用自己造轮子，直接调整现有并发容器的使用姿势就能满足性能要求：

• Java生态直接使用ConcurrentHashMap.newKeySet()作为全局已访问集合：读操作contains()全程无锁，不会被任何写入操作阻塞；写操作调用putIfAbsent()，底层基于CAS实现，写入冲突时不会阻塞直接返回结果，完全符合你的需求。你允许延迟感知变更、容忍少量重复处理的特性，正好抵消了ConcurrentHashMap的弱一致性影响，没有额外副作用。

性能优化建议 #

可以给每个线程增加一个小型本地已访问缓存，每次查询先查本地缓存，本地未命中再查全局集合，插入时先写本地缓存再写全局集合，能大幅降低全局集合的访问频率，性能提升非常明显，且不会过多提升重复处理的概率。

内容的提问来源于stack exchange，提问作者me at stackexchange