创建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 class 对象中的每个键值对。

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

Answer 1

TreeMultimap.asMap() returns a view in O(1) time that operates on the underlying structure (and so is roughly as efficient as working with the Multimap directly). NavigableMap.subMap() 同样 returns 其底层结构的视图。此视图不是 O(1)，因为它必须对较大的地图进行一些搜索，但它并不比您手动查找第一个元素然后迭代的方式差。

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

所有这些意味着迭代 someTreeMultimap.asMap().subMap(...) 返回的映射将是 O(log n) + O(n)（因此，线性），因为子图操作必须搜索第一个有效的条目 - 从那里它只是像往常一样迭代，直到它到达最后一个有效条目。迭代从 subMap().

返回的地图的 entrySet() 应该没有问题

创建guava TreeMultimap的子图及其键值对的高效迭代

Creating a submap of guava TreeMultimap and efficient iteration of its key-value pairs

java

dictionary

multimap

sortedmap

guava