1

の要素TreeMapはソートされているため、おそらくget(...)またはcontainsKey(...)二分探索を使用すると思いました。これらのメソッドは に実装されているメソッドよりも高速で、HashMap実際に二分探索を使用していますか?

4

4 に答える 4

3

二分探索ではありませんが、複雑さは O(logn) でなければなりません:

この実装では、containsKey、get、put、remove 操作の保証された log(n) 時間コストが提供されます。アルゴリズムは、Cormen、Leiserson、および Rivest のアルゴリズム入門にあるものの適応です。

実際には赤黒木であることに注意してください。

赤黒木ベースの NavigableMap 実装

ただし、ハッシュ テーブルを盲目的に O(1) データ構造として扱うことは常に嫌いですが、ほとんどすべての実用的な目的で HashMap はO(1)です。

于 2013-07-02T21:50:23.037 に答える
3

TreeMapクラスおよびのドキュメントを開くとHashMap、答えが得られます。

ではTreeMap、次のように述べています。

この実装では、 、、および操作の保証された log(n) 時間コストがcontainsKeygetputremove提供されます。アルゴリズムは、Cormen、Leiserson、および Rivest のアルゴリズム入門にあるものの適応です。

ではHashMap、次のように述べています。

この実装は、ハッシュ関数がバケット間で要素を適切に分散すると仮定すると、基本操作 (getおよびput)に対して一定時間のパフォーマンスを提供します。

ご覧のとおり、HashMapはO(1)ですが、TreeMapはO(log(n))であるため、HashMapより高速です。

次のウィキペディアのエントリで、ハッシュ テーブルと赤黒木(TreeMap で使用される木の種類)について詳しく読むことができます。

これらの記事の右側では、これらの構造に対する最も一般的な操作の複雑さの概要を確認できます。

于 2013-07-02T21:50:54.320 に答える
1

HashMap の方が高速です。そのメソッドget()とcontainsKey()メソッドは O(1) です (hashCode が正しく実装されていれば一定時間です)。

TreeMapget()とcontainsKey()は O(log(n)) であり、もちろんツリー構造を使用してこれらの操作を高速化します。

于 2013-07-02T21:50:45.153 に答える
0

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;
}

getEntryUsingComparatorComparatorオブジェクトを使用するだけで、同じ二分探索です。

于 2013-07-02T21:55:23.737 に答える