何时使用 TreeMap 而不是 HashMap

Question

我需要一张支持 3 种操作的地图："insert"、"remove" 和 "iterate in sorted order"。这正是Java中TreeMap的界面。也就是说，它也可以通过使用 HashMap 并在每次迭代之前对其进行排序来实现。为了分析不同的方法，假设我执行 n 插入和 m 删除，'r' 读取然后迭代。

使用 TreeMap 我们有以下实现：

TreeMap<Integer, Integer> tm = Maps.newTreeMap();
for (int i=0;i<n;++i) {tm.put(i, 2*i);} // O(n*log(n))
for (int i=0;i<m;++i) {tm.remove(i);} // O(m*log(m))
for (int i=0;i<r;++i) {tm.get(i);} // O(r*log(n-m))
for (Integer i : tm) {print(i);} // O(n-m)

总而言之，我们总共运行时间 O(n*log(n) + m*log(m) + r*log(n-m))

使用 HashMap 我们有以下实现：

HashMap<Integer, Integer> hm = Maps.newHashMap();
for (int i=0;i<n;++i) {hm.put(i, 2*i);} // O(n)
for (int i=0;i<m;++i) {hm.remove(i);} // O(m)
for (int i=0;i<r;++i) {hm.get(i);} // O(r)
List<Integer> sortedList = Lists.newArrayList(hm.keySet()); // O(n-m)
Collections.sort(sortedList); // O((n-m)*log(n-m))
for (Integer i : sortedList) {print(i);} // O(n-m)

总而言之，我们总共有运行时间 O((n-m)*log(n-m))。

所有 n,m O(n*log(n) + m*log(m) + r*log(n-m)) > O((n-m)*log(n-m))。

因此，我的问题是，TreeMap 优于 HashMap 的用例是什么？只有当你需要遍历地图很多次（比方说 k）时才更好吗（在这种情况下，如果 k 是 >> log(n) 的运行时间TreeMap 将是 O(k*(n-m)) 而 HashMap 将是 O(k*(n-m)*log(n-m)))？无论如何，如果您只执行 O(log(n)) 迭代（这听起来像是一个理智的用例), HashMap 将胜过 TreeMap。我错过了什么吗？

Answer 1

当然存在这样的用例。在所有读取密集型设置中，您都具有在插入期间仅排序一次的优势。大多数用例是重读，这与您的问题的假设相反。

当您需要提取具有键的上限或下限的子图、查找最小或最大键或查找最接近给定键的键时，TreeMap 提供了更大的优势。界面 NavigableMap 专用于这些操作。

Answer 2

一个明显的用例是当您想根据某些 Comparator 定义对地图进行排序时。这并不总是与性能有关。

何时使用 TreeMap 而不是 HashMap

When to use TreeMap instead of HashMap

java

collections