包含鍵或獲取樹圖使用binarySearch？

Question

對TreeMap中的元素進行排序，因此我認爲可能get(...)或containsKey(...)使用二分搜索。這些方法是否比在HashMap中實施的方法更快，他們真的使用二分搜索嗎？

Answer 1

Not binary search but the complexity must be O(logn)：

此實現提供了保證的log（n）的時間成本，爲containsKey方法，GET，PUT和刪除操作。算法是Cormen，Leiserson和Rivest的算法簡介中的算法的改編。

注意它實際上是一個紅黑樹：基於

紅黑樹NavigableMap實現

不過需要注意的是，雖然我永遠恨對待哈希表的O （1）數據結構盲目地，幾乎所有的實際用途HashMap是O(1)，除非：例如，你選擇一個非常糟糕的散列函數或大量超載地圖。

Answer 2

HashMap更快。它的get()和containsKey()方法是O（1）（恆定時間，只要hashCode被正確實現）。

TreeMap的get()和containsKey()是O（log（n）），它們當然使用樹結構來使這些操作更快。

Answer 3

打開類TreeMap和HashMap的文檔，您將得到您的答案。

在TreeMap，它說：

此實現提供了containsKey，get，put和remove操作保證的log（n）的時間成本。算法是Cormen，Leiserson和Rivest的算法簡介中的算法的改編。

在HashMap，它說：

此實現提供爲基本操作（get和put）穩定的性能，假定哈希函數將分散的桶中正確的元素。

正如你可以看到，HashMap是O（1），而TreeMap是O（的log（n）），因此HashMap更快。

你可以在下面的維基百科條目閱讀更多關於哈希表和紅黑樹（由TreeMap的使用樹的類型）：

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

在這些文章的右側，您可以看到這些結構上最常見操作的複雜性總結​​。

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對象。