🙎🏽 🎙️ 🧒 Ce que vous devez savoir sur les collections basées sur le hachage 😯 👩🏼‍🌾 🎠

Bonjour à tous. En contact avec Vladislav Rodin. Actuellement, je dirige le cours d'architecte à charge élevée d'OTUS et j'enseigne également des cours sur l'architecture logicielle.

En plus d'enseigner, comme vous l'avez peut-être remarqué, j'écris également du matériel pour le blog OTUS sur Habré et je veux consacrer l'article d'aujourd'hui au lancement d'un nouveau flux du cours "Algorithmes pour les développeurs" .

introduction

Les tables de hachage (HashMap) ainsi que les tableaux dynamiques sont les structures de données les plus populaires utilisées en production. Très souvent, vous pouvez entendre des questions lors des entretiens concernant leur objectif, les caractéristiques de leur structure interne, ainsi que les algorithmes associés. Cette structure de données est classique et se retrouve non seulement en Java, mais aussi dans de nombreux autres langages de programmation.

Formulation du problème

Fixons un objectif pour créer une structure de données qui vous permet de:

contient (élément Element) vérifier si un élément s'y trouve ou non, pour O (1)
add (élément Element) ajoute un élément dans O (1)
delete (élément Element) supprimer un élément dans O (1)

Array

Essayons de faire ces opérations au-dessus d'un tableau, qui est la structure de données la plus simple. Nous convenons que nous considérerons la cellule vide si elle contient null.

Contrôle de disponibilité

Il est nécessaire d'effectuer une recherche linéaire dans le tableau, car l'élément peut potentiellement se trouver dans n'importe quelle cellule. De manière asymptotique, cela peut être fait dans O (n), où n est la taille du tableau.

Ajouter

Si nous devons ajouter un élément n'importe où, nous devons d'abord trouver une cellule vide, puis y écrire l'élément. Ainsi, nous effectuons à nouveau une recherche linéaire et obtenons le comportement asymptotique de O (n).

Supprimer

Pour supprimer un élément, vous devez d'abord le trouver, puis écrire null dans la cellule trouvée. Encore une fois, la recherche linéaire nous conduit à O (n).

L'ensemble de hachage le plus simple

Veuillez noter qu'à chaque opération, nous avons d'abord recherché l'index de la cellule souhaitée, puis effectué l'opération, et c'est la recherche qui gâche l'asymptotique pour nous! Si nous apprenions à obtenir cet indice pour O (1), le problème d'origine serait résolu.

Remplaçons maintenant la recherche linéaire par l'algorithme suivant: nous allons calculer la valeur d'une certaine fonction - une fonction de hachage qui mappe un objet de classe à un entier. Après cela, nous comparerons l'entier résultant à l'index de la cellule du tableau (c'est assez facile à faire, par exemple, en prenant le reste de diviser ce nombre par la taille du tableau). Si la fonction de hachage est écrite de telle manière qu'elle soit considérée comme O (1) (et elle est généralement écrite comme ceci), alors nous avons obtenu l'implémentation la plus simple de l' ensemble de hachage. Une cellule de tableau en termes d'ensemble de hachage peut être appelée un compartiment .

Les problèmes de la mise en œuvre la plus simple d'un ensemble de hachage

Peu importe comment la fonction de hachage est écrite, le nombre de cellules dans le tableau est toujours limité, tandis que l'ensemble d'éléments que nous voulons stocker dans la structure de données est illimité. Après tout, nous ne nous embêterions pas avec la structure des données s'il était nécessaire de sauvegarder seulement dix éléments précédemment connus, non? Cet état de choses conduit à des conflits inévitables . Une collision est une situation où, lors de l'ajout de différents objets, nous tombons dans la même cellule du tableau.

Deux méthodes ont été inventées pour résoudre les collisions: la méthode de chaînage et la méthode d'adressage ouvert .

Méthode de chaînage

La méthode de chaînage est la méthode la plus simple pour résoudre les collisions. Dans la cellule du tableau, nous ne stockerons pas les éléments, mais une liste chaînée de ces éléments. Parce que l'ajout en haut de la liste (et peu importe à quelle partie de la liste ajouter un élément) a le comportement asymptotique de O (1), nous ne gâcherons pas le comportement asymptotique général, et il restera égal à O (1).

Cette implémentation a un problème: si les listes grandissent beaucoup (en dernier recours, nous pouvons considérer une fonction de hachage qui renvoie une constante pour tout objet), alors nous obtenons l'asymptotique O (m), où m est le nombre d'éléments dans l'ensemble, si la taille tableau est fixe. Pour éviter de tels problèmes, le concept de rapport cyclique est introduit.(il peut être égal, par exemple, 1,5). Si lors de l'ajout d'un élément, il s'avère que la fraction du nombre d'éléments dans la structure de données par rapport à la taille du tableau dépasse le facteur de remplissage, alors ce qui se produit: un nouveau tableau est sélectionné dont la taille dépasse la taille de l'ancien tableau (par exemple, 2 fois), et la structure de données est reconstruite sur le nouveau tableau.

Cette méthode de résolution des collisions est utilisée en Java et la structure de données est appelée HashSet .

Méthode d'adressage ouvert

Dans cette méthode, les éléments eux-mêmes sont stockés dans les cellules, et en cas de collision, une séquence d'échantillons se produit , c'est-à-dire que nous commençons à trier les cellules à l'aide d'un algorithme dans l'espoir d'en trouver un libre. Cela peut être fait par différents algorithmes ( séquence d'échantillons linéaire / quadratique , double hachage ), chacun ayant ses propres problèmes (par exemple, l'émergence de grappes primaires ou secondaires ).

D'un ensemble de hachage à une table de hachage (HashMap)

Créons une structure de données qui vous permet d'ajouter, de supprimer, de rechercher des éléments, mais par une touche, aussi rapidement qu'un ensemble de hachage (c'est-à-dire au-delà de O (1)).

Nous utiliserons la même structure de données que l'ensemble de hachage, mais nous ne stockerons pas d'éléments, mais des paires d'éléments.

Ainsi, l'insertion (put (Key key, Value value)) sera effectuée comme suit: nous calculerons la cellule du tableau par un objet de type Key, nous obtiendrons le nombre de bucket. Passons en revue la liste dans le compartiment, en comparant la clé avec la clé dans les paires stockées. Si vous trouvez la même clé - extrayez simplement l'ancienne valeur, si vous ne l'avez pas trouvée - ajoutez une paire.

Comment un article est-il reçu par clé? Oui, selon un principe similaire: nous obtenons un compartiment par clé, parcourons les paires et retournons la valeur dans une paire, la clé dans laquelle est égale à la clé dans la demande, s'il existe une telle paire, et nulle sinon.

Cette structure de données est appelée table de hachage .

Questions d'entrevue typiques

Q: Comment sont organisés HashSet et HashMap? Comment se déroulent les principales opérations dans ces collections? Comment les méthodes equals () et hashCode () sont-elles appliquées?
R : Les réponses à ces questions se trouvent ci-dessus.

Q: Quel est le contrat pour equals () et hashCode ()? À quoi est-il dû?
R : Si les objets sont égaux, alors ils doivent avoir hashCode égal. Ainsi, hashCode doit être déterminé par la capacité des champs impliqués entre égaux. La violation de ce contrat peut entraîner des effets très intéressants. Si les objets sont égaux, mais que leur hashCode est différent, vous risquez de ne pas obtenir la valeur correspondant à la clé par laquelle vous venez d'ajouter l'objet au HashSet ou au HashMap.

Conclusion

Lors des entretiens, ils aiment poser différents cas liés à ces structures de données. De plus, la décision de n'importe lequel d'entre eux peut être déduite de la compréhension des principes de son travail sans «bourrage».

C'est tout. Si vous avez lu le matériel jusqu'à la fin, j'invite mon collègue Evgeny Volosatov à vous montrer comment résoudre le problème de l'olympiade en utilisant les idées de programmation dynamique pour une leçon gratuite sur le sujet "Les secrets de la programmation dynamique" .

Ce que vous devez savoir sur les collections basées sur le hachage