高效獲取LinkedHashSet中最近插入的元素

根據LinkedHashSet的Javadoc，它將通過內部使用雙向鏈表來保持插入元素的插入順序。高效獲取LinkedHashSet中最近插入的元素

它維護一個雙向鏈表，它貫穿其所有條目。該鏈接列表定義迭代順序，哪個是哪個元素被插入到該組（插入順序）

如果我想獲取所述第一插入元件，我可以使用代碼像在順序：

linkedHashSet.iterator().next()

這會給我在O（1）集中的第一個插入的元素。

我想解決一個問題，它需要我訪問O（1）中的最新插入元素，並假設不會有任何重複元素插入到集合中。例如，

linkedHashSet.add(2); // the most recent inserted element in the set is 2 
linkedHashSet.add(3); // the most recent inserted element in the set is 3 
linkedHashSet.add(5); // the most recent inserted element in the set is 5 
linkedHashSet.remove(5); // the most recent inserted element in the set is 3 because 5 is removed and not in the set now

既然是在設置一個雙向鏈表，看來最近的元素應該是雙向鏈表中的最後一個，應該能夠爲O訪問（1）如果有一些API可以獲得它。

我的問題是：在JDK中有沒有辦法做到這一點，或者我需要創建自己的ReversedIteratingLinkedHashSet來做到這一點？基本上，我嘗試爲所有操作找到一個具有O（1）時間複雜度的Set數據結構，包括：插入/刪除/搜索/檢查集合中最近插入的元素。內置的LinkedHashSet似乎很適合內部的非常小的修改，但我不確定這是否可以使用默認的JDK類API完成。

注：我檢查JDK的源代碼，並知道LinkedHashSet在內部與LinkedHashMap實現，如果有，可以使用LinkedHashMap的訪問最近插入的元素爲O任何解決方案（1），這對我來說是非常有用太。

非常感謝。

來源

2013-07-25 nybon

請了解我的教程[LinkedHashMap的內部生活]（http://volodial.blogspot.com/2013/07/internal-life-of-linkedhashmap-in-java.html）以更好地瞭解LinkedHashSet，因爲後者是隻是前 –

的包裝，我會推薦在這裏使用LinkedHashMap。因爲在插入映射後，您可以通過鍵快速獲取映射。無論如何LinkedHashSet是LinkedHashMap。 –

不幸的是，似乎沒有直接/乾淨的方式來訪問O（1）中的LinkedHashSet（或LinkedHashMap）中最近添加的元素。

一個乾淨的方法是將該集合轉換爲一個數組並訪問最後一個元素，但這將是O（n）。

一個骯髒的方法是使用反射來訪問內部哈希映射，映射的頭條目，最後是條目的前驅（before）。

來源

2013-07-25 13:20:58 Thomas

感謝您告訴我這樣做的「骯髒的方式」，最後我編寫了自己的LinkedHashSet變體。 – nybon

@VolodymyrLevytskyi除了禮貌（稱某人是騙子）之外，你應該證明你的主張。迭代時，最近插入的元素的順序是最後一個元素，除非您有自己的實現，這樣做是相反的。 – Thomas

對不起！事實是，最近添加的元素是在鏈表的頭部，並且是迭代時的最後一個... –

高效獲取LinkedHashSet中最近插入的元素

回答

相關問題