Java: obtenir une propriété unique d'un objet (comme hashcode, mais la preuve de collision)

Question

J'ai une tâche pour laquelle il est nécessaire de générer une valeur unique pour chaque objet dans un ensemble. en utilisant le hashcode serait parfait, si les collisions ne sont pas autorisés dans le contrat de hashcode.

Une idée: Record hashcode de chaque objet dans un multiset. Ensuite, utilisez hashcodes comme identifiant unique, mais si ce hashcode est dans l'ensemble plus d'une fois, utilisez une autre valeur qui est pas non plus dans l'ensemble. Mais cela se sent encombrant et maladroit.

De meilleures idées?

Voici ce que je l'ai déjà:

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: Je suppose que cela n'a pas été à l'origine claire, mais le numéro d'identification ne doit en quelque sorte être fonction de l'objet, parce que getVertexName(V) sera appelé à plusieurs reprises, et il prévoit que la mêmes valeurs de V, il obtiendra les mêmes résultats.

En outre, le type Vertex est générique. Je ne peux pas apporter des modifications à une classe spécifique pour résoudre ce problème.

Answer 1

Quelle est la durée de vie de ce numéro unique? Juste la durée de vie du programme? Dans ce cas, pourquoi ne pas simplement un simple compteur statique dans la classe, accessible avec la synchronisation appropriée? Incrémenter pour chaque nouvel objet. Pas besoin de garder une liste des valeurs que vous avez utilisé, juste la valeur la plus élevée que vous avez utilisé.

Si uniques dans de nombreuses exécutions (et peut-être de nombreux cas simultanés) alors peut-être vous pouvez simplement utiliser une base de données qui génère ids record unqiue.

EDITED en réponse à la clarification

La pièce que j'ai raté avant était que nous ne pouvons pas modifier la classe pour laquelle nous voulons générer l'unique « hachage ».

Je pense que le travail à partir du code de hachage de la classe, ce qui aura des collisions rend la vie dure. En supposant que nous pouvons compter sur les classes Vertex en question ayant égaux correctement mis en œuvre () alors nous pouvons utiliser l'objet lui-même comme une clé pour l'ensemble des hashcodes que nous avons utilisé.

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

Vous pouvez envisager d'utiliser un UUID , en fonction de ce que vous essayez d'accomplir ...

Answer 3

Pour trouver une valeur unique pour un objet, vous devez savoir une combinaison de propriétés qui font l'objet unique.

Pour exécuter « .contains () », vous devez avoir une méthode de détermination « equals () », ce qui signifie que vous devez déjà savoir comment identifier un Vertex, vous pouvez peut-être venir avec une expression de les propriétés uniques?

par ex., "(X, y, z, rgb)"

À moins que je suis malentendu à la question, je ne recommanderais pas déblayage avec hashCode d'un objet à cet effet.

Answer 4

Pourquoi ne pas simplement utiliser un numéro de série?

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

Ou une combinaison / hybride, par exemple une longue ((dièse << 32) | getNextSerial ()).

Pour répondre à la clarification EDIT

Lorsque vous construisez l'objet, attribuer le numéro de série à une variable de membre privé et le retourner pour hashCode (). Vous devez alors passer outre égal à égal avec un appel à super.equals () (depuis un numéro de série généré est compatible avec la mise en œuvre par défaut égaux ()) parce qu'en voyant une dérogation hashCode () sans surchargent equals correspondant () sera drapeau rouge le code aux outils (et autres programmeurs).

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

Je pense que vous hashcode mal compris. Sur la base du contrat, le hascode doit être le même quand égaux (..) est vrai et vice versa. Donc, dans votre cas, seul un sommet avec les mêmes propriétés devraient avoir le même hascode, sinon votre auto écrite méthode de calcul de hascode doit être fixé. Pour autant que je l'ai bien compris votre question un sommet pour lui-même est unique, donc vous ne devriez pas avoir un problème, non?

Answer 6

Je ne comprends pas probablement ce que vous faites, mais envisager de créer une référence à chaque objet. Étant donné que la référence contient l'adresse de l'objet, il sera unique pour chaque objet.

Answer 7

Il est pas si difficile, est-il? Il suffit d'utiliser un algorithme de hachage différent, si celui en Java ne garantit pas aucune collision. Envoyer l'objet à l'algorithme de hachage, par exemple Sha-256, et l'utiliser comme la clé. Si vous avez besoin de garder différentes copies de même objet exact, avec des valeurs de hachage différentes, utilisez une graine lorsque vous effectuez le hachage, et stocker ce lié à l'objet avec le hachage.