Discussion :

[BakaOnigiri]

Bonjour,

pour un projet, j'ai besoin de générer un identifiant unique (de type int) en fonction de 3 paramètres (3 entiers).


Pour cela, j'ai utilisé la génération automatique de code de netbeans (quand il génère le code pour la méthode hashCode.

Voici donc le code généré :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
@Override
public int hashCode()
{
    int hash = 5;
    hash = 53 * hash + this.typeOperation;
    hash = 53 * hash + this.typeObjet;
    hash = 53 * hash + this.idObjet;
    return hash;
}

Or, par acquis de conscience, et histoire de m'initier aux tests unitaire, j'ai fait un test pour voir ci c'était vraiment unique (pour typeOperation allant de 0 à 10, typeObjet allant de 0 à 40 et idObjet allant de 0 à 9999)

Or, si on prend :

typeOperation = 0 - typeObjet = 0 - idObjet = 53, hashCode = 744438

mais si on prend :

typeOperation = 0 - typeObjet = 1 - idObjet = 0, alors hashCode vaut aussi 744438.

Donc le hashCode n'est pas exactement ce que je cherche, ou alors est mal codé.

En fait hashCode n'est pas ce que je veux, vu que çà doit être utilisé avec equals() et donc je gère pas l'ordre des opérateurs.

Quel code je doit coder pour avoir un vrai identifiant unique en fonction de ces 3 paramètres et de l'ordre de ces paramètres ?

Merci

[nouknouk]

pour un projet, j'ai besoin de générer un identifiant unique (de type int) en fonction de 3 paramètres (3 entiers)

Il faut commencer par voir si l'information stockée par tes trois entiers est stockable dans un int (donc un mot de 32 bits).

Par exemple:
- entier n°1 : nombre entre 0 et 16
- entier n°2 : nombre entre 0 et 256
- entier n°3 : nombre entre 0 et 60 000

=> total = 16 * 256 * 60 000 = 245 760 000 combinaisons.
=> on peut le faire rentrer dans un 'int' qui peut stocker 2^32 combinaisons.

Si c'est ton cas, en nous donnant plus d'infos sur les entiers en entrée on devrait pouvoir te guider.

Mais si ton total fait plus de 2^32, soit il faudra choisir un autre type d'identifiant (un 'long' qui code sur 64 bits, un String, ...), soit tu ne pourras pas garantir que pour une combinaison des trois entiers tu auras un identifiant unique.
Ce serait en effet vouloir stocker x possibilités différentes dans un espace qui ne peut pas en adresser autant (2^32 dans le cas d'un int).

EDIT:

pour typeOperation allant de 0 à 10, typeObjet allant de 0 à 40 et idObjet allant de 0 à 9999

Désolé, j'avais raté cette phrase là

Donc vu q'on a toutes les infos, on peut faire le calcul:
Là on a 11 * 41 * 10000 = 4 510 000 possibilités.
Ca rentre largement dans un int (2^32 = 4 294 967 296 possibilités).

Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
public int hashCode()
{
    int hash = idObjet + (typeOperation * 10000) + (typeObjet * 10000 * 11);
    return hash;
}
 
// (10000 * 11) est évidemment à remplacer par 110000, c'était juste pour la démarche.

Ce hash là est garanti 100% unique (et sans OGM )

[zorm]

Bonjour,

Je pense que ton problème n'est pas simple dans la mesure où tu ne seras jamais en mesure de prouver qu'il n'existe pas 2 combinaisons de tes entiers qui peuvent donner le même identifiant en passant par une formule de génération. En te basant sur la méthode de hashage, tu peux diminuer les risques en utilisant des multiplicateurs générés aléatoirement. Le nouveau problème que ça pose est que pour 2 instances avec le même paramètrage, il est fortement improbable que tu retrouves le même id.
Sinon, tu peux aussi tenir une table des id => parametres et faire évoluer éventuellement la valeur du hash si jamais tu retrouves un id déjà utilisé

Bon courage en tout cas :p

[nouknouk]

Je pense que ton problème n'est pas simple dans la mesure où tu ne seras jamais en mesure de prouver qu'il n'existe pas 2 combinaisons de tes entiers qui peuvent donner le même identifiant en passant par une formule de génération.

=> pour les trois paramètres qu'il a donnés, et qui sont bornés à des valeurs de 10, 40 et 10 000, c'est tout à fait faisable puisque l'ensemble des possibles est inférieur à 2^32 (le nombre de valeurs différentes stockables par un int), mon code ci-dessus garantit l'unicité de chaque hash (qui du coup n'est d'ailleurs plus vraiment un 'hash' formellement parlant).

[BakaOnigiri]

En effet, merci beaucoup nouknouk, ton code fonctionne niquel, j'avais pensé à faire un truc du genre.

Et çà valide mon premier test unitaire qui passe

Par contre comme t'es venu la valeur 1000 * 11 ?

(j'ai la flemme de me creuser la tête )

[nouknouk]

Par contre comme t'es venu la valeur 1000 * 11 ?

- 10 000 (et pas 1 000!) c'est le nombre de possibilités pour ta variable idObjet (0-9999)
- 11 c'est le nombre de possibilités pour ta variable typeOperation (0-10)

1/ L'idée est qu'on stocke d'abord idObjet et pour chacun de ceux-ci il occupera les quatre derniers chiffres (0 à 9999)

2/ Donc la variable suivante à stocker devra commencer au 5ème chiffre (10 000 et plus). Donc en multipliant par 10 000, on s'assure de n'avoir que des valeurs pour typeOperation comprises entre 10 000 et 100 000

3/ Même réflexion pour la dernière variable: tous les nombres entre 0 et 109 999 sont déjà pris par idObjet et typeOperation . Pour coder typeObjet, on commence donc à 110 000, d'où la multiplication par (10 000 * 11).

[Astartee]

Donc le hashCode n'est pas exactement ce que je cherche, ou alors est mal codé.

Je ne sais pas ce que tu cherchais, mais ici ton hascode est clairement égal à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

53^3*5 + 53^2*typeOperation + 53*typeObjet + idObjet

Je ne sais pas pourquoi tu as choisi cette fonction, mais elle n'est clairement pas injective sur l'ensemble de définition du triplet (typeOperation, typeObjet, idObjet) que tu nous as donné.
Tu n'avais même pas besoin de faire des tests unitaires sur ton programme pour t'en rendre compte, le contre-exemple que tu nous donnes était trouvable immédiatement à la main.

Il faut donc choisir une autre fonction, qui donne effectivement un identifiant unique pour chaque triplet (typeOperation, typeObjet, idObjet).
Eeeet... je n'ai même pas besoin de t'en donner un exemple puisque nouknouk l'a déjà fait en éditant son message
EDIT il y a même 4 autres messages qui sont apparus depuis que j'ai commencé à écrire

[BakaOnigiri]

oui tout a fait, j'ai utilisé, par flemme du moment, la fonction de génération de hash de netbeans.

Qui fait bien son travail, çàd donner une valeur identique pour 3 valeurs identiques, mais pas de valeur unique.

J'ai utilisé une fonction pour ce pourquoi elle n'est pas prévue.


Merci beaucoup.

[nouknouk]

A noter que comme ta valeur retournée n'est pas seulement un hash mais contient bien l'ensemble des combinaisons possibles, il existe une fonction inverse te permettant à partir du seul hash de récupérer les valeurs de chacune de tes trois variables:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
    int hash = ... // le hash en entrée
 
    int idObjet = hash %10000;
    int typeOperation = (hash / 10000) % 11;
    int typeObjet = hash / 110000;

[adiGuba]

Salut,

Donc le hashCode n'est pas exactement ce que je cherche, ou alors est mal codé.

Il n'est pas mal codé, même si ce n'est pas forcément optimisé pour ton cas précis. La méthode hashCode() ne correspond pas à ce que tu veux, car son objectif est de fournir une valeur permettant de dispatcher les objets différents, afin d'améliorer la recherche dans une Map.

Mais rien ne garantit que deux objets différents aient forcément un hashCode différent.

En fait il faut que le couple hashCode/equals respecte les règles suivantes :

1. Si deux objets ont un hashCode différent, alors ces objets sont forcément différents.
2. Si deux objets sont égaux, alors ils ont obligatoirement le même hashCode.
3. Si deux objets ont le même hashCode, alors ils sont potentiellement égaux (il faut vérifier cela avec equals).

Le problème c'est qu'on ne peut pas représenter de manière unique toutes les possibilités de 3 int avec un seul int (à moins d'inventer un nouveau moyen de compression extraordinaire).

Mais dans ton cas la valeur de tes entiers sont limité, donc c'est possible et la manière la plus simple est de générer un int de la forme 00000000 :

• 00 : typeOperation allant de 0 à 10
• 00 : typeObjet allant de 0 à 40
• 0000 : idObjet allant de 0 à 9999

Ce qui se fait assez facilement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

return typeOperation*1000000 + typeObjet*10000 + idObjet;

Et si ces 3 champs représentent l'identité de ton objet, tu peux très bien utiliser cela comme hashCode() : il sera alors bien mieux optimisé pour ton type car il n'y aura aucun conflit

a++

[edit] Il y a eu plein de réponse entre temps...