我将使用哪种数据结构或数据结构组合用于允许批量删除和特定删除的并发队列？

Question

这是我的问题,我需要一个行为像a的数据结构queue,但有一些其他属性:

• 我应该能够轻松删除给定的tag项目(此队列中的每个项目都有一个tag组合它们)
• 我还需要能够删除一个给定的key项目(添加到集合中的所有项目都将具有这样一个唯一的密钥).在这里,如果它简化了事情,我可以删除tag,key如果它会使它更快.
• 此集合在并发环境中使用,因此使用尽可能少的锁定将是非常棒的
• 它应该具有队列的通常FIFO属性.我不需要访问不在头部的项目,但我需要上面的删除行为才能工作.

我正在使用C#来构建这个解决方案,但我对算法和数据结构定义更感兴趣,因为我几乎不相信任何可用的集合满足我的需求.

论文,书籍,博客文章以及任何其他类型的参考都非常受欢迎.

Answer 1

听起来您可以对队列部分使用并发单链表。对于按键删除部分，您可以保留一个指向队列中节点的并发哈希表（条带锁很容易做到）。

如果该方法失败，请查看数据库系统如何执行此操作。他们可以同时做你想做的所有事情。它们维护 B 树中数据的主要副本并维护辅助 B 树索引。对于锁定，它们使用并发哈希表。B 树具有良好的并发属性，因为即使您在独占锁下更新叶子，也可以轻松地共享锁定它们的上部部分。