c# - 对于允许批量和特定删除的并发队列，我将使用什么数据结构或数据结构组合？

Question

这是我的问题，我需要一个行为类似于 a 的数据结构queue，但具有一些其他属性：

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

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

论文、书籍、博客文章和任何其他类型的参考都非常受欢迎。

Answer 1

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

如果该方法失败，请查看数据库系统如何做到这一点。他们可以同时做你想做的所有事情。它们在 b-tree 中维护数据的主要副本并维护辅助 b-tree 索引。对于锁定，他们使用并发哈希表。B 树具有很好的并发特性，因为即使在排他锁下更新叶子时，您也可以轻松地共享锁定它们的上部。

Answer 2

我认为您可以使用双重多链表和两个哈希表。

• 队列列表的一部分
• 按标签对节点进行分组的另一部分
• 一个用于通过键访问节点的哈希表
• 另一个通过标签访问节点的哈希表

Python 中的示例（对不起……）

插入一个元素：

 items_table['item_key'] = new_item

 my_queue.tail.next = new_item
 new_item.previous = my_queue.tail
 my_queue.tail = new_item

 new_item.next_by_tag = tags_table['item_tag'] #head of tag's list
 tags_table['item_tag'].previous_by_tag = new_item
 tags_table['item_tag'] = new_item

按键删除元素：

item = key_table['node_key']

item.next.previous = item.previous
item.previous.next = item.next

item.next_by_tag.previous_by_tag = item.previous_by_tag
item.previous_by_tag.next_by_tag = item.next_by_tag

del item

按标签删除元素：

def remove_elements_by_tag(tag_head):
    if tag_head == None:
        return
    else:
        remove_elements_by_tag(tag_head.next_by_tag)
        tag_head.next.previous = tag_head.previous
        tag_head.previous.next = tag_head.next

类似的东西。希望能帮助到你。