Je pense que ce sera plus utile si j’explique les HashMaps en anglais.

Qu’est-ce qu’un HashMap?

Un HashMap est une structure de données qui est capable de mettre en correspondance certaines clés avec certaines valeurs. Les clés et les valeurs peuvent être n’importe quoi. Par exemple, si je faisais un jeu, je pourrais lier chaque nom d’utilisateur à une liste d’amis, représentée par une liste de chaînes.

Pourquoi utiliser un HashMap?

Les HashMaps sont beaucoup plus rapides pour récupérer des données que les tableaux et les listes liées. Un tableau trié pourrait trouver une valeur particulière en O(log n) avec une recherche binaire. Cependant, une HashMap peut vérifier si elle contient une clé particulière en O(1). Toutes les clés doivent être uniques.

Comment fonctionnent les HashMaps ?

Les HashMaps utilisent un tableau en arrière-plan. Chaque élément du tableau est une autre structure de données (généralement une liste chaînée ou un arbre de recherche binaire). Le HashMap utilise une fonction sur la clé pour déterminer où placer la valeur de la clé dans le tableau. Par exemple, si mon HashMap accepte les Strings… les fonctions de hachage possibles peuvent être :

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

La valeur retournée déterminera l’index dans lequel la valeur va dans le tableau.

Mais attendez ! Il y a un problème !

Il est possible que la valeur retournée soit en dehors des limites du tableau. Par conséquent, nous sommes censés moduler la valeur retournée par la longueur des tableaux.

return Math.abs(number%hashMapArray.length);

Collisions:

N’est-il pas possible que plusieurs clés fassent que la fonction de hachage génère le même indice ? Oui. Par exemple, si nous avons utilisé la première fonction de hachage présentée ci-dessus dans une carte de hachage de chaînes de caractères… toutes deux chaînes de caractères qui commencent par la même lettre recevront le même indice de tableau.

C’est ce qu’on appelle une collision.

Comment gérons-nous les collisions ?

Une technique de gestion des collisions est appelée chaînage. Comme chaque élément du tableau est une liste chaînée (ou une structure de données similaire), plusieurs clés qui ont la même valeur de hachage seront placées dans la même liste chaînée ou « seau ». Ensuite, la carte de hachage est capable de récupérer des valeurs en calculant le code de hachage avec la fonction de hachage, et en recherchant la liste liée particulière pour voir si elle contient une valeur avec la même clé.

Une bonne fonction de hachage doit être écrite pour éviter les collisions.

Avantages du chaînage :

-Le tableau ne peut pas déborder

-Les données peuvent être facilement supprimées

Inconvénients du chaînage :

-Peut subir un coup de performance si les seaux contiennent de très longues listes chaînées.

Le nombre total d’entrées par rapport au nombre de seaux est appelé le facteur de charge. Si le facteur de charge est trop faible, beaucoup d’espace est gaspillé. Si le facteur de charge est trop élevé, l’avantage du hachage est perdu. Un bon compromis pour le facteur de charge est .75

.