Les tables de hachage constituent un moyen utile d'optimiser les performances des applications.
Les tables de hachage ne sont pas un concept nouveau dans le domaine informatique. Ils ont été conçus pour accélérer le traitement informatique, qui est très lent par rapport aux normes actuelles, et ils vous permettent de trouver rapidement une entrée particulière lors de l'interrogation de nombreuses entrées de données. Bien que les machines modernes soient des milliers de fois plus rapides, les tables de hachage restent un outil utile pour obtenir les meilleures performances de vos applications.
Imaginez que vous disposez d'un fichier de données contenant environ un millier d'enregistrements (par exemple des enregistrements de clients pour une petite entreprise) et d'un programme qui lit les enregistrements en mémoire pour les traiter. Chaque enregistrement contient un numéro d'identification client unique à cinq chiffres, le nom du client, son adresse, le solde du compte, etc. Supposons que les enregistrements ne soient pas triés par numéro d'identification client. Par conséquent, si le programme souhaite utiliser le numéro de client comme « clé » pour trouver un enregistrement client particulier, la seule façon de le trouver est de rechercher chaque enregistrement consécutivement. Parfois, il trouvera rapidement l'enregistrement dont vous avez besoin ; mais parfois, avant que le programme ne trouve l'enregistrement dont vous avez besoin, il a presque recherché le dernier enregistrement. Si vous souhaitez effectuer une recherche parmi 1 000 enregistrements, la recherche d'un enregistrement nécessite que le programme vérifie une moyenne de 500,5 ((1 000 + 1)/2) enregistrements. Si vous avez fréquemment besoin de rechercher des données, vous aurez peut-être besoin d'un moyen plus rapide pour trouver un enregistrement.
Une façon d'accélérer votre recherche consiste à diviser les enregistrements en morceaux afin qu'au lieu de rechercher une grande liste, vous effectuiez une recherche dans plusieurs listes courtes. Pour nos numéros d'identification client numériques, vous pouvez créer 10 listes : une liste pour les numéros d'identification commençant par 0, une liste pour les numéros d'identification commençant par 1, et ainsi de suite. Ainsi, pour trouver le numéro d’identification client 38016, il vous suffit de rechercher dans la liste commençant par 3. S'il y a 1 000 enregistrements et que la longueur moyenne de chaque liste est de 100 (1 000 enregistrements divisés en 10 listes), alors le nombre moyen de comparaisons pour rechercher un enregistrement tombe à environ 50 (voir Figure 1).
Bien sûr, si environ un numéro de client sur dix commence par un 0, un autre dixième commence par un 1, et ainsi de suite, alors cette approche fonctionnerait bien. Si 90 % des numéros de clients commençaient par 0, alors cette liste contiendrait 900 enregistrements, nécessitant en moyenne 450 comparaisons par recherche. De plus, 90 % des recherches que le programme doit effectuer concernent des nombres commençant par 0. Par conséquent, le nombre de comparaison moyen dépasse largement le cadre des simples opérations mathématiques.
Il serait préférable que nous puissions répartir les enregistrements dans nos listes de manière à ce que chaque liste contienne à peu près les mêmes entrées, quelle que soit la répartition des nombres dans les valeurs clés. Nous avons besoin d’un moyen de regrouper les numéros de clients et de mieux répartir les résultats. Par exemple, nous pourrions prendre chaque chiffre du nombre, le multiplier par un grand nombre (qui varie en fonction de la position du chiffre), additionner les résultats pour produire un total, diviser ce nombre par 10 et donner le reste sous forme d'index. valeur (indice). Lorsqu'un enregistrement est lu, le programme exécute cette fonction de hachage sur le numéro de client pour déterminer à quelle liste appartient l'enregistrement. Lorsque l'utilisateur a besoin d'interroger, la même fonction de hachage est utilisée comme « clé » pour le numéro de client afin que la liste correcte puisse être recherchée. Une structure de données comme celle-ci s’appelle une table de hachage.
Tables de hachage en Java
Java contient deux classes, java.util.Hashtable et java.util.HashMap , qui fournissent un mécanisme de table de hachage polyvalent. Les deux classes sont très similaires et fournissent généralement la même interface publique. Mais ils présentent quelques différences importantes, dont je parlerai plus tard.
Les objets Hashtable et HashMap vous permettent de combiner une clé et une valeur et de saisir la paire clé/valeur dans le tableau à l'aide de la méthode put (). Vous pouvez ensuite obtenir la valeur en appelant la méthode get(), en passant la clé en paramètre. La clé et la valeur peuvent être n'importe quel objet à condition qu'ils répondent à deux exigences de base. Notez que, comme les clés et les valeurs doivent être des objets, les types primitifs doivent être convertis en objets à l'aide de méthodes telles que Integer(int).
Afin d'utiliser un objet d'une classe spécifique comme clé, la classe doit fournir deux méthodes, equals() et hashCode(). Ces deux méthodes sont dans java.lang.Object , donc toutes les classes peuvent hériter de ces deux méthodes ; cependant, l'implémentation de ces deux méthodes dans la classe Object est généralement inutile, vous devez donc généralement surcharger ces deux méthodes vous-même.
La méthode Equals() compare son objet avec un autre objet et renvoie vrai si les deux objets représentent la même information. Cette méthode cherche également à s’assurer que les deux objets appartiennent à la même classe. Object.equals() renvoie true si les deux objets de référence sont des objets identiques, ce qui explique pourquoi cette méthode n'est généralement pas adaptée. Dans la plupart des cas, vous avez besoin d'un moyen de comparer champ par champ, c'est pourquoi nous considérons que différents objets représentant les mêmes données sont égaux.
La méthode HashCode() génère une valeur int en exécutant une fonction de hachage en utilisant le contenu de l'objet. Hashtable et HashMap utilisent cette valeur pour déterminer dans quel compartiment (ou liste) se trouve une paire clé/valeur.
A titre d'exemple, nous pouvons regarder la classe String, car elle possède ses propres méthodes qui implémentent ces deux méthodes. String.equals() compare deux objets String caractère par caractère et renvoie true si les chaînes sont identiques :
Copiez le code comme suit :
Chaîne monNom = "Einstein" ;
// Le test suivant est
// toujours vrai
if ( monNom.equals("Einstein") )
{...
String.hashCode() exécute une fonction de hachage sur une chaîne. Le code numérique de chaque caractère de la chaîne est multiplié par 31 et le résultat dépend de la position du caractère dans la chaîne. Les résultats de ces calculs sont ensuite additionnés pour donner un total. Ce processus peut paraître compliqué, mais il assure une meilleure répartition des valeurs. Cela montre également jusqu'où vous pouvez aller lorsque vous développez votre propre méthode hashCode(), en étant sûr que le résultat est unique.
Par exemple, supposons que je souhaite utiliser une table de hachage pour implémenter un catalogue de livres et utiliser le numéro ISBN du livre comme clé de recherche pour effectuer la recherche. Je peux utiliser la classe String pour transporter les détails et préparer les méthodes equals() et hashCode() (voir Listing 1). Nous pouvons ajouter des paires clé/valeur à la table de hachage en utilisant la méthode put () (voir Listing 2).
La méthode Put () accepte deux paramètres, tous deux de type Objet. Le premier paramètre est la clé ; le deuxième paramètre est la valeur. La méthode Put () appelle la méthode hashCode() de la clé et divise le résultat par le nombre de listes dans le tableau. Utilisez le reste comme valeur d'index pour déterminer à quelle liste l'enregistrement est ajouté. Notez que la clé est unique dans la table ; si vous appelez put () avec une clé existante, l'entrée correspondante est modifiée pour qu'elle fasse référence à une nouvelle valeur et l'ancienne valeur est renvoyée (lorsque la clé n'existe pas dans la table) , put () renvoie une valeur nulle).
Pour lire une valeur de la table, nous utilisons la clé de recherche avec la méthode get(). Il renvoie une référence d'objet convertie dans le type correct :
Copiez le code comme suit :
LivreEnregistrement br =
(BookRecord)isbnTable.get(
"0-345-40946-9");
System.out.println(
"Auteur : " + br.auteur
+ " Titre : " + br.titre);
Une autre méthode utile est remove(), qui est utilisée presque de la même manière que get(). Elle supprime l'entrée de la table et la renvoie au programme appelant.
votre propre classe
Si vous souhaitez utiliser un type primitif comme clé, vous devez créer un objet du même type. Par exemple, si vous souhaitez utiliser une clé entière, vous devez utiliser le constructeur Integer(int) pour générer un objet à partir d'un entier. Toutes les classes wrapper telles que Integer, Float et Boolean traitent les valeurs primitives comme des objets et surchargent les méthodes equals() et hashCode(), afin qu'elles puissent être utilisées comme clés. De nombreuses autres classes fournies dans le JDK ressemblent à ceci (même les classes Hashtable et HashMap implémentent leurs propres méthodes equals() et hashCode()), mais vous devez consulter la documentation avant d'utiliser des objets d'une classe comme clés de table de hachage. Il est également nécessaire de vérifier le source de la classe pour voir comment equals() et hashCode() sont implémentés. Par exemple, Byte, Character, Short et Integer renvoient tous la valeur entière représentée sous forme de code de hachage. Cela peut ou non répondre à vos besoins.
Utiliser des tables de hachage en Java
Si vous souhaitez créer une table de hachage qui utilise les objets d'une classe que vous définissez comme clés, vous devez vous assurer que les méthodes equals() et hashCode() de cette classe fournissent des valeurs utiles. Examinez d’abord la classe que vous étendez pour déterminer si son implémentation répond à vos besoins. Sinon, vous devez surcharger la méthode.
La contrainte de conception de base de toute méthode equals() est qu'elle doit renvoyer true si l'objet qui lui est transmis appartient à la même classe et que ses champs de données sont définis sur des valeurs représentant les mêmes données. Vous devez également vous assurer que si vous transmettez un argument vide à la méthode, votre code renvoie
Copiez le code comme suit :
false：booléen public égal(Objet o)
{
si ( (o == nul)
|| !(l'instance de maClasse))
{
renvoie faux ;
}
// Comparez maintenant les champs de données...
De plus, vous devez garder à l’esprit certaines règles lors de la conception d’une méthode hashCode(). Premièrement, la méthode doit renvoyer la même valeur pour un objet particulier, quel que soit le nombre de fois où la méthode est appelée (bien sûr, tant que le contenu de l'objet ne change pas entre les appels. Lorsque vous utilisez un objet comme clé de table de hachage, cela devrait être évité). Deuxièmement, si deux objets définis par votre méthode equals() sont égaux, ils doivent également générer le même code de hachage. Troisièmement, et il s’agit plus d’une ligne directrice que d’un principe, vous devriez essayer de concevoir votre méthode de manière à ce qu’elle produise des résultats différents pour différents contenus d’objet. Cela n'a pas d'importance si, de temps en temps, différents objets génèrent le même code de hachage. Cependant, si la méthode ne peut renvoyer que des valeurs comprises entre 1 et 10, alors seules 10 listes peuvent être utilisées, quel que soit le nombre de listes dans la table de hachage.
Un autre facteur à garder à l’esprit lors de la conception d’equals() et de hashCode() est la performance. Chaque appel à put () ou get() implique d'appeler hashCode() pour trouver la bonne liste. Lorsque get() scanne la liste pour trouver la clé, il appelle equals() pour chaque élément de la liste. Implémentez ces méthodes afin qu'elles s'exécutent aussi rapidement et efficacement que possible, en particulier si vous envisagez de rendre votre classe accessible au public, car d'autres utilisateurs voudront peut-être utiliser votre classe dans une application hautes performances où la vitesse d'exécution est importante.
Performances des tables de hachage
Le principal facteur affectant l'efficacité de hashtable est la longueur moyenne des listes dans le tableau, car le temps de recherche moyen est directement lié à cette longueur moyenne. Évidemment, pour réduire la longueur moyenne, vous devez augmenter le nombre de listes dans la table de hachage ; vous obtiendrez la meilleure efficacité de recherche si le nombre de listes est si grand que la plupart ou la totalité des listes ne contiennent qu'un seul enregistrement. Cependant, cela va peut-être trop loin. Si votre table de hachage contient beaucoup plus de listes que d'entrées de données, vous n'avez pas besoin de générer un tel coût en mémoire et, dans certains cas, il est impossible pour les utilisateurs d'accepter cette approche.
Dans notre exemple précédent, nous savions à l’avance combien d’enregistrements nous avions, 1 000. Sachant cela, nous pouvons décider du nombre de listes que notre table de hachage doit contenir pour obtenir le meilleur compromis entre vitesse de recherche et efficacité d'utilisation de la mémoire. Cependant, dans de nombreux cas, vous ne savez pas à l'avance combien d'enregistrements vous allez traiter ; le fichier à partir duquel les données sont lues peut croître continuellement ou le nombre d'enregistrements peut changer considérablement de jour en jour.
Les classes Hashtable et HashMap gèrent ce problème en étendant dynamiquement la table à mesure que des entrées sont ajoutées. Les deux classes ont des constructeurs qui acceptent le nombre initial de listes dans la table et un facteur de charge comme paramètre :
Table de hachage publique (
int Capacité initiale,
facteur de charge flottant)
HashMap publique (
int Capacité initiale,
facteur de charge flottant)
Multipliez ces deux nombres pour calculer une valeur critique. Chaque fois qu'une nouvelle entrée est ajoutée à la table de hachage, le décompte est mis à jour et lorsque le décompte dépasse une valeur critique, la table est réinitialisée (rehachage). (La taille de la liste est augmentée jusqu'à doubler la taille précédente plus 1, et toutes les entrées sont déplacées vers la liste correcte.) Le constructeur par défaut définit la capacité initiale sur 11 et le facteur de charge sur 0,75, donc la valeur critique est de 8. Lorsque le neuvième enregistrement est ajouté à la table, la table de hachage est redimensionnée de manière à contenir 23 listes et la nouvelle valeur critique sera 17 (la partie entière de 23*0,75). Vous pouvez voir que le facteur de charge est une limite supérieure du nombre moyen de listes dans une table de hachage, ce qui signifie que, par défaut, une table de hachage comporte rarement de nombreuses listes contenant plus d'un enregistrement. Comparez notre exemple original, où nous avions 1 000 enregistrements répartis sur 10 listes. Si nous utilisons les valeurs par défaut, ce tableau s'étendra pour contenir plus de 1 500 listes. Mais vous pouvez contrôler cela. Si le nombre de listes multiplié par le facteur de charge est supérieur au nombre d'entrées que vous traitez, le tableau ne sera jamais refait, on peut donc suivre l'exemple ci-dessous :
Copiez le code comme suit :
// La table ne sera pas remaniée tant qu'elle
// a 1 100 entrées (10*110) :
Table de hachage maTableHash =
nouvelle table de hachage (10, 110.0F) ;
Vous ne voudrez probablement pas faire cela à moins que vous ne souhaitiez pas économiser de la mémoire pour des listes vides et que le temps de recherche supplémentaire ne vous dérange pas, ce qui peut être le cas dans les systèmes embarqués. Cependant, cette approche peut être utile car la réinitialisation est coûteuse en termes de calcul, et cette approche garantit que la réinitialisation ne se produit jamais.
Notez que même si l'appel de put () peut entraîner une croissance de la table (augmenter le nombre de listes), l'appel de remove() n'aura pas l'effet inverse. Ainsi, si vous avez une grande table et que vous en supprimez la plupart des entrées, vous vous retrouverez avec une table grande mais presque vide.
Table de hachage et HashMap
Il existe trois différences importantes entre les classes Hashtable et HashMap. La première différence tient principalement à des raisons historiques. Hashtable est basé sur l'ancienne classe Dictionary et HashMap est une implémentation de l'interface Map introduite dans Java 1.2.
La différence la plus importante est peut-être que les méthodes de Hashtable sont synchrones, alors que les méthodes de HashMap ne le sont pas. Cela signifie que, même si vous pouvez utiliser une table de hachage dans une application multithread sans entreprendre aucune action particulière, vous devez de la même manière fournir une synchronisation externe pour une HashMap. Une méthode pratique consiste à utiliser la méthode statique synchroniséeMap() de la classe Collections, qui crée un objet Map thread-safe et le renvoie sous forme d'objet encapsulé. Les méthodes de cet objet vous permettent d'accéder de manière synchrone au HashMap sous-jacent. Le résultat est que vous ne pouvez pas interrompre la synchronisation dans la table de hachage lorsque vous n'en avez pas besoin (comme dans une application monothread), et la synchronisation ajoute beaucoup de temps système de traitement.
La troisième différence est que seul HashMap vous permet d'utiliser des valeurs nulles comme clé ou valeur d'une entrée de table. Un seul enregistrement dans un HashMap peut être une clé vide, mais n'importe quel nombre d'entrées peut être une valeur vide. Cela signifie que si la clé de recherche n'est pas trouvée dans la table, ou si la clé de recherche est trouvée mais qu'il s'agit d'une valeur nulle, alors get() renverra null. Si nécessaire, utilisez la méthode containKey() pour faire la distinction entre les deux situations.
Certaines informations suggèrent que lorsque la synchronisation est requise, utilisez Hashtable, sinon utilisez HashMap. Cependant, comme HashMap peut être synchronisé en cas de besoin, HashMap a plus de fonctions que Hashtable et n'est pas basé sur une ancienne classe, certaines personnes pensent que HashMap est préféré à Hashtable dans diverses situations.
À propos des propriétés
Parfois, vous souhaiterez peut-être utiliser une table de hachage pour mapper les chaînes clés aux chaînes de valeur. Il existe quelques exemples de chaînes d'environnement sous DOS, Windows et Unix. Par exemple, la chaîne de clé PATH est mappée à la chaîne de valeur C:/WINDOWS;C:/WINDOWS/SYSTEM. Les tables de hachage sont un moyen simple de les représenter, mais Java propose un autre moyen.
La classe Java .util.Properties est une sous-classe de Hashtable conçue pour être utilisée avec les clés et valeurs String. L'utilisation de l'objet Properties est similaire à celle de Hashtable, mais la classe ajoute deux méthodes permettant de gagner du temps que vous devez connaître.
La méthode Store() enregistre le contenu d'un objet Properties dans un fichier sous une forme lisible. La méthode Load() est exactement le contraire, utilisée pour lire le fichier et définir l'objet Properties pour qu'il contienne des clés et des valeurs.
Notez que, comme Properties étend Hashtable, vous pouvez utiliser la méthode put () de la superclasse pour ajouter des clés et des valeurs qui ne sont pas des objets String. Ce n'est pas conseillé. De plus, si vous utilisez store() avec un objet Properties qui ne contient pas d'objet String, store() échouera. Comme alternative à put () et get(), vous devez utiliser setProperty() et getProperty(), qui prennent des paramètres String.
D'accord, j'espère que vous savez maintenant comment utiliser les tables de hachage pour accélérer votre traitement.