java - 创建guava TreeMultimap的子图并对其键值对进行高效迭代

Question

我有一个TreeMultimap<Integer, String> ，其中还包括重复的键。

I want to get and display the key value pairs which lies within a specific key range, that too with O(logN+m) time complexity, where N is the total number of key value pairs and m is the number of key value pairs within the given range.

我正在考虑使用其方法 asMap() 将 TreeMultimap 转换为 SortedMap，然后在所需范围内创建子图。

SortedMap<Integer, Collection<String>> sortedMap = mapList.getTmm().asMap();
return sortedMap.subMap(beg,end);

但是，正在使用asMap()方法有效吗？如何显示 Collection 对象中的每个键值对具有给定时间复杂度的类。

或者我应该完全改变我的方法吗？请帮忙。

Answer 1

TreeMultimap.asMap()在 O(1) 时间内返回一个对底层结构进行操作的 View (因此与直接使用 Multimap 的效率大致相同)。 NavigableMap.subMap()类似地返回其底层结构的 View 。这个 View 不是 O(1)，因为它必须对更大的 map 进行一些搜索，但这并不比您手动查找第一个元素然后进行迭代的操作更糟糕。

因此，由于两层间接，存在一些轻微的开销，但本质上您应该期望与直接操作原始数据结构相同的性能。由于 TreeMultimap 由树支持，常见操作(如 get 和 put)的复杂度为 O(log n)，迭代的复杂度为 O(n)。

所有这些意味着迭代由 someTreeMultimap.asMap().subMap(...) 返回的映射将是 O(log n) + O(n) (因此，线性) ，因为子图操作必须搜索第一个有效条目 - 从那里它只是正常迭代，直到到达最后一个有效条目。您应该可以毫无问题地迭代从 subMap() 返回的映射的 entrySet()。