中的元素TreeMap
已排序,因此我认为可能get(...)
或containsKey(...)
使用二进制搜索。这些方法是否比实现的方法更快HashMap
?它们真的使用二分搜索吗?
4 回答
此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。算法是对 Cormen、Leiserson 和 Rivest 的算法简介中的那些算法的改编。
请注意,它实际上是一棵红黑树:
基于红黑树的 NavigableMap 实现
但是请注意,尽管我总是讨厌盲目地将哈希表视为 O(1) 数据结构,但对于几乎所有实际目的而言,HashMap 都是 HashMap O(1)
,除非:例如,您选择了一个非常糟糕的哈希函数或大量重载映射。
在TreeMap
中,它说:
此实现为 、 和 操作 提供有保证的log (n) 时间成本
containsKey
get
put
remove
。算法是对 Cormen、Leiserson 和 Rivest 的算法简介中的那些算法的改编。
在HashMap
中,它说:
此实现为基本操作 (和)提供恒定时间性能
get
put
,假设哈希函数将元素正确地分散在桶中。
如您所见,HashMap
is O(1),而TreeMap
is O(log(n)),因此HashMap
更快。
您可以在以下 Wikipedia 条目中阅读有关哈希表和红黑树(TreeMap 使用的树类型)的更多信息:
在这些文章的右侧,您可以看到对这些结构的最常见操作的复杂性的总结。
HashMap 更快。它get()
和containsKey()
方法是 O(1)(恒定时间,前提是 hashCode 被正确实现)。
TreeMap 的get()
和containsKey()
是 O(log(n)),他们当然使用树结构来使这些操作快速。
如果您对 OpenJDK 7 的实现感兴趣,这很容易理解。所以是的,这是一个二分搜索:
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
getEntryUsingComparator
是同样的二分查找,只是使用了一个Comparator
对象。