我需要一张支持 3 种操作的映射:"插入"、"删除"和"按排序迭代"。这正是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
。我错过了什么吗?
当然存在这样的用例。在所有读取密集型设置中,您具有在插入期间仅排序一次的优势。大多数用例都是阅读量大的,与您的问题的假设相反。
当您需要提取键上具有上限或下限的子映射、查找最小或最大键或查找最接近给定键的键时,TreeMap
提供了更大的优势。接口NavigableMap
专用于这些操作。
一个明显的用例是当您想根据某些Comparator
定义对地图进行排序时。这并不总是关于性能。