为何多数无锁链表实现假设元素唯一？如何支持重复元素？

为什么多数无锁链表实现仅支持唯一元素 #

• 简化并发控制逻辑：唯一元素场景下，插入只需定位到第一个大于目标值的节点位置，无需处理相同值节点的遍历；删除操作也只需找到对应值的节点即可，避免了重复元素带来的多节点匹配问题，降低CAS操作的冲突概率和逻辑复杂度。
• 贴合经典设计目标：Harris的原始论文中，无锁链表的设计初衷是实现高效的集合（Set）结构，集合本身要求元素唯一性，后续多数实现基于这个基础模型衍生，自然延续了这一特性。
• 控制内存与性能开销：重复元素会拉长链表长度，遍历、插入、删除时需处理更多节点，既增加内存占用，又会提高CAS操作的重试概率，影响并发性能。

注释存在性检查后需补充的修改 #

仅注释插入逻辑中检查元素是否存在的代码（第111-113行）还不够，还需做以下调整：

• 调整插入位置判断：原逻辑找到第一个大于目标值的节点后，会检查前驱节点值是否匹配（判断已存在）。现在要改为直接在该位置插入新节点，无需判断前驱节点值，只要保证新节点插入到第一个大于目标值的节点之前即可，不管前方是否有相同值节点。
• 修改删除逻辑：若原删除逻辑只处理第一个匹配节点，现在要根据需求调整：如果是删除任意一个匹配节点，需遍历找到第一个未被标记删除的匹配节点再执行CAS标记；如果是删除所有匹配节点，则要循环遍历处理每个匹配节点。
• 保证并发插入一致性：多线程插入重复元素时，要确保CAS操作的正确性——新节点的next指针需正确指向当前后继节点，前驱节点的next指针通过CAS原子更新为新节点，避免链表断裂或节点丢失。
• 调整查找逻辑：若需求是返回所有匹配节点，遍历过程中要跳过已标记删除的节点，直到遍历完所有相同值的节点。

支持重复元素的无锁链表技术资源 #

• 《The Art of Multiprocessor Programming》扩展思路：在第9章无锁链表基础上，参考后续章节中无锁数据结构的扩展设计，重点关注多元素场景的并发控制优化方向。
• Harris算法扩展论文：查找针对重复元素场景改进的无锁链表研究论文，这类内容通常会调整节点匹配逻辑、优化CAS操作顺序，解决重复元素的并发插入、删除安全问题。
• 开源实现参考：查看ConcurrencyFreaks仓库或其他并发编程仓库中支持重复元素的无锁链表代码，分析它们如何处理重复节点的插入、删除逻辑，比如是否通过节点额外字段区分重复元素，或是调整遍历和CAS的执行时机。

内容的提问来源于stack exchange，提问作者J-w