问题描述

背景

我正在尝试使用 C++ 中的链接方法设计和实现无锁哈希图。每个哈希表单元都应该包含无锁列表。为了启用调整大小，我的数据结构应该包含两个数组 - 一个始终可用的小数组和一个用于调整大小的较大数组，当较小的数组不再足够时。当创建较大的数据时，我希望将存储在较小数据中的数据一一传输到较大的数据中，只要任何线程对数据结构执行某些操作（添加元素、搜索或删除元素）。传输完所有数据后，将移动较大的数组而不是较小的数组，并删除后一个数组。只要阵列需要扩大，循环就会重复。

问题

如前所述，每个数组都应该包含单元格中的列表。我正在尝试找到一种方法将值或节点从一个无锁列表传输到另一个列表，以使值在任何（或两个）列表中都可见。需要确保在哈希映射中的搜索不会给用户带来错误的否定。所以我的问题是：

这样的无锁列表实现可能吗？
如果是这样，这种列表和“移动节点/值”操作的一般概念是什么？我会感谢任何伪代码、C++ 代码或描述它的科学文章。

标签： concurrencyparallel-processinglock-free

为了能够调整数组大小，同时保持无锁进度保证，您将需要使用操作描述符。调整大小开始后，添加一个描述符，其中包含对旧数组和新数组的引用。

在任何操作（添加、搜索或删除）上：

添加操作，搜索旧数组，如果元素已经存在，则将元素移动到新数组中再返回。使用描述符或特殊的空值指示元素已被移动，以便其他线程不会再次尝试移动
搜索，搜索旧数组并移动元素，如上所示。
删除 - 删除也必须首先搜索旧数组。

现在的问题是您将有一个线程必须验证移动是否完成，以便您可以删除描述符并释放旧数组。为了保持无锁，您需要让所有活动线程都尝试进行此验证，因此它变得非常昂贵。

你可以看看：

concurrency - 在无锁列表之间移动值

问题描述

背景

问题

解决方案

推荐阅读