Java: obtener una propiedad única de un objeto (como código hash, pero la prueba de colisión)

Question

Tengo una tarea para la que es necesario generar un valor único para cada objeto en un conjunto. utilizando el código hash sería perfecto, si las colisiones no estaban permitidos en el contrato código hash.

Una idea: Grabar código hash de todos los objetos en un conjunto múltiple. A continuación, utilice hashcodes como el identificador único, pero si que hashcode está en el conjunto más de una vez, utilizar un valor diferente que también no está en el conjunto. Pero esto se siente voluminosos y difíciles.

mejores ideas?

Esto es lo que ya tengo:

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: supongo que esto no era originalmente clara, pero el número de identificación lo hace de alguna manera tengo que estar en función del objeto, porque getVertexName(V) será llamado varias veces, y se espera que para el mismos valores de V, se obtendrán los mismos resultados.

Además, el tipo de vértice es genérico. Así que no puedo hacer cualquier modificación a una clase específica de solucionar este problema.

Answer 1

¿Cuál es la vida útil de este número único? Justo el tiempo de vida del programa? En cuyo caso, ¿por qué no un contador estático simple en la clase, se accede con la sincronización adecuada? Se incrementará para cada nuevo objeto. No hay necesidad de mantener una lista de los valores que se han utilizado, sólo el valor más alto que se haya utilizado.

Si únicas a través de muchas ejecuciones (y tal vez muchos casos simultáneos) entonces tal vez sólo puede utilizar una base de datos que genera ID de registros unqiue.

editar en respuesta a la aclaración

La pieza echaba de menos era antes de que no podemos modificar la clase para la que queremos generar el único "control".

Creo que trabajar desde el código hash de la clase, que tendrá colisiones está haciendo la vida difícil. Suponiendo que podemos confiar en las clases vértice en cuestión tienen iguales realizado correctamente () entonces podemos utilizar el objeto en sí mismo como una clave para el conjunto de hashcodes que hemos utilizado.

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

Se podría considerar el uso de un UUID , dependiendo de lo que está tratando de lograr ...

Answer 3

Para encontrar un valor único para un objeto, usted tiene que saber una combinación de propiedades que hacen que el objeto único.

Para ejecutar ".contains ()", es necesario tener un método para determinar ".equals ()", lo que significa que ya debe saber cómo identificar de forma exclusiva un vértice, por lo que tal vez se puede llegar a una expresión de las propiedades únicas?

por ejemplo., "(X, y, z, rgb)"

A menos que me no entender la pregunta, yo no recomendaría limpiando con hashCode de un objeto para este propósito.

Answer 4

¿Por qué no utilizar un número de serie?

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

O una combinación / híbrido, dice mucho de ((almohadilla << 32) | getNextSerial ()).

Para hacer frente a la aclaración editar

Cuando se crea el objeto, asignar el número de serie a una variable miembro privada y devolverlo para hashCode (). A continuación, debe reemplazar a igual con una llamada a super.equals () (desde un número de serie generado es consistente con los iguales (por defecto) de aplicación) porque ver una anulación de hashCode () sin su correspondiente equals () aumento de presupuesto de bandera roja del código a herramientas (y otros programadores).

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

Creo que hashcode mal entendido. Con base en el contrato la hascode debe ser el mismo cuando los iguales (..) es verdadero y viceversa. Así, en su caso, sólo un vértice con las mismas propiedades deben tener los mismos hascode, de lo contrario su método de cálculo hascode escrita auto debe fijarse. Por lo que yo he entendido su pregunta un vértice por sí mismo es único, por lo que no debería haber un problema, ¿verdad?

Answer 6

Probablemente no entiendo lo que está haciendo, pero considerar la creación de una referencia para cada objeto. Dado que la referencia contiene la dirección del objeto que será único para cada objeto.

Answer 7

No es tan difícil, ¿verdad? Sólo tiene que utilizar un algoritmo de hash diferente, si el uno en Java no garantiza ninguna colisión. Enviar el objeto con el algoritmo de hash, por ejemplo, SHA-256, y usar eso como la clave. Si usted necesita para mantener diferentes copias de exactamente el mismo objeto, con diferentes valores de hash, utilice una semilla cuando se realiza el hash, y almacenar esta relacionado con el objeto con el hash.