Un hashmap Java est-il vraiment O (1)?

J’ai vu des affirmations intéressantes sur les hashaps Java SO et leur temps de recherche O(1) . Est-ce que quelqu’un peut expliquer pourquoi c’est ainsi? À moins que ces hashmaps ne soient très différents des algorithmes de hachage sur lesquels j’ai été acheté, il doit toujours exister un dataset contenant des collisions.

Dans ce cas, la recherche serait O(n) plutôt que O(1) .

Est-ce que quelqu’un peut expliquer s’ils sont O (1) et, dans l’affirmative, comment ils y parviennent?

Une caractéristique particulière d’un HashMap est que, contrairement aux arbres équilibrés, par exemple, leur comportement est probabiliste. Dans ces cas, il est généralement plus utile de parler de complexité en termes de probabilité de survenance d’un événement le plus défavorable. Pour une carte de hachage, il s’agit bien sûr d’une collision avec la carte. Une collision est assez facile à estimer.

collision p = n / capacité

Ainsi, une carte de hachage contenant même un nombre modeste d’éléments risque fort d’avoir au moins une collision. La grande notation O nous permet de faire quelque chose de plus convaincant. Observez que pour toute constante arbitraire, fixe k.

O (n) = O (k * n)

Nous pouvons utiliser cette fonctionnalité pour améliorer les performances de la carte de hachage. Nous pourrions plutôt penser à la probabilité d’au plus 2 collisions.

collision p x 2 = (n / capacité) 2

C’est beaucoup plus bas. Étant donné que le coût d’une collision supplémentaire est sans importance pour les performances de Big O, nous avons trouvé un moyen d’améliorer les performances sans modifier réellement l’algorithme! Nous pouvons généraliser cela pour

p collision xk = (n / capacité) k

Et maintenant, nous pouvons ignorer un nombre arbitraire de collisions et nous retrouver avec une probabilité infime de plus de collisions que nous ne le pensons. Vous pouvez obtenir la probabilité à un niveau arbitrairement petit en choisissant le k correct, sans modifier l’implémentation réelle de l’algorithme.

Nous parlons de cela en disant que le hash-map a un access O (1) avec une forte probabilité

Vous semblez confondre le comportement le plus défavorable avec le temps d’exécution moyen (attendu). Le premier est en effet O (n) pour les tables de hachage en général (c’est-à-dire ne pas utiliser un hachage parfait), mais cela est rarement pertinent dans la pratique.

Toute implémentation de table de hachage fiable, associée à un hachage à moitié décent, a une performance de récupération de O (1) avec un facteur très faible (2 en fait) dans le cas attendu, dans une marge de variance très étroite.

En Java, HashMap utilise hashCode pour localiser un compartiment. Chaque compartiment est une liste d’éléments résidant dans ce compartiment. Les articles sont scannés, en utilisant les mêmes pour la comparaison. Lors de l’ajout d’éléments, le HashMap est redimensionné une fois qu’un certain pourcentage de charge est atteint.

Donc, parfois, il faudra comparer quelques éléments, mais en général, il est beaucoup plus proche de O (1) que de O (n). Pour des raisons pratiques, c’est tout ce que vous devez savoir.

Rappelez-vous que o (1) ne signifie pas que chaque recherche examine uniquement un seul élément – cela signifie que le nombre moyen d’éléments vérifiés rest constant par rapport au nombre d’éléments dans le conteneur. Donc, s’il faut en moyenne 4 comparaisons pour trouver un article dans un conteneur contenant 100 articles, il faut également une moyenne de 4 comparaisons pour trouver un article dans un conteneur contenant 10 000 articles, et pour tout autre nombre d’articles (il y a toujours un peu de variance, surtout autour des points auxquels la table de hachage se rehausse, et quand il y a un très petit nombre d’éléments).

Les collisions n’empêchent donc pas le conteneur d’avoir des opérations o (1), tant que le nombre moyen de clés par compartiment rest dans une limite fixe.

Je sais que c’est une vieille question, mais il y a en fait une nouvelle réponse.

Vous avez raison de dire qu’une carte de hachage n’est pas vraiment O(1) , à proprement parler, car comme le nombre d’éléments devient arbitrairement grand, vous ne pourrez plus chercher en temps constant (et la notation O est définie en termes des nombres qui peuvent devenir arbitrairement grands).

Mais cela ne veut pas dire que la complexité en temps réel est O(n) car il n’y a pas de règle qui dit que les compartiments doivent être implémentés en tant que liste linéaire.

En fait, Java 8 implémente les buckets en tant que TreeMaps une fois qu’ils dépassent un seuil, ce qui rend le temps réel O(log n) .

Si le nombre de compartiments (appelez-le b) est maintenu constant (le cas habituel), alors la recherche est en fait O (n).
Au fur et à mesure que n augmente, le nombre d’éléments dans chaque compartiment est en moyenne n / b. Si la résolution de collision se fait de l’une des manières habituelles (liste chaînée par exemple), alors la recherche est O (n / b) = O (n).

La notation O concerne ce qui se passe quand n devient de plus en plus grand. Il peut être trompeur lorsqu’il est appliqué à certains algorithmes, et les tables de hachage en sont un exemple. Nous choisissons le nombre de compartiments en fonction du nombre d’éléments à traiter. Lorsque n a à peu près la même taille que b, alors la recherche est à peu près constante, mais nous ne pouvons pas l’appeler O (1) car O est défini en termes de limite comme n → ∞.

O(1+n/k)k est le nombre de godets.

Si l’implémentation définit k = n/alpha alors c’est O(1+alpha) = O(1) puisque alpha est une constante.

Nous avons établi que la description standard des recherches de tables de hachage, à savoir O (1), fait référence à la durée moyenne attendue, et non à la pire des performances. Pour une table de hachage résolvant les collisions avec le chaînage (comme le hashmap de Java), il s’agit techniquement de O (1 + α) avec une bonne fonction de hachage , où α est le facteur de charge de la table. Toujours constant tant que le nombre d’objects que vous stockez ne dépasse pas un facteur constant supérieur à la taille de la table.

Il a également été expliqué que, à proprement parler, il est possible de construire une entrée qui nécessite des recherches O ( n ) pour toute fonction de hachage déterministe. Mais il est également intéressant de prendre en compte le délai prévu le plus défavorable, qui est différent du temps de recherche moyen. L’utilisation du chaînage est O (1 + la longueur de la plus longue chaîne), par exemple example (log n / log log n ) lorsque α = 1.

Si vous êtes intéressé par des moyens théoriques pour obtenir des recherches dans le pire des cas, vous pouvez lire le hachage parfait dynamic qui résout les collisions de manière récursive avec une autre table de hachage!

C’est O (1) seulement si votre fonction de hachage est très bonne. L’implémentation de la table de hachage Java ne protège pas contre les fonctions de hachage incorrectes.

Que vous ayez besoin de développer la table lorsque vous ajoutez ou non des éléments n’est pas pertinent pour la question, car il s’agit de la durée de la recherche.

Cela concerne essentiellement la plupart des implémentations de tables de hachage dans la plupart des langages de programmation, car l’algorithme lui-même ne change pas vraiment.

S’il n’y a pas de collisions dans la table, il vous suffit de faire une seule recherche, donc le temps d’exécution est O (1). Si des collisions sont présentes, vous devez effectuer plusieurs recherches, ce qui réduit les performances vers O (n).

Cela dépend de l’algorithme que vous choisissez pour éviter les collisions. Si votre implémentation utilise un chaînage séparé, le pire scénario se produit lorsque chaque élément de données est haché à la même valeur (mauvais choix de la fonction de hachage par exemple). Dans ce cas, la recherche de données n’est pas différente d’une recherche linéaire sur une liste chaînée, à savoir O (n). Cependant, la probabilité que cela se produise est négligeable et les recherches les meilleures et les cas moyens restnt constants, à savoir O (1).

Les universitaires mis à part, d’un sharepoint vue pratique, les HashMaps doivent être considérés comme ayant un impact sur les performances sans conséquence (sauf indication contraire de votre profileur).

Seulement dans les cas théoriques, lorsque les codes de hachage sont toujours différents et que bucket pour chaque code de hachage est également différent, le O (1) existera. Sinon, il est d’ordre constant, c’est-à-dire qu’à l’incrément de hashmap, son ordre de recherche rest constant.

Les éléments à l’intérieur de HashMap sont stockés sous la forme d’un tableau de liste chaînée (nœud), chaque liste liée dans le tableau représente un compartiment pour une valeur de hachage unique d’une ou plusieurs clés.
Lors de l’ajout d’une entrée dans HashMap, le code de hachage de la clé est utilisé pour déterminer l’emplacement du compartiment dans le tableau, par exemple:

 location = (arraylength - 1) & keyhashcode 

Ici, le & représente l’opérateur ET bitwise.

Par exemple: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

Pendant l’opération, il utilise la même méthode pour déterminer l’emplacement du godet pour la clé. Dans le meilleur des cas, chaque code de hachage est unique et génère un compartiment unique pour chaque clé. Dans ce cas, la méthode get passe uniquement du temps à déterminer l’emplacement du compartiment et à récupérer la valeur constante O (1).

Dans le pire des cas, toutes les clés ont le même code de hachage et sont stockées dans le même compartiment, ce qui entraîne la traversée de la liste complète, ce qui conduit à O (n).

Dans le cas de java 8, le compartiment de la liste chaînée est remplacé par un TreeMap si la taille dépasse 8, ce qui réduit l’efficacité de la recherche dans le pire des cas à O (log n).

Bien sûr, les performances du hashmap dépendent de la qualité de la fonction hashCode () pour l’object donné. Cependant, si la fonction est implémentée de telle manière que la possibilité de collision est très faible, les performances seront très bonnes (ce n’est pas ssortingctement O (1) dans tous les cas possibles, mais dans la plupart des cas).

Par exemple, l’implémentation par défaut dans le JRE Oracle consiste à utiliser un nombre aléatoire (qui est stocké dans l’instance d’object pour qu’il ne change pas – mais désactive également le locking biaisé, mais il s’agit d’une autre discussion). très lent.