6

Java の HashMap と TreeMap の両方で equals() の計算上の複雑さを理解しようとしています。さて、HashMap と TreeMap の両方が AbstractMap から同じ実装を継承するため、どちらの場合も同じであるべきだと言うかもしれません。ただし、それを完全に受け入れる前に、説明が必要です。

これが私を混乱させるものです。AbstractMap ドキュメントのオーバーライドされた equals() の説明の一部は次のとおりです。

より正式には、m1.entrySet().equals(m2.entrySet()) の場合、2 つのマップ m1 と m2 は同じマッピングを表します。

entrySet によって返されるセットが HashSet なのか、SortedSet なのか、それ以外なのかについて、ドキュメントは明確ではありません。私の見解では、これは分析全体に影響を与えるため、知っておくことが重要です。

entrySet() によって返されるセットが HashSet 型の場合、2 つのセットを O(n) で比較できます [2 つのハッシュ セットの場合の等しいコスト]。ただし、SortedSet 型の場合は、O(nlogn) [2 つの並べ替えられたセットの場合の等しいコスト] で比較できます。したがって、HashMap の場合の equals() の複雑さは、SortedMap の場合とは異なるか、少なくとも私の推論に基づく必要があります。

私の推論のどこかが間違っていると強く思うので、どこが間違っているか教えてください。正しい理屈とは。最後に、HashMap と SortedMap の場合の equals() の複雑さに興味があります。ありがとう。

4

1 に答える 1

5

両方の方法の複雑さについては、あなたが正しいと思います。どちらも から equals 実装を継承しているためAbstractMap、 のソース コードを調べる価値がありますAbstractMap。関連する部分は次のとおりです。

Map<K,V> m = (Map<K,V>) o;
if (m.size() != size())
    return false;

Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
    if (!(m.get(key)==null && m.containsKey(key)))
        return false;
} else {
    if (!value.equals(m.get(key)))
        return false;
}
return true;

サブクラスによってオーバーライドされる内側のループ内でgetandメソッドを呼び出すことに注意してください。containsKeyHashMap はこれらを O(1) で実装し、TreeMap は O(log n) で実装するため、Hashmap の O(n) と TreeMap の O(n log n) の全体的な複雑さが等しくなります。

于 2013-09-17T05:57:37.617 に答える