1

セット内のすべてのオブジェクトに対して一意の値を生成する必要があるタスクがあります。ハッシュコードコントラクトで衝突が許可されていない場合は、ハッシュコードを使用するのが最適です。

1つのアイデア：すべてのオブジェクトのハッシュコードをマルチセットに記録します。次に、一意の識別子としてハッシュコードを使用しますが、そのハッシュコードがセットに複数回含まれている場合は、セットに含まれていない別の値を使用します。しかし、これはかさばり、ぎこちなく感じます。

より良いアイデア？

これが私がすでに持っているものです：

public static <V> void toGraphViz(final Graph<V, DefaultWeightedEdge> g, String filename) {

    // to avoid hashcode collisions
    final Set<Integer> hashcodes = new HashSet<Integer>(g.vertexSet().size());

    DOTExporter<V, DefaultWeightedEdge> dot = new DOTExporter<V, DefaultWeightedEdge>(new VertexNameProvider<V> () {

    // vertex name must be unqiue
    @Override
    public String getVertexName(V arg0) {
        int hash = arg0.hashCode();
        while (hashcodes.contains((hash))) {
            hash += 1;
        }
        return "" + hash;
    }
}

編集：これは元々明確ではなかったと思いますが、ID番号はオブジェクトの関数である必要があります。これは、何度も呼び出され、同じ値に対して同じ結果が得られるgetVertexName(V)ことを期待しているためです。V

また、頂点タイプはジェネリックです。したがって、これを修正するために特定のクラスに変更を加えることはできません。

4

7 に答える 7

4

この一意の番号の有効期間はどれくらいですか？プログラムの存続期間だけですか？その場合、適切な同期でアクセスされる、クラス内の単純な静的カウンターではないのはなぜですか？新しいオブジェクトごとにインクリメントします。使用した値のリストを保持する必要はありません。使用した最大値のみを保持します。

多くの実行（およびおそらく多くの同時インスタンス）で一意である場合は、unqiueレコードIDを生成するデータベースを使用できます。

明確化に応じて編集

以前に見逃したのは、一意の「ハッシュ」を生成するクラスを変更できないことでした。

衝突するクラスのハッシュコードから作業することは、人生を困難にしていると思います。正しく実装されたequals（）を備えた問題のVertexクラスに依存できると仮定すると、使用したハッシュコードのセットへのキーとしてオブジェクト自体を使用できます。

public class Hasher {

    public  <V> void toGraphViz(final Graph<V, DefaultWeightedEdge> g, String filename) {
         final Map<V, Integer> hashcodes = new HashMap< V, Integer>();
         final int latestHashHolder[] = { 0 }; // array to allow access from inner class

         DOTExporter<V, DefaultWeightedEdge> dot 
                 = new DOTExporter<V, DefaultWeightedEdge>(new VertexNameProvider<V> ()) {

         // vertex name must be unqiue
            @Override
            public synchronized String getVertexName(V vertex) {
                int hashcode;
                if ( hashcodes.containsKey(vertex)){
                    hashcode = hashcodes.get(vertex);
                } else {                
                    hashcode = latestHashHolder[0];
                    latestHashHolder[0]++;
                    hashcodes.put(vertex, (Integer)latestHashHolder[0]);
                }
                return "Vertex-" + hashcode;
            }
        };
    }
}
于 2009-12-03T22:54:52.470 に答える
2

シリアル番号だけを使ってみませんか？

static private int serial=0;
static public synchronized nextSerialNumber() { return ++serial; }

または、組み合わせ/ハイブリッド、たとえばlong（（hash << 32）| getNextSerial（））と言います。

EDITの説明に対処するため

オブジェクトを作成するときは、シリアル番号をプライベートメンバー変数に割り当て、hashCode（）に返します。次に、super.equals（）を呼び出してequalsをオーバーライドする必要があります（生成されたシリアル番号はデフォルトのequals（）実装と一致しているため）。対応するequals（）オーバーライドなしでhashCode（）オーバーライドを確認すると、コードにレッドフラグが立てられるためです。ツール（および他のプログラマー）に。

public class Vertex
{
private final int                   serial;                                 // instance serial number

public Vertex() {
    serial=nextSerialNumber();
    ...
    }

public int hashCode() {
    return serial;
    }

public boolean equals(Object obj) {
    return super.equals(obj);                                               // serial number hash-code consistent with default equals    
    }

...        

static private int nextSerial=0;
static public synchronized nextSerialNumber() { return nextSerial++; }
}
于 2009-12-03T22:54:41.073 に答える
2

達成しようとしていることに応じて、 UUIDの使用を検討できます...

于 2009-12-03T22:57:30.687 に答える
2

オブジェクトの一意の値を見つけるには、オブジェクトを一意にするプロパティの組み合わせを知る必要があります。

「.contains()」を実行するには、「.equals()」を決定する方法が必要です。これは、頂点を一意に識別する方法を既に知っている必要があるため、一意のプロパティの式を考え出すことができるかもしれません?

例: "(x, y, z, rgb)"

質問を誤解していない限り、この目的でオブジェクトの hashCode をいじることはお勧めしません。

于 2009-12-03T23:02:40.063 に答える
1

ハッシュコードを誤解したと思います。コントラクトに基づいて、equals（..）がtrueの場合、hascodeは同じである必要があり、その逆も同様です。したがって、あなたの場合、同じプロパティを持つ頂点だけが同じhascodeを持つ必要があります。そうでない場合は、自分で作成したhascode計算方法を修正する必要があります。私があなたの質問を理解している限り、頂点自体はユニークなので、問題はないはずですよね？

于 2009-12-04T09:49:58.997 に答える
0

そんなに難しくないですよね？Javaのハッシュアルゴリズムで衝突が保証されない場合は、別のハッシュアルゴリズムを使用してください。オブジェクトをハッシュアルゴリズム（Sha-256など）に送信し、それをキーとして使用します。まったく同じオブジェクトの異なるコピーを異なるハッシュ値で保持する必要がある場合は、ハッシュを実行するときにシードを使用し、これをオブジェクトに関連してハッシュとともに保存します。

于 2009-12-04T09:43:31.603 に答える
0

何をしているのか理解できないかもしれませんが、各オブジェクトへの参照を作成することを検討してください。参照にはオブジェクトのアドレスが含まれているため、オブジェクトごとに一意になります。

于 2009-12-04T09:21:37.337 に答える