1

こんにちは、HashMap に裏打ちされた Set を使用して、グラフ内で既に通過したエッジを追跡しています。各エッジに格納されているデータのハッシュコードを追加した結果によってセットをキーイングすることを計画していました。

v.getData().hashCode() + wordV.getData().hashCode()

しかし、contains を使用してエッジがセット内にあるかどうかを確認する場合、これはどの程度信頼できるのでしょうか? 仮説的に偽陽性を得ることができませんでしたか? とにかくこれを克服する方法はありますか？

私が懸念する正確な声明は次のとおりです。

edgeSet.contains(v.getData().hashCode() + wordV.getData().hashCode())

ありがとう！

あ、ちなみに私はJavaを使っています。

編集：

私は質問でこれを明確にするべきでした。私のグラフにはエッジ オブジェクトはありません。それぞれがより多くの頂点オブジェクトのリストを保持する頂点オブジェクトがあり、これがエッジです。したがって、あなたの回答と合わせて、次の質問が続くと思います。

オブジェクトではなく、情報への参照を格納するために Set を使用できますか? つまり、頂点のデータ オブジェクトの 2 つのハッシュコードを加算した結果を保存できますか?

EDIT2：

私は実際にハッシュマップに Java ライブラリを使用しています。以下のように宣言します。

Set<Integer> edgeSet = Collections.newSetFromMap(new ConcurrentHashMap<Integer, Boolean>());
4

3 に答える 3

6

HashSet注：あなたの質問から、あなたが使用しているのか、それとも独自のホームロール実装を使用しているのかわかりませんでした。Javaは、値が無視されるHashSet単なるラッパーであることに注意してください。内部マップを呼び出すだけです。HashMapHashSet.containscontainsKey

HashMap.containsKeyは と同じルックアップを使用しますget。これにより、ハッシュが計算され、それを使用して適切なバケットが検索されます。そこからバケットをequalsたどって、完全に一致するものが見つかるまで使用します。hashCode要素の型が両方とも正しく実装されていると仮定すると、最終的には が確認に使用されるため、equals誤検知が発生する可能性はありません。containsKeyequals

関連するソース コードは、 とのgetEntry両方で使用されるpackage-private メソッドにcontainsKeyありgetます。

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

編集：

オブジェクトではなく、情報への参照を格納するために Set を使用できますか? つまり、頂点のデータ オブジェクトの 2 つのハッシュコードを加算した結果を保存できますか?

いいえ、この情報を表す新しいクラスを実装し、そのインスタンスを に格納する必要がありますSet。これは、情報の各部分のフィールドを持ち、適切にhashCodeオーバーライドequalsされた単純な POJO である可能性があります。

于 2012-09-08T02:47:54.053 に答える
5

定義上、ハッシュ コードには衝突があります。それらを一緒に追加しても何の役にも立ちません。

グラフのエッジが hashCode と equals をサポートするようにし、単純にエッジをハッシュ セットに入れる必要があります。

class Edge { ... equals and hashCode ... }

HashSet<Edge> traversed = new HashSet<Edge>();
traversed.add(edge);
...
if(traversed.contains(edge)) ...

代わりにエッジに番号を付けている場合、Integer には既に適切なハッシュ コードと equals があるため、それを使用します。

HashSet<Integer> traversed = new HashSet<Integer>();
if(traversed.contains(edgeNumber)) ...
traversed.add(3);
于 2012-09-08T02:49:26.930 に答える
1

hashCode()との両方をオーバーライドする限り、equals()問題ありません。ハッシュ コードが一意であるとは限りません。そうは言っても、あなたはセットを悪用しています。適切に実装されたメソッドを含むクラスを格納するhashCode()とequals()、次のようなメソッドcontains()' は完全な精度になります。ただし、ここではそのように使用していません。独自のデータ構造/コレクションをほとんど構築しているように聞こえるので、「ハッシュ」コレクションと同じ方法でこれを行うことを検討する必要があります - HashMap を使用してハッシュのバケットを保存します - ハッシュ値をキー、そして比較する値としてのコレクション。これにより、親マップに探しているハッシュがあるかどうかをすばやく確認できます。そうでない場合は、完了です (false)。存在する場合は、その「バケット」に探している特定の値がある (true) ことを確認する必要があります。

于 2012-09-08T02:43:16.547 に答える