java - Tree map 中的 containsKey 或 get 是否使用 binarySearch？

Question

中的元素TreeMap已排序，因此我认为可能get(...)或containsKey(...)使用二进制搜索。这些方法是否比实现的方法更快HashMap？它们真的使用二分搜索吗？

Answer 1

不是二进制搜索，但复杂度必须是 O(logn)：

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。算法是对 Cormen、Leiserson 和 Rivest 的算法简介中的那些算法的改编。

请注意，它实际上是一棵红黑树：

基于红黑树的 NavigableMap 实现

但是请注意，尽管我总是讨厌盲目地将哈希表视为 O(1) 数据结构，但对于几乎所有实际目的而言，HashMap 都是 HashMap O(1)，除非：例如，您选择了一个非常糟糕的哈希函数或大量重载映射。

Answer 2

打开类TreeMap和的文档HashMap，您将得到答案。

在TreeMap中，它说：

此实现为 、 和 操作 提供有保证的log (n) 时间成本containsKeygetputremove。算法是对 Cormen、Leiserson 和 Rivest 的算法简介中的那些算法的改编。

在HashMap中，它说：

此实现为基本操作 (和)提供恒定时间性能getput，假设哈希函数将元素正确地分散在桶中。

如您所见，HashMapis O(1)，而TreeMapis O(log(n))，因此HashMap更快。

您可以在以下 Wikipedia 条目中阅读有关哈希表和红黑树（TreeMap 使用的树类型）的更多信息：

• http://en.wikipedia.org/wiki/Hash_table
• http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

在这些文章的右侧，您可以看到对这些结构的最常见操作的复杂性的总结。

Answer 3

HashMap 更快。它get()和containsKey()方法是 O(1)（恒定时间，前提是 hashCode 被正确实现）。

TreeMap 的get()和containsKey()是 O(log(n))，他们当然使用树结构来使这些操作快速。

Answer 4

如果您对 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对象。