使用散列圖實現優先隊列

Question

這可能是一個非常天真的問題，或者沒有意義。但是我對實施優先隊列感到困惑。 爲什麼我們不能使用帶密鑰的散列表作爲優先級，並將值作爲具有該優先級的數據。 我在這裏錯過了一些基本的東西。 例如： 如果A的優先級是1，B是3，c是4 我們可以簡單地將1,3,4作爲關鍵字並將A，B，C分別保存爲hashmap的值，分別用於優先級隊列的實現。 請清除我的邏輯

Answer 1

該實現的問題在於，它沒有利用HashMap功能輕鬆訪問給定密鑰的任何元素。由於您正在創建一個隊列，因此您以後不會擁有優先級1,3,4，並且只需要查找地圖的最高優先級，必須完全迭代才能完成此操作！

一張地圖的工作原理是這樣的：它在所有位置創建一個具有空值的巨大數組（非常非常大）。然後，它使用公式獲取您的密鑰，通常是字符串或字符串表示形式，然後將其轉換爲數字。一個簡單的方法是對每個字母的字符代碼進行求和，雖然這對地圖來說是一個不好的選擇，但您可以稍後查看它的原因。然後，使用數組的模數（餘數）大小（例如，Java中的n％大小）對該數字進行上限，以便它成爲數組中的有效位置，然後將該元素放置在那裏。這樣，進行深入搜索非常容易，因爲您不需要搜索，您確切知道每個元素的位置。

因此，使用Map實現隊列將會非常耗費內存，而沒有HashMap搜索的明顯優勢。此外，遍歷它非常非常昂貴，因爲您需要迭代一個巨大的數組並忽略空值;你不確定實際值在哪裏。在你的例子中想象一下，優先級從0到100.即使你永遠不會有100個任務，你將有一個100個位置數組迭代，檢查每個位置是否存在具有該優先級的任務。

更好的方法是使用簡單的列表並將優先級存儲在數據中。假設優先級不隨時間變化，您只需在添加時迭代一次，以找到正確的位置，並始終訪問第一個（或最後一個）元素，即具有已知最高優先級的元素。

在性能的最後一個註釋中，最好重複添加，即使您添加的搜索時間完全相同。因爲當你搜索最高優先級時，每次都需要一直到最後，因爲也許最後一個元素是較大的一個。請注意，即使您的鍵是數字字符串或整數，HashMap也不會存儲以整齊新月順序組織的項目。它專門設計爲而不是這樣做，以避免衝突（兩個相同的對象具有相同的密鑰，因此需要將列表添加到大陣列的特定位置）。但是，當你添加時，假設你的列表已經排序了，你只需要迭代直到你到達正確的目的地。

Answer 2

當您嘗試遍歷HashMap時，您將得到一個奇怪的順序。 HashMap（或任何有關此事的地圖）沒有保證的遍歷順序，所以你將無法以有效的方式「排序」隊列。

你當然可以查詢所有的鍵，排序列表並按順序獲取值，但與替代方法相比，這是非常低效的（你已經在O（n^2）處爲鍵的長度而沒有做額外的工作）

Answer 3

長話短說，這一切都歸結爲HashMap s沒有排序，因此您最終需要一些外部機制來弄清楚隊列中的「下一個」。

因此，例如，說你把條目

[1, "A"] 
[3, "B"] 
[4, "C"] 

如果你只有一個HashMap，有搞清楚這1是「第一」短通過每一個關鍵迭代的沒有可靠的方法，因爲在內部該鍵可以是：

[1, "A"] 
[3, "B"] 
[4, "C"] 

或

[3, "B"] 
[4, "C"] 
[1, "A"] 

或

[3, "B"] 
[1, "A"] 
[4, "C"] 

等等。

從HashMap javadoc：

此類不保證作爲對地圖的順序;特別是，它不能保證訂單會隨着時間的推移保持不變。

所以使用HashMap真的沒有意義的，因爲你必須閒着額外的工作使得HashMap相比，到底堆效率較低。現在

---

，如果你真的想使用HashMap，你可以：

• 抓住EntrySet，按密鑰，然後得到的第一個值。沒關係，如果這只是只有時間，你需要搶第一個值，但情況很少。只要您更改地圖並需要重新執行此操作，效率會比常規堆更差。

• 使用一些外部機制，如ArrayList或其他東西來跟蹤鍵，也許保持它作爲插入值的一部分排序。但是，此時不妨跳過HashMap並實現「正常」堆，否則基本上會做同樣的事情，但會增加在ArrayList和HashMap之間分割數據的複雜性。

所以最後，額外的工作並不值得。