ジャバ:オブジェクトの一意のプロパティを取得します (ハッシュコードなどですが、衝突防止)
質問
セット内のすべてのオブジェクトに対して一意の値を生成する必要があるタスクがあります。ハッシュコード コントラクトで衝突が許可されていなければ、ハッシュコードを使用するのが完璧です。
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
, 、同じ結果が得られます。
また、Vertex タイプは汎用です。したがって、これを修正するために特定のクラスを変更することはできません。
解決
この固有の番号の有効期間はどれくらいですか?プログラムの存続期間だけですか?この場合、適切な同期を使用してアクセスできるクラス内の単純な静的カウンターを使用しないのはなぜでしょうか。新しいオブジェクトごとに増加します。使用した値のリストを保持する必要はなく、使用した最高値のみを保持します。
多数の実行 (およびおそらくは多数の同時インスタンス) にわたって一意である場合は、おそらく、一意のレコード ID を生成するデータベースを使用するだけで済みます。
説明に応じて編集されました
以前見逃していた部分は、一意の「ハッシュ」を生成したいクラスを変更できないということでした。
衝突が発生するクラスのハッシュ コードから作業するのは大変なことだと思います。問題の Vertex クラスが、equals() を正しく実装していることに依存できると仮定すると、オブジェクト自体を、使用したハッシュコードのセットのキーとして使用できます。
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;
}
};
}
}
他のヒント
の使用を検討できます。 UUID, 、何を達成しようとしているかによって異なります...
オブジェクトの一意の値を見つけるには、オブジェクトを一意にするプロパティの組み合わせを知る必要があります。
「.contains()」を実行するには、「.equals()」を決定するメソッドが必要です。つまり、頂点を一意に識別する方法をすでに知っている必要があるため、一意のプロパティの式を思いつくことができるかもしれません。 ?
例: "(x, y, z, rgb)"
私が質問を誤解していない限り、この目的でオブジェクトの hashCode をいじることはお勧めしません。
なぜシリアル番号を使用しないのでしょうか?
static private int serial=0;
static public synchronized nextSerialNumber() { return ++serial; }
または、組み合わせ/ハイブリッド、たとえば、long of ((hash<<32) | getNextSerial())。
編集の明確化に対処するには
オブジェクトを構築するときに、シリアル番号をプライベート メンバー変数に割り当て、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++; }
}
ハッシュコードを誤解しているようです。契約に基づいて、equals(..) が true の場合、およびその逆の場合、hascode は同じである必要があります。したがって、あなたの場合、同じプロパティを持つ頂点のみが同じhascodeを持つ必要があります。そうでない場合は、自分で作成したhascode計算方法を修正する必要があります。私があなたの質問を理解した限りでは、頂点はそれ自体が一意であるため、問題はないはずですよね?
私はおそらくあなたが何をしているのか理解していませんが、各オブジェクトへの参照を作成することを検討してください。参照にはオブジェクトのアドレスが含まれているため、各オブジェクトに対して一意になります。
そんなに難しくないですよね?Java のハッシュ アルゴリズムでは衝突がないことが保証されない場合は、別のハッシュ アルゴリズムを使用してください。オブジェクトをハッシュ アルゴリズムに送信します。Sha-256、それをキーとして使用します。まったく同じオブジェクトの異なるコピーを異なるハッシュ値で保持する必要がある場合は、ハッシュを実行するときにシードを使用し、これをハッシュを持つオブジェクトに関連付けて保存します。