Map:Clé composé de deux String

Version imprimable

23/05/2006, 14h53
progamer54

Map:Clé composé de deux String

Bonjour,

je suis sur un projet java ou je fais une HashMap qui au couple (chaine1, chaine2) rend une valeur (un double).

J'aimerai implanter la meilleure structure possible. J'hésite entre:

-1: Une clé multiple composée des deux chaines (si c'est possible...)

-2: UNe clé objet (l'objet qui a en attribut les deux chaines), si c'est possible...

-3; je concaténe les deux chaines en une seule pour faire la clé.

Quel est votre avis ? Merci d'avance
23/05/2006, 14h57
KiLVaiDeN

Mon avis :

:arrow: Solution propre, mais moins performante : Un objet clé composé de tes chaines qui redéfinie les méthodes nécessaires à la comparaison et aux tris ( si nécessaire ). Implique la création de multiples objets clés.

:arrow: Solution moins propre, mais performante : Concaténation :)

Je penche en général vers les solutions plus performante quand le design de l'application ne se voit pas trop perturbé; donc en l'occurence je choisirais la concaténation :) Cependant attention, il faut mettre un délimiteur..

Clé String 1 : Attention
Clé String 2 : AuxDelimiteurs

et

Clé String 1 : AttentionAux
Clé String 2 : Delimiteurs

Ne doivent pas pointer sur le même objet normalement non ? Enfin attention à ça :) A+
23/05/2006, 15h11
Logan Mauzaize

Et un Map<String, Map<String,Double> > ? :aie:

Qui a dit sauvage ?_?
23/05/2006, 15h12
adiGuba

Salut,

Citation:

Envoyé par progamer54

-1: Une clé multiple composée des deux chaines (si c'est possible...)

Que veux-tu dire par là exactement ?

Citation:

Envoyé par progamer54

-2: UNe clé objet (l'objet qui a en attribut les deux chaines), si c'est possible...

C'est la meilleure solution. Il faut bien sûr que cet objet implémente correctement les méthode equals() et hashcode()...

Citation:

Envoyé par progamer54

-3; je concaténe les deux chaines en une seule pour faire la clé.

Dans ce cas tu ne pourras pas différencier certaines clef. Par exemple le couple ("AB","CD") sera identique au couple ("A","BCD") puisque les deux donneront "ABCD".
Bien sur cela dépend de tes besoins...

a++

Quel est votre avis ? Merci d'avance[/quote]
23/05/2006, 15h12
progamer54

OK.Merci

Pourrais m'indiquer comment faire une Map dont la clé est un objet?
23/05/2006, 15h13
KiLVaiDeN

Un Map contenant un autre Map alors que tu peux tout faire avec un seul Map : c'est pas très conseillé :mouarf:

Citation:

Envoyé par progamer54

-1: Une clé multiple composée des deux chaines (si c'est possible...)

La solution 1 est la meilleure (en Java un tableau est un objet) : car aussi propre que la 2, et aussi performante que la 3 !

Pour preuve...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
        Map map = new HashMap();
        String[] cle1 = new String[] { "hello", "world" };
        Double valeur1 = new Double(3.14);
        map.put(cle1, valeur1);
        Object cle2 = new String[] { "array", "object" };
        Object valeur2 = new Double(1.0);
        map.put(cle2, valeur2);
        System.out.println(map);
        // {[Ljava.lang.String;@107077e=1.0, [Ljava.lang.String;@11a698a=3.14}
        Object test = map.get(cle1);
        System.out.println(test.equals(valeur1));        
        // true

;)

23/05/2006, 15h30
KiLVaiDeN

Bien vu g_rare :)

Mais j'emet un doute sur la performance; Penses-tu que ce soit vraiment plus performant ?

Car au final tu stockes quand même un tableau ( Un objet à part entière ) qui contient deux objets. Donc en mémoire tu stockes beaucoup plus que le fait de stocker une simple chaine de caractère concaténée.

Et puis, tu as un souci, si tu veux ordonner tes clés non ? Ou je me trompe ?

Juste par curiosité ;)
23/05/2006, 15h30
progamer54
OK merci.

et si je veux faire de ma clé un objet je fais:
Code:

1 2 3 4 5 nb=3.4; Entité e=new Entité(S1,S2); m.put(e,nb); nb2=m.get(e);
ça marche ça? sinon comment mettre un objet en clef? je dois définir Equals() dans mon objet?
23/05/2006, 15h39
g_rare

Citation:

Envoyé par KiLVaiDeN

Mais j'emet un doute sur la performance; Penses-tu que ce soit vraiment plus performant ?

Je parlais de la "performance" du code (rapport entre efforts de programmation et couverture de la résolution du problème), et non de la taille occupée en mémoire... d'ailleurs ce serait plutôt de l' <<efficience>> : ou le rapport ressources/résultats. :D

Citation:

Envoyé par KiLVaiDeN

Et puis, tu as un souci, si tu veux ordonner tes clés non ? Ou je me trompe ?

C'est sûr qu'un tableau étant un java.lang.Object, mais pas un java.lang.Comparable : il est utilisable dans une Map (car "equals" existe) mais pas dans une SortedMap (car "compareTo" n'existe pas) ! 8O

Citation:

Envoyé par progamer54

sinon comment mettre un objet en clef? je dois définir Equals() dans mon objet?

Citation:

Envoyé par adiGuba

Il faut bien sûr que cet objet implémente correctement les méthode equals() et hashcode()...

g_rare >> la solution du tableau est une bonne idée mais ce n'est pas tout à fait correct :

Il est préférable que les clefs des Map soit immuable (non-modifiable), or ce n'est pas le cas d'un tableau.
La méthode equals() des tableaux ne compare pas les différents éléments du tableau, mais seulement la référence du tableau. Donc deux clef au contenu identique ne donneront pas le résultat voulu.

Pour s'en convaincre il suffit de rajouter le code suivant :

Code:

1
2
3
4
5
6
        // cle3 "identique" au contenu de cle1 
        String[] cle3 = new String[] { "hello", "world" };
 
        System.out.println( cle1.equals(cle3) ); // renvoit false
 
        System.out.println( map.get(cle3) ); // renvoit null

Il est donc préférable de passer par une classe conteneur. Voici un exemple de classe qui représente une clef avec deux attributs (et qui utilise les Generics) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public final class BiKey<T,U> {
    private final T key1;
    private final U key2;
 
    /**
     * Creation d'un clef nulle (les deux valeurs sont nulles).
     */
    public BiKey() {
        this(null,null);
    }
 
    /**
     * Creation d'une clef avec deux attributs.
     * @param key1 Valeur du premier attribut.
     * @param key2 Valeur du deuxieme attribut.
     */
    public BiKey(T key1, U key2) {
        this.key1 = key1;
        this.key2 = key2;
    }
 
    /**
     * Methode utilitaire permettant de vérifier que deux objets sont egaux
     */
    private boolean objectsEquals(Object o1, Object o2) {
        boolean sameObject = o1==o2;
        if (!sameObject && o1!=null && o2!=null) {
            sameObject = o1.equals(o2);
        }
        return sameObject;
    }
 
    /**
     * Implémentation de equals().
     * Renvoit true si l'objet en paramètre est identique (même référence),
     * ou si ses attributs sont identiques (selon leurs méthodes equals()).
     */
    @Override
    public boolean equals(Object obj) {
        boolean sameObject = this==obj;
        if (!sameObject && obj instanceof BiKey) {
            BiKey<?,?> other = (BiKey<?,?>) obj;
            sameObject = objectsEquals(this.key1, other.key1)
                &&  objectsEquals(this.key2, other.key2);
        }
        return sameObject;
    }
 
    /**
     * Implémentation de hashCode().
     * Retourne la somme des hashCode() des attributs (0 s'il sont null).
     */
    @Override
    public int hashCode() {
        int hashCode = 0;
        if (this.key1!=null) {
            hashCode += this.key1.hashCode();
        }
        if (this.key2!=null) {
            hashCode += this.key2.hashCode();
        }
        return hashCode;
    }
 
    @Override
    public String toString() {
        String s1 = null;
        String s2 = null;
        if (this.key1!=null) {
            s1 = this.key1.toString();
        }
        if (this.key2!=null) {
            s2 = this.key2.toString();
        }
        return "(" + s1 + ", " + s2 +")";
    }
 
    public T getKey1() {
        return this.key1;
    }
 
    public U getKey2() {
        return this.key2;
    }
}

Exemple d'utilisation :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
        Map<BiKey<String,String>, Double> map = new HashMap<BiKey<String,String>, Double>();
        BiKey<String,String> cle1 = new BiKey<String,String>("hello", "world");
        Double valeur1 = new Double(3.14);
        map.put(cle1, valeur1);
        BiKey<String,String> cle2 =new BiKey<String,String>("array", "object");
        Double valeur2 = new Double(1.0);
        map.put(cle2, valeur2);
        System.out.println(map);
        // {(hello, world)=3.14, (array, object)=1.0}
        Object test = map.get(cle1);
        System.out.println(test.equals(valeur1));        
        // true
 
        //------------------------------------------------------
 
        // cle3 "identique" au contenu de cle1 
        BiKey<String,String> cle3 = new BiKey<String,String>("hello", "world");
 
        System.out.println( cle1.equals(cle3) ); // renvoit true
 
        System.out.println( map.get(cle3) ); // renvoit 3.14

Bien sûr il est préférable d'utiliser des objets immuables pour les attributs de la clef (c'est le cas de String, Integer, Float, etc...)

a++

Citation:

Envoyé par adiGuba

Il est préférable que les clefs des Map soit immuable (non-modifiable), or ce n'est pas le cas d'un tableau.
La méthode equals() des tableaux ne compare pas les différents éléments du tableau, mais seulement la référence du tableau. Donc deux clef au contenu identique ne donneront pas le résultat voulu.

+1 :oops:

Sinon y'a quelques "détails" que je propose dans ta classe de bi-clé générique:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public final class BiKey<T,U> implements Comparable {
    
/**
 * All keys inserted into a sorted map must implement the Comparable
 interface (or be accepted by the specified comparator).
 */
public int compareTo(Object o) {
  int hash1 = this.hashCode();
  int hash2 = (o == null) ? 0 : o.hashCode();
  return hash1 - hash2;
}
    
    /**
     * Implémentation de equals().
     * Renvoit true si l'objet en paramètre est identique (même référence),
     * ou si ses attributs sont identiques (selon leurs méthodes equals()).
     */
    @Override
    public boolean equals(Object obj) {
        boolean sameObject = this==obj;
        if (!sameObject && obj instanceof BiKey<T,U>) {
            BiKey<T,U> other = (BiKey<T,U>) obj;
            sameObject = objectsEquals(this.key1, other.key1)
                &&  objectsEquals(this.key2, other.key2);
        }
        return sameObject;
    }
    
    /**
     * Implémentation de hashCode().
     * Retourne la somme des hashCode() des attributs (0 s'il sont null).
     */
    @Override
    public int hashCode() {
        int result = 17; // 17 nombre premier
        int hash1 = (key == null) ? 0 : key1.hashCode();
        result += 37*result + hash1; // 37 nombre premier
        int hash2 = (key == null) ? 0 : key2.hashCode();
        result += 37*result + hash2; // 
37 nombre premier
        return result;
    }
    
    @Override
    public String toString() {
        return "(" + String.valueOf(s1) + ", " + String.valueOf(s2) +")";
    }    
    
}

:question:

Quelques remarques (aussi :D) :

Je ne suis pas trop d'accord avec ton implémentation de compareTo() : La comparaison des hashCode ne suffit pas à mes yeux puisque deux objets différents peuvent avoir le même hashcode... Il faut également comparer la valeur des attributs. Et pour cela il faut qu'ils soient eux-mêmes comparables...

Et tant qu'à implémenter Comparable, autant utiliser également les Generics et implémenter Comparable<BiKey<T,U>>, ce qui donne :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public final class BiKey<T extends Comparable<T>,U extends Comparable<U>> implements Comparable<BiKey<T,U>>{
    private final T key1;
    private final U key2;
    
    public int compareTo(BiKey<T,U> o) {
        int result = -1;
        if (o!=null) {
            result = 0;
            if (this.key1!=o.key1) {
                if (this.key1==null) {
                    result = -1;
                } else if (o.key1==null) {
                    result = +1;
                } else {
                    result = this.key1.compareTo(o.key1);
                }
            }
            if (result==0) {
                if (this.key2!=o.key2) {
                    if (this.key2==null) {
                        result = -1;
                    } else if (o.key2==null) {
                        result = +1;
                    } else {
                        result = this.key2.compareTo(o.key2);
                    }
                }
            }
        }
        return result;
    }

Toutefois je ferais cela dans une classe fille afin d'avoir une version qui puisse être utiliser avec des éléments non comparable (voir plus bas)...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    /**
     * Implémentation de equals().
     * Renvoit true si l'objet en paramètre est identique (même référence),
     * ou si ses attributs sont identiques (selon leurs méthodes equals()).
     */
    @Override
    public boolean equals(Object obj) {
        boolean sameObject = this==obj;
        if (!sameObject && obj instanceof BiKey<T,U>) {
            BiKey<T,U> other = (BiKey<T,U>) obj;
            sameObject = objectsEquals(this.key1, other.key1)
                &&  objectsEquals(this.key2, other.key2);
        }
        return sameObject;
    }

Non, car instanceof BiKey<T,U> ne peut pas fonctionner car le type générique est perdu à l'exécution (d'ailleur cela provoque une erreur de compilation). Et de toutes manière on n'a pas besoin du type exact des attributs pour connaitre leurs égalités...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    /**
     * Implémentation de hashCode().
     * Retourne la somme des hashCode() des attributs (0 s'il sont null).
     */
    @Override
    public int hashCode() {
        int result = 17; // 17 nombre premier
        int hash1 = (key == null) ? 0 : key1.hashCode();
        result += 37*result + hash1; // 37 nombre premier
        int hash2 = (key == null) ? 0 : key2.hashCode();
        result += 37*result + hash2; // 
37 nombre premier
        return result;
    }

Oui :ccool:
Je sais que l'utilisation de nombre premier peut améliorer le hashcode... Par contre je ne maitrise pas vraiment cela donc je fais le minimum syndicale ;)

Code:

1
2
3
4
5
 
    @Override
    public String toString() {
        return "(" + String.valueOf(s1) + ", " + String.valueOf(s2) +")";
    }

+1 aussi
Je n'ai pas vraiment l'habitude de l'utiliser pourtant c'est très pratique et nettement plus lissible...

Au final cela donnerait deux classe : BiKey pour des clefs dont les attributs n'implémente pas forcément Comparable :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public class BiKey<T, U> {
    private final T key1;
    private final U key2;
 
    /**
     * Creation d'un clef nulle (les deux valeurs sont nulles).
     */
    public BiKey() {
        this(null,null);
    }
 
    /**
     * Creation d'une clef avec deux attributs.
     * @param key1 Valeur du premier attribut.
     * @param key2 Valeur du deuxieme attribut.
     */
    public BiKey(T key1, U key2) {
        this.key1 = key1;
        this.key2 = key2;
    }
 
    /**
     * Methode utilitaire permettant de vérifier que deux objets sont egaux
     */
    private boolean objectsEquals(Object o1, Object o2) {
        boolean sameObject = o1==o2;
        if (!sameObject && o1!=null && o2!=null) {
            sameObject = o1.equals(o2);
        }
        return sameObject;
    }
 
    /**
     * Implémentation de equals().
     * Renvoit true si l'objet en paramètre est identique (même référence),
     * ou si ses attributs sont identiques (selon leurs méthodes equals()).
     */
    @Override
    public final boolean equals(Object obj) {
        boolean sameObject = this==obj;
        if (!sameObject && obj instanceof BiKey) {
            BiKey<?,?> other = (BiKey<?,?>) obj;
            sameObject = objectsEquals(this.key1, other.key1)
                &&  objectsEquals(this.key2, other.key2);
        }
        return sameObject;
    }
 
    /**
     * Implémentation de hashCode().
     * Retourne la somme des hashCode() des attributs (0 s'il sont null).
     */
    @Override
    public final int hashCode() {
        int result = 17; // 17 nombre premier
        int hash1 = (this.key1 == null) ? 0 : this.key1.hashCode();
        result += 37*result + hash1; // 37 nombre premier
        int hash2 = (this.key2 == null) ? 0 : this.key2.hashCode();
        result += 37*result + hash2; // 37 nombre premier
        return result;
    }
 
    @Override
    public final String toString() {
        return "(" + String.valueOf(this.key1) + ", " + String.valueOf(this.key2) +")";
    }
 
    public final T getKey1() {
        return this.key1;
    }
 
    public final U getKey2() {
        return this.key2;
    }
}

La classe n'est plus final car on a besoin d'en hériter... Du coup on passe toutes les méthodes en final pour éviter d'avoir des classes filles qui ne respectent pas l'immuabilité (en surchargeant ces méthodes par exemple)...

Enfin la classe SortedBiKey permet de gérer des clefs qui implementent Comparable afin d'être utilisé dans une SortedMap. Elle hérite directement de BiKey :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public final class SortedBiKey<T extends Comparable<T>, U extends Comparable<U>>
    extends BiKey<T, U> implements Comparable<SortedBiKey<T,U>>{
 
    /**
     * Creation d'un clef nulle (les deux valeurs sont nulles).
     */
    public SortedBiKey() {
        this(null,null);
    }
 
    /**
     * Creation d'une clef avec deux attributs.
     * @param key1 Valeur du premier attribut.
     * @param key2 Valeur du deuxieme attribut.
     */
    public SortedBiKey(T key1, U key2) {
        super(key1, key2);
    }
 
    public int compareTo(SortedBiKey<T,U> o) {
        int result = -1;
        if (o!=null) {
            result = 0;
            if (this.getKey1()!=o.getKey1()) {
                if (this.getKey1()==null) {
                    result = -1;
                } else if (o.getKey1()==null) {
                    result = +1;
                } else {
                    result = this.getKey1().compareTo(o.getKey1());
                }
            }
            if (result==0) {
                if (this.getKey2()!=o.getKey2()) {
                    if (this.getKey2()==null) {
                        result = -1;
                    } else if (o.getKey2()==null) {
                        result = +1;
                    } else {
                        result = this.getKey2().compareTo(o.getKey2());
                    }
                }
            }
        }
        return result;
    }
}

Je suis sûr qu'on peut faire mieux pour la méthode compareTo() ;)

Enfin, petite astuce si vous ne voulez pas vous embêter à coder les méthodes hashCode(), equals(), compareTo() ou toString(), le package org.apache.commons.lang.builder des Commons/Lang du projet Jakarta propose une série de classe Builder automatique ou presque ;)

a++