Map hascode

[MANTA..]

Bonjour à tous,

Je fais appel à vous car je n'arrive pas à comprendre ce que sont les tables de hashage. Je demande car en cour on a fait un exercice java ou il fallait les utilisé et étant donné que je n'ai jamais vue ca je n'ai rien compris, j'ai regardé des cour sur internet mais il y a encore des choses que je ne comprend pas, les voici:

1/ Qu'est ce que c'est une MAP en java?
2/Pourquoi il faut associé une méthode équals à une méthode hashcode?
3/Doit-on toujours implémenter la méthode hashcode?

Voila, merci d'avance pour vos réponses
-----

[invitea0ecda6e]

Une réponse à tes questions sur forum.hardware.fr :

Le hashcode c'est important de savoir à quoi il sert !

sinon, tôt ou tard tu vas te poser de droles de question et passer des journées entères à débugguer !

le hashcode est utilisé pour créér un entier à partir d'un objet.
Le principe de base c'est : si 2 objets sont égaux, ils doivent avior le même hascode.

C'est la règle à respecter quand tu redéfinies a méthode hascode.

Maintenant la question qui tue : "mais à quoi ca sert la méthode hashcode ??"

et la réponse qui tue : c'est utilisé dans les algo de hashage.

par exemple : les HashMap (ou HashTable).
Le principe : associé à des objets Clef des objet Value. Le but étend que la recherche de la valeur à partir de la clef soit rapide.

en interne ca fonctionne à peu près comem ca :
on créé un tableau de Vecteur en mémoire d'une taille T.

quand on souhaite ajouter un couple (clef, valeur), on hash la clef, ce qui nous donne un identifiant. On calcul l'identifiant modulo T, ce qui nous donne un index I dans le tableau, et on ajoute le couple clef-valeur dans le vecteur situé à l'index I du tableau.

Ensuite, quand on recherchera une valeur dans le tableau, à la place de parcourir tout le tableau à la recherche de la clef, on fait la même opération pour trouver l'index, et on cherche la clef dans le vecteur se trouvant à cet index dans le tableau (en utilisant la méthode equals).

(J'espère que j'ai été à peu près clair)

si vous avez bien compris le principe de l'algo des hasmap, vous voyez que c'est important de ne pas faire n'importe quoi avec le hascode : par exemple, si pour un objet qui n'a pas changé d'état, 2 appels à la méthode hashcode ne donne pas le même résultat, on ne le retrouveras jamais dans le HashMap (puisqu'on ne regardera pas au bon index). En plus, si on redéfinit le haschode, il faut quasiment obligatoirement redéfinir le equals ! sinon, on tombera au bon index, mais on ne retrouveras pas l'objets dans le vecteur ...

Un truc qui marche quasi-toujours pour redéfinir le hascode, c'est d'aditionner les hascode de ses attributs. C'est une bonne méthode pour avoir un algo de hashage correct. ex :

    public class Client {
       private String nom, prenom;
     
       public boolean equals (Object o) {
          return this.nom.equals(((Client) o).nom) &&
                 this.prenom.equals(((Client) o).prenom);
       }
       public int hashcode () {
          return nom.hascode() + prenom.hascode();
       }
    }

le problème, c'est que à chaque appel au hascode, on va déclenché l'appel à 2 hashcode de String (qui sont assez lourd).

Pour les petites applis ca passe, mais dans le cas d'EJB par exemple, utiliser masivement cette technique (pour les PrimaryKey) risque d'entrainer un écroulement du serveur !

la plupart du temps, retourner le hashage d'un seul des attributs est suffisant. Bien sur, il faut choisir l'attribut qui aura le plus de chance de renvoyer un hascode différents dans le cas d'objets différents. (si un hascode retourne toujours la même valeur, la recherche dans une Map devient aussi lente (voir plus) qu'une recherche itérative dans un tableau).
Dans le cas idéal, l'objet possède un identifiant unique (ex : id dans la base de donnée) et il suffira de retourner cet entier.

[invite62588872]

Hello,

1/ Qu'est ce que c'est une MAP en java?

Je vais t'expliquer le concept à la place de Google car je m'emmerde au boulot, pour le reste recherche un peu sur le net

Contrairement aux listes, le contenu des maps n'est pas obtenu via un index mais via une clé.

Si tu veux obtenir le Xe élément d'une liste, tu écris quelque chose du style : choutteListe.get(X-1);

Par contre en utilisant une map tu risque plutôt d'écrire quelque chose du style choutteMap.get("uneClé");
A chaque clé est liée une et une seule valeur.

Voici un exemple avec liste et un exemple avec map. Chacune contient des Truc, et un Truc est fait simplement d'un String, qui permet de l'identifier parmi d'autres trucs, rien de plus. Note que j'écris ce code comme ça dans le poste, il faudra être indulgent si je fais une typo (quoique je pense qu'il n'y en aura pas.. heheh)

Truc truc1 = new Truc("truc1");
Truc truc2 = new Truc("truc2");
Truc truc3 = new Truc("truc3");

List<Truc> chouetteListe = new ArrayList<Truc>();
chouetteListe.add(truc1);
chouetteListe.add(truc2);
chouetteList.add(truc3);

Map<String,Truc> chouetteMap = new HashMap<String,Truc>();
chouetteMap.put("premier",truc1);
chouetteMap.put("second",truc2);
chouetteMap.put("dernier",truc3);

Si on part de ce bout de code, et que tu veux accéder à un des objets stockés dans la liste ou dans la map, disons "truc1", tu écrireras ceci :

Truc trucObtenuViaListe = chouetteListe.get(0); // renvoie le premier objet de la liste, et il se fait que c'est le Truc qui a le String "truc1"
Truc trucObtenuViaMap = chouetteMap.get("premier"); // renvoie l'object stocké à la clé "premier" de la map, et il se fait que c'est le Truc qui a le String "truc1"
System.out.println(trucObtenuViaListe.getIdentifiant()); // affichera "truc1" qui est le String stocké dans l'objet truc1
System.out.println(trucObtenuViaMap.getIdentifiant()); // affichera "truc1" qui est le String stocké dans l'objet truc1

Ceci illustre la différence entre l'index et la clé.
Il faut savoir que si ensuite tu remets quelque chose dans chouetteMap en utilisant une clé déjà existante, l'objet courant sera écrasé par le nouveau :

chouetteMap = new HashMap<String,Truc>();
chouetteMap.put("premier",truc1); // on met truc1 à la clé "premier"
chouetteMap.put("premier",new Truc("je suis pas le premier !")); // on écrase ce qu'on vient de mettre
System.out.println(chouetteMap.get("premier").getIdentifiant()); // affichera "je suis pas le premier !"

Il est bon aussi de savoir que la clé d'une Map peut être n'importe quel type d'objet. Ici dans l'exemple j'ai utilisé String comme type de clé (et c'est par hasard qu'un objet truc contienne un String, ces deux String n'ont rien à voir l'un avec l'autre !).

Voilà ça c'est le "grand concept". Les applications sont + que multiples !

Bonne programmation Sur ce je rentre chez moi, j'espère que ça aura servi à quelque chose.

[MANTA..]

MERCI POUR VOS REPONSE, grace a vous j'ai bien compris ce qu'est une table de hachage , il ne me reste plus qu'a comprendre comment faire pour bien redéfinir hashcode et équals. Encore merci à vous deux

[A voir en vidéo sur Futura]

[invite62588872]

MERCI POUR VOS REPONSE, grace a vous j'ai bien compris ce qu'est une table de hachage , il ne me reste plus qu'a comprendre comment faire pour bien redéfinir hashcode et équals. Encore merci à vous deux

Content d'avoir servi à quelque chose Pour hashcode et equals le net t'expliquera ça bien en détails. Note que ça n'a rien d'effrayant

[MANTA..]

Effectivement, je pense avoir à peu près compris ce que c'est