Programmation Java/Objets comparables et clés

Certaines collections d'objets nécessitent l'utilisation de classes dont les instances sont comparables pour pouvoir trier la collection. De plus, pour utiliser une instance d'une classe comme clé dans les tables associatives, la classe doit posséder des propriétés supplémentaires.

Programmation Java

Version imprimable

[ Modifier le sommaire ]

this

Énumérations

Objets comparables

Pour utiliser un objet dans une collection triée, on peut :

soit utiliser des éléments instances d'une classe comparable,
soit spécifier un comparateur d'éléments au constructeur de la collection.

interface `Comparable`

Une classe implémente l'interface java.lang.Comparable en ajoutant la méthode suivante :

int compareTo(Object o)

ou (Java 5+) interface Comparable<T> :

int compareTo(T o)

Dans cette méthode l'objet this est comparé à l'objet o. Cette méthode doit retourner le signe de la soustraction virtuelle this - o. C'est à dire :

-1 si this < o
0 si this == o
+1 si this > o

Cette méthode doit avoir les propriétés suivantes, pour toutes instances de la classe nommées o1, o2 et o3 :

o1.compareTo(o1) == 0,
o1.compareTo(o2) == - o2.compareTo(o1),
o1.compareTo(o2) > 0 et o2.compareTo(o3) > 0 implique o1.compareTo(o3) > 0.

De plus, pour utiliser une instance de la classe dans une collection, le comportement de cette méthode doit être consistant avec celle de la méthode equals :

Pour toute instance de la classe nommés o1 et o2, les deux expressions booléennes o1.compareTo(o2)==0 et o1.equals(o2) retournent la même valeur,
La comparaison avec null doit lancer une exception NullPointerException.

Comparateur (`Comparator`)

L'interface java.util.Comparator permet de rendre comparable des instances dont la classe n'implémente pas elle-même l'interface java.lang.Comparable vue précédemment. Une classe implémentant cette interface doit déclarer deux méthodes :

int compare(Object o1, Object o2)
int equals(Object o)

ou (Java 5+) interface Comparator<T> :

int compare(T o1, T o2)
int equals(Object o)

La méthode equals compare les comparateurs (eux-mêmes) this et o.

La méthode compare compare les deux objets spécifiés et retourne le signe de la soustraction virtuelle o1 - o2, comme expliqué dans la section précédente. C'est-à-dire :

-1 si o1 < o2
0 si o1 == o2
+1 si o1 > o2

Clé de table associative

Pour utiliser une instance de classe comme clé d'une table associative (Map en anglais), la classe doit posséder les propriétés suivantes :

La classe doit posséder une méthode equals cohérente,
La classe doit posséder une méthode hashCode cohérente.

Dans le cas contraire (par défaut), il est toujours possible d'utiliser des instances de la classe comme clé, mais il faudra utiliser cette instance seulement. C'est à dire que pour retrouver une valeur dans une table associative, il ne sera pas possible d'utiliser une autre instance dont les attributs sont égaux à ceux de l'instance utilisée pour réaliser l'association. Une énumération ayant des instances prédéterminées et ne pouvant avoir d'autres instances convient donc pour être utilisée comme clé.

Exemple : un tableau d'entiers utilisé comme clé.

int[] key1 = { 1, 2 };
int[] key2 = { 1, 2 }; // même contenu que key1

HashMap hmap = new HashMap();

// association key1 -> chaîne de caractère
hmap.put(key1, "Valeur pour la suite (1,2)");

// tentative pour retrouver la valeur
String s1 = (String)hmap.get(key1); // retourne "Valeur pour la suite (1,2)"

// tentative pour retrouver la valeur
String s2 = (String)hmap.get(key2); // retourne null

La tentative échoue car un tableau n'a pas toutes les propriétés nécessaires. La méthode equals est correcte, mais la méthode hashCode retourne deux valeurs différentes.

Méthode equals

Une classe doit implémenter la méthode equals de manière cohérente, c’est-à-dire, pour toutes instances de la classe nommées o1, o2 et o3 :

o1.equals(o1) == true,
o1.equals(o2) == o2.equals(o1),
o1.equals(o2) et o2.equals(o3) implique o1.equals(o3).

Méthode hashCode

Pour utiliser une classe comme clé d'une table associative, il faut que la classe implémente la méthode hashCode() de manière cohérente. Pour comprendre cela, il faut aborder le fonctionnement interne des tables associatives indexée par des objets :

Les méthodes de la table associative appellent la méthode hashCode() de la clé pour obtenir un entier,
Cet entier est transformé en index dans un tableau par reste de la division par la taille du tableau,
Ce tableau contient une liste de clés comparées avec celle fournie à la méthode appelée en utilisant la méthode equals vue auparavant.

Il est donc essentiel que la méthode hashCode ait les propriétés suivantes :

Cette méthode doit toujours retourner la même valeur si l'objet n'a pas été modifié,
Pour deux objets égaux (méthode equals retourne true), la méthode hashCode doit retourner deux valeurs égales. C'est à dire, pour toute instance de la classe nommés o1 et o2, o1.equals(o2) implique o1.hashCode() == o2.hashCode(),
Il est recommandé que pour deux objets différents, la méthode hashCode retourne deux valeurs distinctes.

La méthode par défaut retourne la même valeur que la méthode System.identityHashCode(this) qui se base sur la référence de l'objet (0 si la référence est null). C'est à dire que deux objets différents mais avec des contenus identiques auront tout de même une valeur différente.

Objets utilisables comme clé

Comme expliqué dans la section d'introduction, il est possible d'utiliser n'importe quel type d'objet à condition d'utiliser exactement la même instance, ou bien que la classe possède des méthodes equals et hashCode cohérentes, comme la classe java.lang.String par exemple.

String key1 = "Clé de test";
String key2 = "Clé" + " de " + "test";

HashMap hmap = new HashMap();

// association key1 -> chaîne de caractère
hmap.put(key1, "Valeur pour la clé");

// tentative pour retrouver la valeur
String s1 = (String)hmap.get(key1); // retourne "Valeur pour la clé"

// tentative pour retrouver la valeur
String s2 = (String)hmap.get(key2); // retourne "Valeur pour la clé"