寻求无需读写同步的高速多线程Set实现，性能优于ConcurrentHashMap

你描述的场景完全可以通过数组+CAS的方式实现专用Set结构，性能会大幅优于通用的ConcurrentHashMap：后者为了支持全功能操作（增删改、任意key类型、强一致性、扩容并发安全等）有大量冗余开销，而你的场景只需要add/contains两个操作、key固定为Long类型、允许弱一致性，完全可以砍掉所有不必要的逻辑实现极致性能。

基础结构设计 #

采用开放寻址+挂链的哈希结构，核心设计如下：

• 底层用AtomicReference<Node>[]作为哈希桶数组，长度取2的n次方，将哈希取模运算转换为位运算降低开销
• 每个桶存储不可变的Node链表：Node类仅用final修饰long id和Node next两个字段，保证对象初始化安全，不会出现半初始化对象被读线程访问的问题
• 因为你的场景哈希冲突率极低（单桶元素通常1个，最多2-3个），链表遍历开销可以忽略

add操作逻辑 #

满足O(1)平均复杂度，无锁实现：

1. 计算待插入id的哈希值，通过位与运算得到桶下标
2. 先遍历当前桶的链表，判断元素是否已存在，已存在则直接返回
3. 不存在则新建Node，将当前桶的链表头挂在新Node的next字段上，形成新的链表头
4. 用CAS尝试将桶的引用从旧链表头替换为新链表头
5. CAS失败则重复步骤2-4，因为冲突率极低，通常1-2次重试即可成功

contains操作逻辑 #

全程无同步、无阻塞，性能接近普通数组读：

1. 计算待查询id的哈希值，得到桶下标
2. 直接读取当前桶的链表头，遍历判断是否存在对应id
3. 存在返回true，不存在返回false

注意：读操作没有加任何内存屏障，最多看不到其他线程刚写入的元素，刚好符合你允许跨线程写入延迟可见的要求；同时因为链表是不可变结构，绝对不会出现普通HashSet多线程读死循环的问题。

扩容处理（可选） #

如果可以提前预估图的节点规模，初始化时直接将桶数组开至足够大（负载因子控制在0.5以下），可以完全省略扩容逻辑。如果需要支持动态扩容：

• 后台单独线程创建新的更大的桶数组，批量迁移所有桶的链表
• 迁移完成后用原子操作替换全局的桶数组引用即可
• 迁移过程中写操作还是写入旧数组，读操作优先查新数组，查不到再查旧数组即可，符合弱一致性要求

• 哈希函数选用针对Long优化的低碰撞实现，比如直接对Long的高低位做异或运算，或者用精简版MurmurHash
• Java 9+可以用AtomicReferenceArray的getPlain/setPlain方法做普通读写，仅CAS操作带内存屏障，比默认的volatile读开销更低
• 因为图遍历场景重复插入的概率极低，可以先尝试CAS插入，失败后再检查元素是否存在，省掉一次链表遍历开销

• 读操作全程无锁无阻塞，完全不需要等待写入操作完成
• 本线程插入成功后，后续读操作必然能看到刚插入的元素（CAS操作的线程内可见性天然满足）
• 跨线程写入允许延迟可见，最多导致遍历少量重复路径，不会影响业务正确性

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