何时使用TreeMap代替HashMap

Question

我需要一个支持3种操作的映射：“插入”，“删除”和“按排序顺序迭代”。这正是TreeMapJava中的接口。话虽如此，也可以通过使用a 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))。

因此，我的问题是，a TreeMap优于a 的用例是HashMap什么？仅当您需要多次遍历地图（比如说k）（在这种情况下，如果k>>是>> log(n)的运行时间TreeMap将为O(k*(n-m))而for HashMap将会为更好O(k*(n-m)*log(n-m)))吗？），无论如何，如果您仅执行O(log(n))迭代（听起来确实如此）像这样的理智的用例），HashMap会胜过TreeMap我吗？

Answer 1

当然存在这样的用例。在所有重读设置中，您都可以在插入期间仅排序一次。与您的问题的假设相反，大多数用例都是阅读量很大的。

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