是否有这样一个结合队列和散列表的数据结构？

Question

是否有这样的数据结构，结合Queue和Hashmap？

除了FIFO（enqueue/dequeue），其中一个队列正常了，我想

• 排队的时候，总是带着key排队行为，
• 没有密钥偷看时，返回头队列
• 与键偷看时的，返回与排队的第一个元素此键
• 没有密钥出队时，移除第一元件以往排队
• 用钥匙出队时，除去具有关键

我不知道这样的数据结构，在野外已经存在的所有元素？

Answer 1

不，没有。但是，您可以将两者结合起来以实现您想要的行为（尽管您将不得不一路做出折中）。

要做到这一点，您将存储：

• 一个HashMap其中的值是队列中的项目引用：HashMap<Key, ReferenceToFIFOElement>或HashMap<Key, Set<ReferenceToFIFOElement>>。
• 实际的FIFO队列：FIFO<Item>

当你排队，你先在队列的顶部添加元素。然后，如果密钥尚未注册（或将所述引用添加到映射到设置案例中的给定密钥的引用桶中），则使用对新创建的元素的引用来更新散列映射。只需检索密钥并访问引用的项目（或者设置案例中的第一个引用项目，或者如果没有提供密钥，则可以访问顶部）。

出列是真正的权衡将发生：

• 如果您只存储到插入在HashMap中的给定键的第一个项目的引用，那么你将不得不在遍历所有的队列，从上述项目开始。 这意味着整体更高的时间复杂度。
• 如果您将使用给定键的项目的所有引用存储在散列映射中（使用集合），那么您只需遍历该集合并从队列中删除引用的元素。 这增加了数据结构的空间复杂度。

然而，在现实中却可能更加复杂，这取决于数据结构选择的FIFO的引擎盖下的地方：

• 数组列表：缓存友好，随机存取...但可以在插入/删除元素时需要重新分配。这会导致引用 - >存储索引而不是实际引用。
• 链接列表：不缓存友好，但插入和删除保证为O（1）。