c - 是否存在保留插入顺序的无锁哈希表？

Question

我正在尝试优化我在其中使用基于锁的哈希表的库。一种方法是用无锁结构替换基于锁的结构。

我发现了一些算法，我决定使用这篇论文在 C 中实现:Split-ordered lists: lock-free extensible hash tables

问题是这种结构不保留元素的插入顺序，我需要这个特性有两个原因:

1) 获取当前元素的下一个元素(按照插入顺序而不是hashkey顺序)，

2) 当达到 ht 中的最大元素数时替换旧条目(用新条目)。这是因为我将哈希表用作缓冲区，并且我想固定其大小。

所以我问你，所有无锁哈希表的实现都会遇到这个“缺乏插入顺序”的问题吗？或者有什么解决办法？

Answer 1

如果内存不是问题，一个简单的实现方法是使用原子引用。修改将复制内部数据结构，进行更改，然后更新引用。

在一个简单的实现中，这意味着最后一次写入获胜，所有其他写入都被“忽略”。对于更复杂的情况，您可以在引用中添加一个锁定结构，以允许对写入操作进行排队。

因此，您付出了另一个间接级别的代价，但却获得了一种交换数据结构和算法的非常简单的方法。

由于这种方法适用于任何算法，您可以选择一种保留顺序的算法。