Java: ottenere una proprietà unica di un oggetto (come codice hash, ma collisione prova)

Question

Ho un compito per il quale è necessario generare un valore univoco per ogni oggetto in un set. utilizzando il codice hash sarebbe perfetto, se le collisioni non sono stati ammessi nel contratto codice hash.

Un'idea: Registra codice hash di ogni oggetto in un multiset. Quindi, utilizzare codici hash come l'identificatore univoco, ma se questo codice hash è nel set più di una volta, utilizzare un valore diverso che non sia anche nel set. Ma questo si sente ingombranti e scomodi.

un'idea migliore?

Ecco quello che ho già:

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

Modifica Credo che questo non era in origine chiara, ma il numero id fa in qualche modo bisogno di essere un funzione dell'oggetto, perché getVertexName(V) verrà chiamato più volte, e si aspetta che per la stessi valori di V, otterrà gli stessi risultati.

Inoltre, il tipo di Vertex è generico. Quindi non posso apportare modifiche a una classe specifica per risolvere questo problema.

Answer 1

Qual è la durata di questo numero unico? Proprio la durata del programma? In questo caso, perché non solo un contatore statico semplice nella classe, accessibile con la sincronizzazione adatto? Incrementarlo per ogni nuovo oggetto. Non c'è bisogno di tenere un elenco dei valori che avete usato, solo il valore più alto si è utilizzato.

Se unici in molte esecuzioni (e forse molti casi simultanee) allora forse si può semplicemente utilizzare un database che genera ID record unqiue.

A CURA in risposta ad un chiarimento

Il pezzo mi mancava prima era che non siamo in grado di modificare la classe per la quale vogliamo generare l'unico "hash".

Credo che lavorare dal codice hash della classe, che avrà collisioni sta rendendo la vita difficile. Partendo dal presupposto che siamo in grado di contare su classi di vertice in questione hanno eguali correttamente attuate () allora possiamo usare l'oggetto stesso come chiave per l'insieme di codici hash che abbiamo usato.

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

Si potrebbe considerare l'utilizzo di un UUID , a seconda di ciò che si sta cercando di realizzare ...

Answer 3

Per trovare un valore univoco per un oggetto, è necessario conoscere una combinazione di proprietà che rendono l'oggetto unico.

Per eseguire ".contains ()", è necessario disporre di un metodo per determinare ".equals ()", che significa che si dovrebbe già sapere come identificare in modo univoco un vertice, quindi forse si può trovare con un'espressione di le proprietà uniche?

es., "(X, y, z, rgb)"

A meno che io sto equivoco la questione, io non consiglierei pasticciare con hashCode di un oggetto per questo scopo.

Answer 4

Perché non usare un numero di serie?

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

O una combinazione / ibrido, dice un lungo di ((hash << 32) | getNextSerial ()).

Per affrontare il chiarimento EDIT

Quando si costruisce l'oggetto, assegnare il numero di serie per una variabile membro privato e restituirlo per hashCode (). Si dovrebbe quindi ignorare pari con una chiamata a super.equals () (dal momento che un numero di serie generato è coerente con i pari di default () attuazione) perché vedere una sostituzione di hashCode () senza un corrispondente equals () Azionamento volontà bandiera rossa il codice agli strumenti (e gli altri programmatori).

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

I pensi hashcode frainteso. Sulla base del contratto il hascode dovrebbe essere lo stesso quando equals (..) è vera, e viceversa. Quindi nel tuo caso solo un vertice con le stesse proprietà dovrebbero avere lo stesso hascode, altrimenti la vostra auto metodo di calcolo hascode scritto dovrebbe essere risolto. Per quanto ho capito la tua domanda un vertice per sé è unico, quindi non dovreste avere un problema, giusto?

Answer 6

Probabilmente non capisco quello che stai facendo, ma considerare la creazione di un punto di riferimento a ciascun oggetto. Poiché il riferimento contiene l'indirizzo dell'oggetto sarà unico per ogni oggetto.

Answer 7

Non è poi così difficile, è vero? Basta usare un algoritmo hash differente, se quello in Java non garantisce nessuna collisione. Invia l'oggetto alla algoritmo di hash, per esempio Sha-256, e utilizzarla come chiave. Se è necessario mantenere diverse copie esatte stesso oggetto, con differenti valori di hash, utilizzare un seme quando si esegue l'hash, e conservare questo relativo all'oggetto con l'hash.