何时使用TreeMap而不是HashMap？

Question

I require a map that supports 3 operations: "insert", "remove" and "iterate in sorted order". This is exactly the interface of TreeMap in Java. That being said it can also be implemented by using a HashMap and sorting it every time before iteration. To analyze the different approaches, lets say I perform n inserts and m removes, 'r' reads and then iterate.

With TreeMap we have the following implementation:

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)

All told we have a total run time of O(n*log(n) + m*log(m) + r*log(n-m))

With HashMap we have the following implementation:

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)

All told we have a total run time of O((n-m)*log(n-m)).

For all n,m O(n*log(n) + m*log(m) + r*log(n-m)) > O((n-m)*log(n-m)).

My question therefore is, what is the use case where a TreeMap is better than a HashMap? Is it only better if you need to iterate over the map many (let's say k) times (in which case, if k is >> log(n) the run time for TreeMap will be O(k*(n-m)) whereas for HashMap will be O(k*(n-m)*log(n-m)))? Regardless, if you are only performing O(log(n)) iterations (this does sound like such a sane use case), HashMap will outperform TreeMap. Am I missing something?

- Benjy Kessler

---

https://dev59.com/33VC5IYBdhLWcg3wbQXA - sunysen

https://dev59.com/gG435IYBdhLWcg3wlRIf - sunysen

那是针对特定用例的。我的观点是，是否存在一种情况，TreeMap比HashMap更好。 - Benjy Kessler

不是这样的！最好将地图复制到列表中并进行排序。 - Benjy Kessler

我肯定不会仅仅因为可读性而偏爱HashMap。适当的代码设计可以在任何情况下轻松提供可读性。 - Marko Topolnik

Answer 1

当然存在这样的用例。在所有读取为主的设置中，插入时只需进行一次排序即可获得优势。与您的问题假设相反，大多数用例确实是以读取为主。

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

- Marko Topolnik

---

我编辑了我的问题，考虑到读取。在HashMap中，读取的时间复杂度为O(1)，而在TreeMap中运行的时间复杂度为O(log(n))。 - Benjy Kessler

这是真的吗？哪个应用程序比插入、删除和获取更经常地迭代Map？我认为获取将是最常见的操作，而不是迭代。如果迭代是最常见的操作，那么你就会得到一个O(k*n) > O(n^2)的算法，这已经很难处理了。 - Benjy Kessler

我能理解为什么NavigableMap很有用，如果你想使用树来实现它那也没问题。我的问题是为什么TreeMap很有用。 - Benjy Kessler

TreeMap实现了NavigableMap接口。 - Marko Topolnik

在一句话中，您提到整个“应用程序”，然后突然转向一个“算法”。应用程序通过引用在“TreeMap”中建立的状态来服务请求，通常通过这种方式服务许多请求，并偶尔进行更新。 - Marko Topolnik

Answer 2

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

- user3248346

---

OP已经讲过了：在迭代之前，使用HashMap并进行排序。 - Marko Topolnik

你可以使用自定义比较器对map,keySet()进行排序。 - default locale

我的观点是，OP只关注性能方面。在某些情况下，最重要的要求不是性能，而是以某种有序的方式保存数据。 - user3248346

没人关心你如何“持有”数据；我们关心的是你能用它做什么。如果我给你一个内部使用HashMap并在返回keySet之前使用数组排序的实现，你会像使用TreeMap一样满意。 - Marko Topolnik

@MarkoTopolnik，我认为你在这里看不到树林。 - user3248346

我认为你的评论没有建设性。你只是表达了一个观点，没有提供任何进一步的论据。 - Marko Topolnik