我有一個包含ID和日期的對象的集合。我想以某種方式存儲這些對象，以便我可以有效地按ID查找它們，並刪除在某個時間點之前發生的所有事件。一段時間之前驅逐事件的高效數據結構？
我在考慮使用HashMap和TreeMap，其中HashMap包含ID，TreeMap存儲按日期排序的元素。這可以通過ID給出O（1）查找並讓我有效地移除所有舊事件。我也嘗試使用沒有ID的哈希表的日期的排序TreeMap。
是否有更高效的數據結構來存儲信息以有效地支持這些操作？
既然你想要支持的操作
我認爲可以想要使用鏈式哈希表和splay樹組合的數據結構。基本思想如下：哈希表將ID值映射到所討論的對象，並且展開樹存儲按日期排序的對象。要插入到結構中，可以在O（log n）攤銷時間內將元素插入ID散列表和splay樹中。您可以在散列表中的O（1）預期時間內執行查找。
根據問題的參數，您可以刪除在某段時間之前出現的所有元素。這個想法如下。有效地展開樹（分攤O（log n））支持刪除時間在某個特定值之前的樹中的所有內容。現在，如果您插入到此結構中的條目具有的屬性是，每當您在某個時間以下刪除所有值時，就不會再在該時間之前插入條目，則可以使用以下刪除過程：首先，使用高效算法刪除全部需要在總攤銷時間O（log n）中刪除splay樹中的條目，然後記錄剛剛刪除的時間。從這一點開始，任何時候你在散列表中進行查找，如果你看到一個元素的時間低於給定的時間閾值，你只需刪除它。如果您在重新組合時執行此操作，則可以將散列表中應刪除的所有內容從O（n）中分散到需要的時間，並且可以分攤工作。這仍然給你O（1）查找時間ID和O（1）分期插入時間到哈希表。總之，如果你能做出這樣的假設，你將得到以下運行時間：
希望這有助於！
感謝您的美妙想法。對此，我真的非常感激 ！！ – user1180969 2012-02-04 21:37:16
@ user1180969-很高興幫助！不要忘記，如果你認爲這是你正在尋找的東西，你可以接受這個答案。 :-) – templatetypedef 2012-02-04 21:40:04
你在做什麼樣的比較？你想做範圍搜索（查找日期範圍或ID範圍內的所有內容）？ – templatetypedef 2012-02-04 21:02:26
ID搜索基本上是一個查找。日期搜索是在現在之前刪除任何東西 – user1180969 2012-02-04 21:05:47