CodeGym /Blog Java /France /Les tables de hachage en Java avec des exemples
Auteur
Pavlo Plynko
Java Developer at CodeGym

Les tables de hachage en Java avec des exemples

Publié dans le groupe France
La classe Hashtable Java est un des plus anciens membres du framework de collections Java. C'est une implémentation de la structure mathématique des données des tables de hachage. Une Hashtable Java possède en interne des conteneurs où des paires clé/valeur sont stockées. Hashtable est assez similaire à HashMap. La différence principale entre les deux est que Hashtable est synchronisée, tandis que HashMap ne l'est pas. Qu'est-ce qu'une Hashtable ? Les tables de hachage en Java avec des exemples - 1

Hashtable Java comme structure de données

Une Hashtable est une structure de données où les données sont stockées sous forme de tableau. Chaque valeur de données a une valeur de clé unique. Si la clé est connue, tu peux accéder aux données souhaitées très rapidement. Ainsi, les opérations d'insertion et de recherche sont rapides et indépendantes de la taille des données. Une table de hachage se compose d'un tableau pour conserver des données et d'une fonction de hachage pour générer l'index où un élément doit être stocké. Qu'est-ce que le hachage ? En Java, il s'agit d'une règle qui mappe un objet sur un jeu de caractères (un code de hachage). Habituellement, ce genre de fonction convertit un gros morceau de données en une petite valeur entière. Les fonctions de hachage peuvent être variées, mais elles respectent toutes certaines propriétés :
  • Un objet particulier a un code de hachage particulier.
  • Deux objets égaux ont les mêmes codes de hachage. L'inverse n'est pas vrai.
  • Si deux codes de hachage sont différents, alors nous avons la certitude que les objets ne sont pas égaux.
  • Différents objets peuvent avoir le même code de hachage. Cet événement très rare est appelé une collision. Une bonne fonction de hachage minimise la probabilité de collisions.
Le résultat de l'application de la fonction de hachage à un objet est appelé hashCode.

Hashtable en Java

La classe Hashtable est l'implémentation d'une structure de données de table de hachage. Cette collection a été créée plus tôt que le framework de collections Java, mais n'y a été incluse que par la suite. Comme toutes les collections « anciennes » (de Java 1.0), une hashtable est synchronisée (presque toutes ses méthodes sont marquées synchronized). Pour cette raison, Hashtable a des problèmes de performances importants. Ainsi, à partir de Java 1.2, dans la plupart des cas, il est recommandé d'utiliser d'autres implémentations de l'interface Map pour leur absence de synchronisation. HashMap est généralement la solution de remplacement la plus appropriée. La classe Hashtable <K,V> se compose de clés et de valeurs. Elle stocke les clés en fonction du principe de hachage. Les paires clé/valeur sont stockées dans des « conteneurs ». Les conteneurs forment ensemble une « table », une sorte de tableau interne. Hashtable utilise le code de hachage de la clé pour déterminer le conteneur sur lequel mapper la paire clé/valeur. La fonction de hachage calcule un emplacement de conteneur à partir du code de hachage d'une clé. Cette fonction renvoie un nombre entier pour un objet. Comme nous l'avons dit plus haut, deux objets égaux ont le même code de hachage, tandis que deux objets inégaux peuvent ne pas avoir des codes de hachage différents. Différents objets mis dans une hashtable peuvent avoir le même code de hachage. Pour résoudre ce problème (collision), une hashtable utilise un tableau de listes. Toutes les paires qui mappent sur le même conteneur sont stockées dans une liste et une référence à la liste est stockée dans l'index du tableau.

Constructeurs de Hashtable Java

  • Hashtable() est le constructeur par défaut. Il crée une hashtable vide. (Capacité initiale par défaut = 11, facteur de charge = 0,75).
  • Hashtable(int size) construit une hashtable de la taille spécifiée.
  • Hashtable(int size, float fillRatio) crée une table de hachage de la taille et du rapport de remplissage spécifiés.
  • Hashtable(Map m) crée une hashtable avec les mêmes mappages que la carte passée.

Déclaration de hashtable

La classe Hashtable Java implémente les interfaces Map, Cloneable et Serializable. Elle étend la classe Dictionary.

Hashtable.java
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable
K est le type des clés conservées par la carte. V est le type des valeurs mappées. Exemple :

Hashtable<Student, Integer> myHTable = new Hashtable<>();

Comment importer une hashtable Java

En Java, Hashtable se trouve à l'intérieur du package java.util. Utilise donc import java.util.Hashtable; dans ton code. En général, ton EDI te donnera un petit indice.

Opérations principales des hashtables

Les principales opérations de la classe Hashtable sont la récupération, l'insertion dans la collection et la suppression. Ici, ces trois opérations se présentent ainsi :
  • Object get(Object key) renvoie la valeur de l'objet qui possède la clé spécifiée. Renvoie null si cette clé est introuvable.
  • Object put(Object key, Object value) mappe la clé spécifiée à la valeur spécifiée. Ni la clé ni la valeur ne peuvent être null.
  • Object remove(Object key) supprime l'entrée (la clé et la valeur correspondante) de la hashtable.
Voici d'autres opérations importantes :
  • int size() renvoie la quantité d'entrées dans la table de hachage.
  • boolean contains(Object value) vérifie si la valeur spécifiée se trouve dans la table de hachage. Si c'est le cas, la méthode renvoie true, sinon elle renvoie false.
  • boolean containsValue(Object value) vérifie si la valeur spécifiée se trouve dans la table de hachage. Si c'est le cas, la méthode renvoie true, sinon elle renvoie false.
  • void clear() supprime toutes les entrées de la hashtable.
  • boolean containsKey(Object key) est une méthode qui renvoie true si la clé spécifiée existe dans la table de hachage ; sinon elle renvoie false.
  • boolean isEmpty() renvoie true si la hashtable est vide, ou false si elle contient au moins une clé.
  • void rehash() augmente la taille de la hashtable et hache à nouveau toutes ses clés.

Implémentation d'une table de hachage, code Java :

Créons une classe Student :

import java.util.Date;
public class Student {
   String surname;
   String name;
   String secondName;
   Long birthday; // Long instead of long is used by Gson/Jackson json parsers and various orm databases

   public Student(String surname, String name, String secondName, Date birthday ){
       this.surname = surname;
       this.name = name;
       this.secondName = secondName;
       this.birthday = birthday == null ? 0 : birthday.getTime();
   }

   @Override
   public int hashCode(){
       //TODO: check for nulls
       return (surname + name + secondName + birthday).hashCode();
   }
   @Override
   public boolean equals(Object other_) {
       Student other = (Student)other_;
       return (surname == null || surname.equals(other.surname) )
               && (name == null || name.equals(other.name))
               && (secondName == null || secondName.equals(other.secondName))
               && (birthday == null || birthday.equals(other.birthday));
   }
}
Voici un exemple de Hashtable Java. Mettons deux objets de la classe Student dans la hashtable, puis supprimons-en un et vérifions quelques paramètres.

public class HashTableExample {
   public static void main(String[] args) {
 
       Hashtable<Student, Integer> myHTable = new Hashtable<>();
       Student sarah1 = new Student("Sarah","Connor", "Jane", null);
       Student john = new Student("John","Connor", "Kyle", new Date(1985, 02-1, 28)); // date not exists
       myHTable.put(john,1);
       myHTable.put(sarah1,0);
       System.out.println(myHTable.get(john));
       System.out.println(myHTable.isEmpty());
       System.out.println(myHTable.size());
       System.out.println(myHTable.contains(1));
       myHTable.remove(john);
       System.out.println(myHTable.contains(0));
       System.out.println(myHTable.contains(1));
       System.out.println(myHTable.containsKey(sarah1));
   }
}
Le résultat de l'exécution du programme est :

1
false
2
true
true
false
true

HashMap vs Hashtable

  • Hashtable est similaire à HashMap en Java. La différence la plus significative est que la classe Hashtable est synchronisée alors que HashMap ne l'est pas. Par conséquent, Hashtable est plus lente que HashMap en raison de la synchronisation.
  • Au-delà du problème de synchronisation, Hashtable ne permet pas d'utiliser null comme valeur ou clé. HashMap permet d'avoir une clé null et plusieurs valeurs null.
  • Hashtable hérite de la classe Dictionary tandis que HashMap hérite de la classe AbstractMap.
  • HashMap est traversée par un Iterator. Hashtable peut être traversée non seulement par un Iterator, mais aussi par un Enumerator.

Exemple de hashtable Java (clé null avec Hashable vs HashMap)

Voici un fragment de code pour montrer quand null est utilisé comme clé et valeur dans HashMap et Hashtable

// Null key Java hashtable example and hashmap example  

try{
      System.out.println("Hashtable");
      Hashtable hashTable = new Hashtable();
      hashTable.put(null, new Object());
    }catch(Exception ex){
      ex.printStackTrace();
    }
    System.out.println("HashMap");
    HashMap hashMap = new HashMap();
    hashMap.put(null, new Object());
    System.out.println("as you see no exceptions with null key in HashMap");
  }
Le résultat de l'exécution du programme qui contient ce fragment est :

java.lang.NullPointerException
	at java.base/java.util.Hashtable.put(Hashtable.java:480)
	at Character.main(Character.java:58)
HashMap
as you see no exceptions with null key in HashMap

Conclusion

Tu n'utiliseras pas Hashtable très souvent dans de vrais projets, mais tu peux facilement rencontrer cette structure de données dans de vieux projets. Quoi qu'il en soit, il est important de comprendre les structures de données que Java offre et comment elles fonctionnent, au moins pour tes entretiens. Des objets HashMap sont généralement utilisés au lieu de Hashtable en raison de leur similitude. La classe HashMap est plus performante (elle n'est pas synchronisée) et peut avoir null comme clé.
Cet article est également disponible en anglais:
Read the English version of this article to become an expert on the Java Hashtable class. Hash tables are the best kind of hash! :)
Commentaires
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION