2

私は声明を読みました：

HashSet は、基本的な操作 (追加、削除、包含、およびサイズ) に対して一定時間のパフォーマンスを提供します。

ここで「含む」は本当ですか？バケットの候補リストは一定時間のパフォーマンスですが、バケット ao(n) 操作内の要素を見つけていませんか?

私は何かを誤解していますか？

4

6 に答える 6

2

ドキュメントが言うように、

このクラスは、ハッシュ関数がバケット間で要素を適切に分散すると仮定すると、基本操作 (追加、削除、包含、およびサイズ) に対して一定時間のパフォーマンスを提供します。

上記の仮定部分を確認してください。世界で最も貧弱なハッシュ関数の 1 つの結果として、すべての要素が 1 つのバケットに収まる場合、Contains は o(n) です。HashSet は内部的に HashMap を使用します。

于 2013-03-29T05:39:20.860 に答える
2

n in o(n) は、バケット内ではなく、ハッシュ内の要素数を表します。バケット内の要素の数はセットのサイズに比例して増加せず、制限されているため、一定の最大時間がかかる場合があります。定数時間は表記に影響しません。少なくとも完全なハッシュ関数がある場合、これはまったく別の問題です。

于 2013-03-29T05:44:58.763 に答える
0

名前が示すように、技術HashSetによって実装されます。hasingしたがって、これは、オブジェクトを見つける複雑さが O(1) であることを意味します。containsこれがO(1) 時間かかる理由です。しかし、最悪の場合、すべてのオブジェクトが同じバケットに入れられると、複雑さは O(n) になります。

このセットに指定された要素が含まれている場合は true を返します。より正式には、このセットに (o==null ? e==null : o.equals(e)) となる要素 e が含まれている場合にのみ true を返します。

public boolean contains(Object o) {
    return map.containsKey(o);
}

上記は HashSet クラスの contains メソッドです。オブジェクトを格納するために map を使用していることに注意してください。

于 2013-03-29T05:47:35.927 に答える
0

HashSethasing 関数を使用して要素を検索します。その中で評価するのはO(1)です。

たとえば、従業員の名前を格納するためのハッシュ テーブルがある場合、その関数を ASCII 文字の合計として使用します。

f(name) = sum(ascii chars)

f('ahmed') = 'a' + 'h' + 'm' + 'e' + 'd' = 97 + 104 + 109 + 101 + 100 = 511 となります。したがって、'ahmed' は次の場所に格納されます。 511. ただし、前のハッシュ関数は非常に悪く、同じ合計を生成する名前で評価すると多くの競合が発生します。したがって、適切なハッシュ関数を見つけることは、ハッシュ テーブルの実装において非常に重要な目標です。

詳細については、ハッシュ テーブルのデータ構造を参照してください。

于 2013-03-29T05:29:30.283 に答える
0

はい、そうですfinding the elements within the bucket a o(n) operation。
contains演算性能はO(n)です。ターゲット オブジェクトを、 内の他のすべてのオブジェクトと等しくしますHashSet。

于 2013-03-29T05:35:37.110 に答える
0

バケット ao(n) 操作内の要素が見つかりませんか?

それは本当に依存します。アルゴリズムが各値を調べて目的の値を取得しなければならないほど多くのハッシュ衝突がある場合、最悪の場合、時間は o(n) になります。しかし、それは良いハッシュ関数ではありません。適切なハッシュ関数は、割り当てられたハッシュをその範囲全体に均等に広げます。

hashCodeこれは、常に同じものを返す場合にも発生する可能性があり、これも良い兆候ではありません。セットのカーディナリティに関係なく、同じハッシュが得られます。

于 2013-03-29T05:52:59.390 に答える