Java: erhält eine einzigartige Eigenschaft eines Objekts (wie hashcode, aber Kollision fest)

Question

Ich habe eine Aufgabe, für die es notwendig ist, einen eindeutigen Wert für jedes Objekt in einem Satz zu erzeugen. den Hash-Code mit wäre perfekt, wenn Kollisionen nicht im hashcode Vertrag erlaubt war.

Eine Idee: Nehmen Sie jedes Objekt hashcode in eine multiset. Verwenden Sie dann Hashcodes als eindeutige Kennung, aber wenn der Hash-Code in der Menge mehr als einmal ist, einen anderen Wert verwenden, auch nicht in der Menge ist. Aber das fühlt sich sperrig und umständlich.

Bessere Ideen?

Hier ist, was ich bereits:

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;
    }
}

EDIT: Ich denke, das ursprünglich nicht klar war, aber die ID-Nummer muss irgendwie eine Funktion des Objekts sein, weil getVertexName(V) wird mehrmals aufgerufen, und es erwartet, dass für die gleiche Werte von V, wird es die gleichen Ergebnisse erhalten.

Auch ist der Vertex Typ generisch. So kann ich keine Änderungen an einer bestimmten Klasse machen, dies zu beheben.

Answer 1

Was ist die Lebensdauer dieser einzigartigen Nummer? Nur die Laufzeit des Programms? In diesem Fall, warum nicht nur ein einfachen statischen Zähler in der Klasse, mit geeigneter Synchronisation zugegriffen? Erhöhe es für jedes neue Objekt. Keine Notwendigkeit, eine Liste der Werte zu halten, die Sie verwendet haben, nur den höchsten Wert, den Sie verwendet haben.

Wenn einzigartig in vielen Ausführungen (und vielleicht viele gleichzeitige Instanzen), dann können Sie vielleicht nur eine Datenbank verwenden, die ids unqiue Datensatz erzeugt.

EDITED als Reaktion auf Klarstellung

Das Stück, das ich vor gefehlt hat, war, dass wir die Klasse nicht ändern können, für die wir die einzigartige „hash“ generieren möchten.

Ich denke, dass aus dem Hash-Code der Klasse arbeiten, die Kollisionen werden müssen, ist das Leben hart. Unter der Annahme, dass wir uns auf den Vertex-Klassen in Frage verlassen können korrekt umgesetzt equals mit (), dann können wir das Objekt selbst als Schlüssel zu dem Satz von Hashcodes wir verwendet haben, verwendet werden.

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;
            }
        };
    }
}

Answer 2

Sie könnten prüfen, mit einem UUID , je nachdem, was Sie versuchen zu erreichen ...

Answer 3

Um einen eindeutigen Wert für ein Objekt zu finden, Sie haben eine Kombination von Eigenschaften zu wissen, dass das Objekt einzigartig machen.

„.contains ()“ ausführen zu können, müssen Sie ein Verfahren haben, der Bestimmung „.equals ()“, was bedeutet, sollten Sie bereits wissen, wie man eindeutig ein Vertex zu identifizieren, so können Sie vielleicht mit einem Ausdruck kommen von die einzigartigen Eigenschaften?

z. B. "(x, y, z, RGB)"

Wenn ich die Frage bin Missverständnis, ich würde nicht mit einer Objekt hashCode für diesen Zweck empfehlen Ausmisten.

Answer 4

Warum nicht einfach eine Seriennummer verwenden?

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

oder eine Kombination / Hybrid, sagt eine lange von ((Hash << 32) | getNextSerial ()).

, um die EDIT Klärung adressieren

Wenn Sie das Objekt konstruieren, die Seriennummer zu einem privaten Membervariable zuweisen und senden Sie es für hashCode (). Sie sollten dann gleich mit einem Aufruf an super.equals () überschreiben (da eine generierte Seriennummer ist mit den Standard equals konsistent () Implementierung), da ohne entsprechende equals eine hashCode () überschreiben zu sehen () überschreiben rot-Flagge der Code zu Werkzeugen (und andere Programmierer).

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++; }
}

Answer 5

Ich glaube, du falsch verstanden hashcode. Auf der Grundlage des Vertrages sollte die hascode gleich sein, wenn equals (..) wahr ist und vice versa. Also in Ihrem Fall nur eine Ecke mit den gleichen Eigenschaften sollen die gleichen hascode haben, sonst wird Ihre selbst geschriebene hascode Berechnungsmethode festgelegt werden soll. Soweit ich Ihre Frage eine Ecke für sich selbst verstanden haben, ist einzigartig, so dass Sie nicht ein Problem haben sollte, nicht wahr?

Answer 6

ich wahrscheinlich nicht verstehen, was Sie tun, aber bedenken Sie Erstellen eines Verweises für jedes Objekt. Da die Referenz der Adresse des Objekts enthält, wird es sein, einzigartig für jedes Objekt.

Answer 7

Es ist nicht so schwer, oder? Verwenden Sie einfach einen anderen Hash-Algorithmus, wenn der eine in Java nicht, dass keine Kollisionen garantiert. Sendet das Objekt in dem Hash-Algorithmus, z.B. Sha-256, und verwendet, die als Schlüssel. Wenn Sie verschiedene Kopien von exakt gleichen Objekt zu halten, mit unterschiedlichen Hash-Werte, verwenden Sie einen Samen, wenn Sie den Hash ausführen und speichern diese im Zusammenhang mit dem Objekt mit dem Hash.