Qu'est-ce que le hachage

C'est le processus de conversion d'un objet en une valeur entière. La valeur entière facilite l'indexation et des recherches plus rapides.

Qu'est-ce que HashMap

HashMap fait partie du framework de collection Java. Il utilise une technique appelée Hashing. Il implémente l'interface cartographique. Il stocke les données dans la paire Clé et Valeur. HashMap contient un tableau de nœuds et le nœud est représenté sous forme de classe. Il utilise un tableau et une structure de données LinkedList en interne pour stocker la clé et la valeur. Il y a quatre champs dans HashMap.

Avant de comprendre le fonctionnement interne de HashMap, vous devez connaître les méthodes hashCode() et equals().

Unix contre Windows

équivaut à():Il vérifie l'égalité de deux objets. Il compare les Clés, qu'elles soient égales ou non. C'est une méthode de la classe Object. Il peut être annulé. Si vous remplacez la méthode equals(), il est alors obligatoire de remplacer la méthode hashCode().hashCode() :C'est la méthode de la classe d'objet. Il renvoie la référence mémoire de l'objet sous forme entière. La valeur reçue de la méthode est utilisée comme numéro de compartiment. Le numéro du bucket est l'adresse de l'élément à l'intérieur de la carte. Le code de hachage de la clé nulle est 0.Seaux :Le tableau du nœud est appelé buckets. Chaque nœud a une structure de données comme une LinkedList. Plusieurs nœuds peuvent partager le même compartiment. Sa capacité peut être différente.

Insérer une paire clé-valeur dans HashMap

Nous utilisons la méthode put() pour insérer la paire clé et valeur dans le HashMap. La taille par défaut de HashMap est 16 (0 à 15).

Exemple

Dans l'exemple suivant, nous souhaitons insérer trois paires (Clé, Valeur) dans le HashMap.

 HashMap map = new HashMap(); map.put('Aman', 19); map.put('Sunny', 29); map.put('Ritesh', 39); 

Voyons à quel index la paire clé-valeur sera enregistrée dans HashMap. Lorsque nous appelons la méthode put(), elle calcule le code de hachage de la clé « Aman ». Supposons que le code de hachage de « Aman » soit 2657860. Pour stocker la clé en mémoire, nous devons calculer l'index.

Calcul de l'indice

Index minimise la taille du tableau. La formule de calcul de l'indice est la suivante :

 Index = hashcode(Key) & (n-1) 

Où n est la taille du tableau. Par conséquent, la valeur de l'indice pour « Aman » est :

java synchroniser

 Index = 2657860 & (16-1) = 4 

La valeur 4 est la valeur d'index calculée où la clé et la valeur seront stockées dans HashMap.

Collision de hachage

C'est le cas lorsque la valeur d'index calculée est la même pour deux clés ou plus. Calculons le code de hachage pour une autre clé « Sunny ». Supposons que le code de hachage de « Sunny » soit 63281940. Pour stocker la clé dans la mémoire, nous devons calculer l'index en utilisant la formule d'index.

 Index=63281940 & (16-1) = 4 

La valeur 4 est la valeur d'index calculée où la clé sera stockée dans HashMap. Dans ce cas, la méthode equals() vérifie que les deux clés sont égales ou non. Si les clés sont identiques, remplacez la valeur par la valeur actuelle. Sinon, connectez cet objet nœud à l’objet nœud existant via LinkedList. Par conséquent, les deux clés seront stockées à l’index 4.

De même, nous stockerons la clé « Ritesh ». Supposons que le code de hachage de la clé soit 2349873. La valeur de l'index sera 1. Par conséquent, cette clé sera stockée à l'index 1.

Méthode get() dans HashMap

La méthode get() est utilisée pour obtenir la valeur par sa clé. Il ne récupérera pas la valeur si vous ne connaissez pas la clé. Lorsque la méthode get(K Key) est appelée, elle calcule le code de hachage de la clé.

imprimer depuis Java

Supposons que nous devions récupérer la clé « Aman ». La méthode suivante sera appelée.

 map.get(new Key('Aman')); 

Il génère le code de hachage 2657860. Calculez maintenant la valeur d'index de 2657860 en utilisant la formule d'index. La valeur de l'indice sera de 4, comme nous l'avons calculé ci-dessus. La méthode get() recherche la valeur d'index 4. Elle compare le premier élément Key avec la Key donnée. Si les deux clés sont égales, alors il renvoie la valeur, sinon vérifiez l'élément suivant du nœud s'il existe. Dans notre scénario, il se trouve comme premier élément du nœud et renvoie la valeur 19.

Allons chercher une autre clé « Sunny ».

Le code de hachage de la clé « Sunny » est 63281940. La valeur d'index calculée de 63281940 est 4, comme nous l'avons calculé pour la méthode put(). Accédez à l'index 4 du tableau et comparez la clé du premier élément avec la clé donnée. Il compare également les clés. Dans notre scénario, la clé donnée est le deuxième élément et le suivant du nœud est nul. Il compare le deuxième élément Key avec la Key spécifiée et renvoie la valeur 29. Il renvoie null si le prochain du nœud est nul.