Vous aimez ce que vous lisez sur ce blog ?
Envie d'aller plus loin avec véritable formation d'expertise en Java ?
Venez suivre ma formation Masterclasse Expertise Java !

"Même un développeur experimenté a besoin de continuer à apprendre. Et dans cette formation... j'ai appris beaucoup !" - A.G., Java Champion

Sessions intra-entreprises sur demande : contact[at]mokatech.net.
Inscrivez-vous vite !

De l'utilité d'un bon hashCode

La bonne implémentation de la méthode hashCode() a une conséquence directe sur les performances des collections de type Hash* (HashSet, HashMap...).

Pour le démontrer, je vous propose une petite expérience : nous allons mesurer le temps nécessaire à l'insertion d'un grand nombre d'objets dans un HashSet, en fonction de la qualité de leur algorithme de hachage.

Nous utiliserons à cet effet la classe Person, qui nous servira de cobaye.
Son hashCode est calculé à partir d'un nombre ajustable de caractères (charsToHash) tirés de sa propriété name. Dans le pire des cas (0 caractères), la valeur renvoyée sera donc une constante.

public class Person {
 
    /** Nombre de chars à prendre en compte pour le calcul du hashCode */
    public static int charsToHash = 0;
 
    private final String name;
 
    public Person(String name) {
        this.name = name;
    }
 
    @Override
    public boolean equals(Object o) {
        (...)
    }
 
    @Override
    public int hashCode() {
        return name == null ? 0 : name.substring(0, charsToHash).hashCode();
    }
}

Notre benchmark se déroule alors comme suit :

  • Tout d'abord, un ensemble de Personnes est généré à partir d'un fichier texte qui contient des noms aléatoires.
  • Ensuite, on fait varier le nombre de caractères servant à calculer le hashCode d'une Personne (charsToHash). Pour chaque valeur testée, on insère plusieurs (INSERTS) fois l'ensemble complet des Personnes dans un même HashSet, afin de provoquer des collisions.
  • Le temps mesuré est affiché dans la console, ainsi que le gain relatif à la première mesure, qui sert de référence.
public class HashCodeBenchmark {
 
    private static final String PERSONS_FILE = "net/thecodersbreakfast/corejava/hash/names.txt";
    private static final int PERSONS_IN_FILE = 1000;
    private static final int INSERTS = 1500;
    private static final int MIN_CHARS_TO_HASH = 0;
    private static final int MAX_CHARS_TO_HASH = 5;
 
    public static void main(String[] args) throws IOException {
        HashCodeBenchmark test = new HashCodeBenchmark();
        test.benchmarkSuite();
    }
 
    private List<Person> persons = loadPersonsFromFile();
 
    private List<Person> loadPersonsFromFile() {
        List<Person> persons = new ArrayList<Person>(PERSONS_IN_FILE);
 
        try {
            InputStream is = Thread.currentThread().getContextClassLoader().getResourceAsStream(PERSONS_FILE);
            InputStreamReader isr = new InputStreamReader(is);
            BufferedReader reader = new BufferedReader(isr);
            String personName = null;
            while ((personName = reader.readLine()) != null) {
                persons.add(new Person(personName));
            }
            reader.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
 
        return persons;
    }
 
    private void benchmarkSuite() {
        System.out.printf(
            "Inserting %d times %d persons (total: %d insertions)%n", 
            INSERTS, PERSONS_IN_FILE, INSERTS * PERSONS_IN_FILE);
 
        long referenceTime = 0;
        for (int hashStrength = MIN_CHARS_TO_HASH; hashStrength <= MAX_CHARS_TO_HASH; hashStrength++) {
            cleanMemory();
            Person.charsToHash = hashStrength;
            long time = benchmark();
 
            if (referenceTime==0) {
                referenceTime = time;
            }
 
            System.out.printf(
                "%d chars used in hash = %6dms (%5.1fx faster)%n", 
                hashStrength, time, ((float)referenceTime/time));
        }
    }
 
    public long benchmark() {
        Set<Person> set = new HashSet<Person>(PERSONS_IN_FILE);
        long time = System.currentTimeMillis();
        for (int i = 0; i < INSERTS; i++) {
            set.addAll(persons);
        }
        time = System.currentTimeMillis() - time;
        assert set.size()==PERSONS_IN_FILE;
        return time;
    }
 
    private void cleanMemory() {
        System.gc();
        System.gc();
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
        }
    }
 
}

Ci-dessous, les résultats obtenus sur ma machine. Le nombre d'itérations (INSERTS) a été choisi pour obtenir des résultats significatifs en un temps acceptable.

Inserting 1500 times 1000 persons (total: 1500000 insertions)
0 chars used in hash =  15296ms (  1,0x faster)
1 chars used in hash =   1028ms ( 14,9x faster)
2 chars used in hash =    350ms ( 43,7x faster)
3 chars used in hash =    220ms ( 69,5x faster)
4 chars used in hash =    181ms ( 84,5x faster)
5 chars used in hash =    176ms ( 86,9x faster)
6 chars used in hash =    170ms ( 90,0x faster)

On note que, si la progression n'est pas linéaire, la différence de performance entre un hashCode constant et un hashCode plus discriminant est énorme.
Vous pouvez effectuer vos propres mesures à l'aide du code source disponible en pièce jointe du billet.

En tout cas, la conclusion est sans appel : il est très important de produire des hashCodes réellement discriminants si l'on veut obtenir des performances raisonnables.


Commentaires

1. Le jeudi 6 octobre 2011, 09:51 par olivier

Bonjour,
Avec cet exemple je comprend bien pourquoi il est important de surcharger le hashCode mais est-ce que tu aurais des conseils sur "Comment construire un bon hashcode".

Par exemple, comment faire avec la classe Person ayant les attributs suivants :
- String firstName
- String lastName
- String phone
- int id (par exemple le numéro de sécu)

2. Le jeudi 6 octobre 2011, 10:09 par Nicolas

Il y a quelques apis qui propose de simplifier l'écriture du hashCode comme Apache Commons et Guava. As tu noté une différence de performance entre elles et une écriture à la main ?

3. Le jeudi 6 octobre 2011, 13:41 par Brice

Bon article, as usual.

Je mettrais cet article en relation avec le design d'un objet s'il est utilisé dans une collection par exemple.

http://blog.arkey.fr/2010/03/30/a-p...

4. Le jeudi 6 octobre 2011, 14:13 par Olivier Croisier

Bonne remarque.
Dans le même genre, je vous renvoie également à un de mes anciens articles (mais toujours valable), sur les getters/setters appliqués aux collections :

http://thecodersbreakfast.net/index...

5. Le jeudi 6 octobre 2011, 15:15 par Mathieu

Salut Olivier,

Pour affiner ton benchmark, ne faudrait-il pas changer l'implémentation de ton equals ? Actuellement il dépend de la taille du nom, donc les résultats sont faussé dans le sens qu'au plus le nom de la personne est grand, au plus ton equals va être lent, et le equals peut être est appelé lors des insertions lorsqu'un même hashcode est trouvé.

Tu pourrais par exemple avoir un equals basé sur l'index de la personne dans le fichier. Exemple:

class Person {

   private final int index;
   @Override
   public boolean equals(Object o) {
       return index == ((Person) o).index;
   }

}

Tu peux te permettre ce genre de equals "lineaire" car tu sais que tu n'as que des Person dans ton set.

Les résultats devraient être similaires mais beaucoup plus resserés je pense.

6. Le jeudi 6 octobre 2011, 15:37 par Olivier Croisier

Remarque intéressante, même si je doute que cela change grand chose au résultat. As-tu testé ? (le code est en pièce jointe du billet). Sinon, j'essaierai de le faire rapidement.

7. Le jeudi 6 octobre 2011, 21:59 par HollyDays

@ Mathieu

Depuis au moins le JDK 1.5, String.equals() ne s'exécute en un temps proportionnel à la longueur de la chaîne de caractères que si les 2 chaînes à comparer sont de même longueur.

Si elles sont de longueur différente (ce qui, vue la liste de noms utilisée dans le test d'Olivier, est statistiquement le cas de loin le plus probable), alors l'exécution de String.equals() se fait en un temps constant, car dans ce cas, la valeur de retour est toujours false.

Pour vérifier mes dires, il te suffit de regarder comment est implémenté String.equals() dans le JDK (ce que je t'invite à faire !)

8. Le mardi 18 octobre 2011, 09:16 par Saubienluyet

Ça n'a aucun rapport avec le mécanisme de calcul du HashCode, mais en anglais, le pluriel de "person" c'est "people"...

9. Le mercredi 19 octobre 2011, 20:42 par mejdi

C'est la règle 9 dans effective java qui parle de l'impact du mauvais choix de hashcode dans les hashMap .
Mais ce cas partique qui manque dans le livre nous fait prendre conscience de l'importance de cette règle.

Pour la classe Person, la règle stipule de choisir les attributs les plus significatifs, je pense que ces attributs sont de bons candidats :
- lastName
- firstName
- id

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.