創建按Java中的創建/更新時間排序的有序HashMap

Question

我正在使用以下格式的數據元組：[IP，字節數，時間]。我在IP上創建了一個HashMap來計算爲每個IP服務的字節數。然後，我意識到我需要刪除最近最少使用的鍵值對來創建更多空間。我想創建一個時間約束，比如說1小時，並且在那段時間內沒有動作的情況下刪除鍵值對。所以我需要保存每一對的更新時間。事實上，對於具有按時間戳排序的對的良好性能來說似乎是合理的。

因此，我想要做的是維護一個基於鍵值對的創建或更新時間的排序列表。我需要明確地瞭解這些創建和更新時間。我提出了兩個不同的想法，但現在確切地確定要使用哪一個以及如何使用。這裏是我的兩個想法：

• 我需要一個LinkedList頭指向最近更新的鍵值對的時間戳，並有這個鍵值對點列表節點。
• 我需要根據其創建/更新時間以排序順序維護HashMap。也許我需要用整數值和長指示時間戳將整數值更改爲對象。

而問題是如何在Java中實現這些功能以實現高效的添加/刪除/獲取性能？或者我可以使用哪些庫來獲取按創建/更新時間排序的HashMap？

Answer 1

要按創建/更新時間進行排序，您需要有時間進行比較。這意味着當被創建/更新時，您的對象將必須知道。通過在創建對象時默認設置version字段並在更新對象時將其設置爲new Date()，可以相對容易地完成此操作。

有您能立足自己（TreeSet和TreeMap，尤其是）誰落實對象本身（Comparable接口）或Comparator定義的順序結構。如果您存儲更新時保存日期的項目，則可以實施可幫助排序過程的比較器。

如果您僅限於使用LinkedList和HashMap，則必須使用例如Collections#Sort對列表進行排序。在HashMap的情況下，您必須對Entry Set進行排序，但由於無法對其進行修改，因此必須以這種方式生成新的已排序映射。

儘管如此，HashMap是一種與排序無關的結構，因此在遍歷它時仍然會遇到一些問題。 A LinkedHashMap可以解決這個問題，但同樣，這一切都取決於您的數據類型限制。

Answer 2

這是一個適合LinkedHashMap的情況，覆蓋了removeEldestEntry()方法。這張地圖的關鍵是IP地址，值將是(bytes, last_update)的一個元組。

首先，您需要使用「訪問順序」創建您的地圖：這意味着任何對地圖條目的訪問都會將該條目移動到列表的末尾（MRU）。然後，在獲得新記錄時執行以下操作：

• 如果映射不包含IP的條目，請創建一個包含字節數的新條目。
• 如果map確實包含一個條目，請獲取其中的字節數，並通過將新的字節添加到old來創建新條目。然後put()新的進入地圖，取代舊的。

您的元組應自動設置時間字段爲當前時間。但是，要理解的是，你並不真正關心時間，它只是一個用於從列表中刪除項目的屬性。

覆蓋removeEldestEntry()，如果時間超出範圍，則返回true。

雖然，老實說，我認爲你會更好地使用基於尺寸的驅逐戰略（限制你的地圖數量固定）。基於時間的策略會讓您遇到DDOS攻擊，在這種情況下，您有大量條目一次進入，耗盡您的內存。

Answer 3

提供我的兩分錢......我最近做了類似的事情（當時我不知道LinkedHashMap），我需要跟蹤一些會話信息。

我最終使用了ConcurrentHashMap，因爲一次可以激活多個用戶會話，並且每30分鐘運行一次清理以清除陳舊的會話數據。我的思考過程是，由於應用程序需要更快的性能來處理會話數據，因此我將會話ID保留爲關鍵字。當我需要清除最舊的數據時，只需抓取數值列表並進行排序（假設該類實現了Comparable，或者您可以爲其編寫Comparator），因爲這不是「經常」完成的。

希望有所幫助。

PS。我很好奇這與LinkedHashMap實施相比如何？