java - 从 SortedMap 的头部删除多个项目的性能

Question

我在 Java 中工作并且有一个 SortedMap，它是作为 ConcurrentSkipListMap 实现的。我需要从 SortedMap 的头部删除一些项目——即所有键小于某个阈值的项目。实际删除的项目数可能最终为 0、1 或多个。这有可能(但不太可能)导致整个 SortedMap 中的所有项目都被删除(即，极有可能至少有一个项目将大于阈值，但不能保证)。

在我看来，应该有一种方法可以相当有效地做到这一点，因为我们可以利用以下假设:1)要删除的项目是连续的，以及 2)要删除的第一个项目是SortedMap(并且根据#1，其余的紧随其后)。如果我构建自己的跳过列表，这很容易做到，但我很懒，不想重建内置 ConcurrentSkipListMap 中已经为我提供的所有逻辑，只是为了进行这个自定义操作。所以我的问题是，在使用 ConcurrentSkipListMap 时如何利用这些假设来提高性能？

我想出了以下方法，但不知道它们是否真的利用了我的假设:

SortedMap<Date, Item> mymap = ConcurrentSkipListMap<Date, Item>();
addItemsToMap(mymap);
Date threshold = calculateThreshold();

方法一:遍历，删除项目，直到我达到阈值。

Iterator<Entry<Date, Item>> itr = mymap.entrySet().iterator();
for (Date key = itr.next().getKey(); key.before(threshold); key = itr.next().getKey())
    itr.remove();

方法二:重复删除第一项，直到第一项超过阈值。

for (Date key = mymap.firstKey(); key.before(threshold); key = mymap.firstKey())
    mymap.remove(key);

方法三:获取从head到threshold的entry集合，然后全部移除。

Iterator<Entry<Date, Item>> itr2 = mymap.headMap(threshold).entrySet().iterator();
while (itr2.hasNext()) {
    itr2.next();
    itr2.remove();
}

方法四:#3 的更优雅版本。

mymap.headMap(threshold).clear();

Answer 1

我建议您使用 ConcurrentSkipListMap 类中提供的 tailMap 方法。

由于此 Collection 已排序，您可能必须将 key 传递给您需要从中获取数据的方法。

你可以看看java docs .

例如 - 让我们假设我的 ConcurrentSkipListMap 有键 1,2,4,5 并且我的阈值是 2。我会通过 2 + 1 = 3 到 tailMap 方法，我将返回一个 ConcurrentNavigableMap ，其中包含 4 和 5 .