Prob hashmap -> valeur associée à une clé changeante

Prob hashmap -> valeur associée à une clé changeante - Java - Programmation

Marsh Posté le 18-01-2007 à 15:44:09    

Bonjour,
 
Je sais que vu le titre cela n'est pas très explicite, je vais essayer de vous détailler mon problème.
Tout cela correspond à un programme qui doit donner le plus court chemin entre deux sommets d'un graphe valué .
 
Ma structure est ceci :

Code :
  1. private HashMap<Sommet,TreeSet<Arc>> graphe;


J'ai donc une classe Sommet qui contient :  
 

Code :
  1. private String nom;
  2. private int plusCourt; // valuation associé au sommet


Et une classe Arc :
 

Code :
  1. private Sommet arrivee;
  2. private int poids;


J'ai crée tous les sommets et tous les arcs. J'ai entré dans la hashmap pour chaque sommet les arcs associés.
Tout cela fonctionne à merveille !
 
Maintenant je souhaite modifier l'attribut plusCourt pour tous les sommets contenus dans le hashmap.
 

Code :
  1. for(Sommet s: graphe.keySet()){
  3.   if(s.getNom()==depart)
  4.   {
  5.    sommetDepart = s;
  6.    s.setPlusCourt(0);
  8.   }
  9.   else
  10.   {
  11.    s.setPlusCourt(3000);
  12.   }
  13.  }


 
Et en fait après avoir executé ce code, lorsque je parcours toutes les clés pour afficher la valeur, je n'ai que des null ?!? Logiquement si je modifie une clé elle devrait garder sa valeur associé dans le hashmap ?
 
Merci de m'éclairer la dessus.
 
Louis

Reply

Marsh Posté le 18-01-2007 à 15:44:09   

Reply

Marsh Posté le 18-01-2007 à 16:17:29    

t'utilises quoi par hasard comme hashCode ?

Reply

Marsh Posté le 18-01-2007 à 16:24:08    

justement le hashcode est définie grace aux deux attributs :
 

Code :
  1. public int hashCode() {
  2.         // On choisit les deux nombres impairs
  3.         int result = 7;
  4.         final int multiplier = 17;
  5.        
  6.         // Pour chaque attribut, on calcule le hashcode
  7.         // que l'on ajoute au résultat après l'avoir multiplié
  8.         // par le nombre "multiplieur" :
  9.         result = multiplier*result + nom.hashCode();
  10.         result = multiplier*result + ((Integer)plusCourt).hashCode();
  11.        
  12.         // On retourne le résultat :
  13.         return result;
  14.     }


 
il s'agit d'un hashcode trouvé sur le net que j'ai adapté avec mes attributs.

Message cité 1 fois
Reply

Marsh Posté le 18-01-2007 à 17:24:37    

donc tu comprends bien le problème si le hashCode de ton instance est changeant ...

Reply

Marsh Posté le 18-01-2007 à 17:29:19    

allserv a écrit :

justement le hashcode est définie grace aux deux attributs :
 

Code :
  1. public int hashCode() {
  2.         // On choisit les deux nombres impairs
  3.         int result = 7;
  4.         final int multiplier = 17;
  5.        
  6.         // Pour chaque attribut, on calcule le hashcode
  7.         // que l'on ajoute au résultat après l'avoir multiplié
  8.         // par le nombre "multiplieur" :
  9.         result = multiplier*result + nom.hashCode();
  10.         result = multiplier*result + ((Integer)plusCourt).hashCode();
  11.        
  12.         // On retourne le résultat :
  13.         return result;
  14.     }


 
il s'agit d'un hashcode trouvé sur le net que j'ai adapté avec mes attributs.


 
Les hashCode() ne doivent par varier tant que les objets sont utilisés comme clefs, sinon le comportement de la HashMap est indéterminé. Ici la valeur du noeud ne l'identifie pas du tout, j'imagine. Ce qui identifie ton noeud, c'est l'attribut "nom". Enfin, j'espère que cet attribut ne varie pas au cours du temps. Renvoie simplement nom.hashCode() et pense à implémenter le equals() de la même manière.
 
Dans la Javadoc 1.5 de java.lang.Objet.hashCode() :
 
*  Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
* If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
* It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.  

Reply

Marsh Posté le 18-01-2007 à 18:30:53    

Merci ca fonctionne parfaitement;)
 
 
Un autre petit problème tout bete mais dont je ne trouve pas la solution
 
Dans mon TreeSet d'arc, lorsque j'ai deux Arc différents mais avec le meme poids, le dernier arc n'est pas ajouté :

Code :
  1. Arc AB = new Arc(B,1);
  2. Arc AD = new Arc(D,2);
  3. Arc AC = new Arc(C,1);
  5. monGraphe.ajoutArc(A,AB);
  6. monGraphe.ajoutArc(A,AD);
  7. monGraphe.ajoutArc(A,AC);


 
Dans cet exemple je n'ai pas l'arc AC par exemple !
 
Pourtant j'ai defini le hashcode sur le sommet d'arrivée qui diffère donc devrait pas y avoir de problème :

Code :
  1. public int hashCode() {
  2.         return arrivee.hashCode();
  3.  }
  5.  public boolean equals(Arc monArc){
  6.   return (monArc.arrivee.equals(this.arrivee) && monArc.getPoids()==this.poids);
  7.  }


 
Et le hashcode du sommet est :

Code :
  1. public int hashCode() {
  2.        return nom.hashCode();
  3.     }
  5.  public boolean equals(Sommet otre){
  6.   return otre.getNom().equals(this.nom);
  7.  }


 
Comment faire pour résoudre ce dernier problème ?
 
Je te remercie encore pour tes reponses

Reply

Marsh Posté le 18-01-2007 à 18:46:08    

et ajoutArc c'est quoi ? et toi tu compares deux arcs uniquement avec un sommet et son poids ? donc AC(3) et BC(3) c'est le même arc ?

Reply

Marsh Posté le 18-01-2007 à 19:08:37    

Ah ouais c'est vrai ca, je viens de rajouter un attribut dans la class Arc :
private Sommet depart  
 
J'ai redefini les methodes hashcode et equals :

Code :
  1. public int hashCode() {
  2.         return depart.hashCode()+arrivee.hashCode();
  3.  }
  5.  public boolean equals(Arc monArc){
  6.   return (monArc.depart.equals(this.depart) && monArc.arrivee.equals(this.arrivee) && monArc.getPoids()==this.poids);
  7.  }


 
Le problème est que ca ne me resouds pas mon prob ! :(
 
Merci encore

Message cité 1 fois
Reply

Marsh Posté le 18-01-2007 à 21:30:21    

allserv a écrit :

Ah ouais c'est vrai ca, je viens de rajouter un attribut dans la class Arc :
private Sommet depart  
 
J'ai redefini les methodes hashcode et equals :

Code :
  1. public int hashCode() {
  2.         return depart.hashCode()+arrivee.hashCode();
  3.  }
  5.  public boolean equals(Arc monArc){
  6.   return (monArc.depart.equals(this.depart) && monArc.arrivee.equals(this.arrivee) && monArc.getPoids()==this.poids);
  7.  }


 
Le problème est que ca ne me resouds pas mon prob ! :(
 
Merci encore


 
1) Es-tu bien sûr que tu n'auras jamais 2 arcs distincts joignant les mêmes sommets A et B, avec le même poids ? Tout dépend du problème que tu veux résoudre avec ton graphe, mais dans certains applis c'est possible. Dans ce cas, tu dois rajouter un identifiant à tes arcs (comme un String nom).  
2) Le hashCode n'intervient que quand l'objet est clé dans une HashMap, éléments d'HashSet, etc.
3) Là tu as un TreeSet. Les TreeSet utilisent la fonction compareTo() pour ranger leurs éléments. Tu as dû déclarer que Arc implémentait l'interface Comparable, non ? Donc s'il y a un problème, il vient du compareTo(), je pense ;
4) Comme dit Taz, si tu ne nous donnes pas le code de la méthode "ajoutArc", on est mal barrés.
 
Pour 2) et 3) je t'aurais bien dit "lis la doc, nom de Dieu !", mais je dois avouer que je n'ai pas trouvé de page chez Sun qui résume clairement ce genre d'infos.
 

Reply

Marsh Posté le 19-01-2007 à 13:14:32    

Oui en effet cela venait bien du compareTo qui etait fait sur le poids et si le poids etait le même il jne le rentrait pas.
 
Merci pour vos réponses
 
@+

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed