我正在尝试优化一个使用基于锁的哈希表的库。一种方法是用无锁结构代替基于锁的结构。
我找到了一些算法，我决定使用本文在 C 中实现： 拆分有序列表：无锁可扩展哈希表
问题是这种结构不保留元素的插入顺序，我需要此功能有两个原因：
1）获取当前元素的下一个元素（根据插入顺序而不是哈希键顺序），
2） 在达到 ht 中的最大元素数时替换旧条目（用新条目）。这是因为我像缓冲区一样使用哈希表，并且我想固定其大小。
所以我问你，所有无锁哈希表的实现都存在这种"缺乏插入顺序"的问题？还是有解决方案？
如果内存不是问题，实现此目的的一种简单方法是使用原子引用。修改将复制内部数据结构，进行更改，然后更新引用。
在简单的实现中，这意味着最后一次写入获胜，所有其他写入将被"忽略"。对于更复杂的情况，您可以在引用中添加一个锁定结构，该结构允许对写入操作进行排队。
因此，您可以使用另一个级别的间接性付费，但可以获得一种非常简单的方法来交换数据结构和算法。
由于此方法适用于任何算法，因此您可以选择一种保留顺序的算法。