是否有這樣一個結合隊列和散列表的數據結構？

Question

是否有這樣的數據結構，結合Queue和Hashmap？

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

• 排隊的時候，總是帶着key排隊行爲，
• 沒有密鑰偷看時，返回頭隊列
• 與鍵偷看時的，返回與排隊的第一個元素此鍵
• 沒有密鑰出隊時，移除第一元件以往排隊
• 用鑰匙出隊時，除去具有關鍵

我不知道這樣的數據結構，在野外已經存在的所有元素？

Answer 1

不，沒有。但是，您可以將兩者結合起來以實現您想要的行爲（儘管您將不得不一路做出折中）。

要做到這一點，您將存儲：

• 一個HashMap其中的值是隊列中的項目引用：HashMap<Key, ReferenceToFIFOElement>或HashMap<Key, Set<ReferenceToFIFOElement>>。
• 實際的FIFO隊列：FIFO<Item>

當你排隊，你先在隊列的頂部添加元素。然後，如果密鑰尚未註冊（或將所述引用添加到映射到設置案例中的給定密鑰的引用桶中），則使用對新創建的元素的引用來更新散列映射。只需檢索密鑰並訪問引用的項目（或者設置案例中的第一個引用項目，或者如果沒有提供密鑰，則可以訪問頂部）。

出列是真正的權衡將發生：

• 如果您只存儲到插入在HashMap中的給定鍵的第一個項目的引用，那麼你將不得不在遍歷所有的隊列，從上述項目開始。 這意味着整體更高的時間複雜度。
• 如果您將使用給定鍵的項目的所有引用存儲在散列映射中（使用集合），那麼您只需遍歷該集合並從隊列中刪除引用的元素。 這增加了數據結構的空間複雜度。

然而，在現實中卻可能更加複雜，這取決於數據結構選擇的FIFO的引擎蓋下的地方：

• 數組列表：緩存友好，隨機存取...但可以在插入/刪除元素時需要重新分配。這會導致引用 - >存儲索引而不是實際引用。
• 鏈接列表：不緩存友好，但插入和刪除保證爲O（1）。