Java est hashmap vraiment O(1)?
j'ai vu des affirmations intéressantes sur les hashmaps de Java et leur temps de recherche O(1) . Quelqu'un peut m'expliquer pourquoi il en est ainsi? À moins que ces hashmaps soient très différents des algorithmes de hachage sur lesquels j'ai été acheté, il doit toujours exister un ensemble de données qui contient des collisions.
, Dans ce cas, la recherche serait O(n) plutôt que O(1) .
peut-on expliquer si sont O (1) et, dans l'affirmative, comment y parvenir?
15 réponses
une caractéristique particulière d'un HashMap est que contrairement, disons, aux arbres équilibrés, son comportement est probabiliste. Dans ces cas, il est généralement plus utile de parler de la complexité en termes de probabilité du pire cas d'événement survenant serait. Pour une carte hachurée, c'est bien sûr le cas d'une collision par rapport à la longueur de la carte. Une collision est assez facile à estimer.
P collision = n / Capacité
donc une carte de hachage avec même un nombre modeste d'éléments est assez susceptible d'éprouver au moins une collision. La notation Big O nous permet de faire quelque chose de plus convaincant. Observez que pour toute constante fixe arbitraire K.
O (n) = O(k * n)
nous pouvons utiliser cette fonctionnalité pour améliorer les performances de la carte hash. On pourrait plutôt penser à la probabilité d'au plus 2 collisions.
P collision x 2 = (n / Capacité) 2
c'est beaucoup plus bas. Puisque le coût de gestion d'une collision supplémentaire n'est pas pertinent pour les performances de Big O, nous avons trouvé un moyen d'améliorer les performances sans changer l'algorithme! Nous pouvons généraliser cela à
P collision x k = (n / Capacité) k
Et maintenant, nous pouvons ignorer certains nombre arbitraire de collisions et extrêmement infime probabilité de plus de collisions que nous sommes comptables. Vous pourriez obtenir la probabilité à un niveau arbitrairement minuscule En choisissant le k correct, tout sans modifier l'implémentation réelle de l'algorithme.
nous parlons de cela en disant que le hash-map A O (1) accès avec haute probabilité
vous semblez confondre le comportement du pire avec l'exécution du scénario moyen (prévu). Le premier est en effet O(n) pour les tables de hachage en général (c.-à-d. n'utilisant pas un hachage parfait), mais cela est rarement pertinent dans la pratique.
toute mise en œuvre fiable d'une table de hachage, 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 prévu, à l'intérieur d'une marge de variance très étroite.
en Java, HashMap fonctionne en utilisant hashCode pour localiser un seau. Chaque seau est une liste d'articles résidant dans ce seau. Les articles sont balayés, en utilisant des égaux pour la comparaison. Lors de l'ajout d'éléments, le HashMap est redimensionné une fois qu'un certain pourcentage de charge est atteint.
ainsi, parfois il devra comparer avec quelques articles, mais en général il est beaucoup plus proche de O(1) Que 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 ne porte que sur un seul article-cela signifie que le nombre moyen d'articles vérifiés reste constant W. R. T. le nombre d'articles dans le conteneur. Donc, s'il faut en moyenne 4 comparaisons pour trouver un article dans un conteneur avec 100 Articles, il devrait également prendre une moyenne de 4 comparaisons pour trouver un article dans un conteneur avec 10000 articles, et pour tout autre nombre d'articles (Il ya toujours un peu de variance, en particulier autour des points à laquelle la table de hash se ressasse, et quand il y a un très petit nombre d'articles).
ainsi, les collisions n'empêchent pas le conteneur d'effectuer des opérations o(1), tant que le nombre moyen de clés par godet reste 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 qu'une carte de hachage n'est pas vraiment O(1) , à proprement parler, parce que comme le nombre d'éléments devient arbitrairement grand, éventuellement vous ne serez pas en mesure de rechercher en temps constant (et o-notation est défini en termes de nombres qui peuvent obtenir arbitrairement grand).
mais il ne s'ensuit pas que la complexité en temps réel est O(n) -- parce que il n'y a aucune règle qui dit que les seaux doivent être mis en œuvre comme une liste linéaire.
en fait, Java 8 implémente les seaux comme TreeMaps une fois qu'ils dépassent un seuil, ce qui rend le temps réel O(log n) .
si le nombre de seaux (appelez-le b) est maintenu constant (le cas habituel), alors la recherche est en fait O(n).
lorsque n devient grand, le nombre d'éléments dans chaque seau est en moyenne n/b. Si la résolution de collision est faite de l'une des façons habituelles (liste liée par exemple), alors la recherche est O(n/B) = O(N).
Le O la notation est ce qui arrive lorsque n devient de plus en plus grandes. Il peut être trompeur lorsqu'il est appliqué à certains algorithmes, et les tables de hachage sont un cas au point. Nous choisissons le nombre de seaux en fonction du nombre d'éléments que nous prévoyons traiter. Quand n est à peu près de la même taille que b, alors la recherche est à peu près constante-temps, mais nous ne pouvons pas l'appeler O(1) parce que O est défini en termes d'une limite comme n → ∞.
O(1+n/k) où k est le nombre de seaux.
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 de tables de hachage de recherche étant O(1) se réfère à la moyenne-case temps prévu, pas la stricte pire des performances. Pour une table de hachage résoudre les collisions avec le chaînage (comme Java hashmap) c'est techniquement O(1+α) Avec une bonne fonction de hachage , Où α est le facteur de charge de la table. Toujours constant tant que le nombre d'objets que vous stockez n'est pas plus qu'un facteur constant supérieur à la taille de la table.
il a également été expliqué qu'à strictement parler il est possible de construire des inputs qui nécessitent des recherches O ( n ) pour n'importe quelle fonction de hachage déterministe. Mais il est également intéressant de considérer le pire des cas temps prévu , qui est différent du temps de recherche Moyen. En utilisant le chaînage c'est O(1 + La longueur de la chaîne la plus longue), par exemple Θ(log n / log n ) quand α=1.
si vous êtes intéressé par les moyens théoriques pour atteindre le temps constant prévu des recherches du pire des cas, vous pouvez lire sur Dynamic perfect hashing qui résout les collisions récursivement avec une autre table de hachage!
Il est O(1) seulement si votre fonction de hachage est très bon. L'implémentation de la table de hachage Java ne protège pas contre les mauvaises fonctions de hachage.
si vous avez besoin de faire pousser la table lorsque vous ajoutez des éléments ou non n'est pas pertinent à la question parce qu'il s'agit de temps de recherche.
cela vaut essentiellement pour 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 présentes dans le tableau, vous n'avez qu'à faire une seule recherche, donc le temps de fonctionnement est O(1). S'il y a des collisions présentes, vous devez faire plus d'une recherche, ce qui réduit la performance vers O(n).
Cela dépend de l'algorithme choisi pour éviter les collisions. Si votre implémentation utilise un enchaînement séparé, alors le pire des scénarios se produit lorsque chaque élément de données est hashé à 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érent d'une recherche linéaire sur une liste, i.e. O(n). Cependant, la probabilité que cela se produise est négligeable et les cas les meilleurs et les cas moyens demeurent constants, c.-à-d. O(1).
des Universitaires de côté, à partir d'un point de vue pratique, HashMaps devraient être acceptés comme une conséquence d'impact sur les performances (à moins que votre profiler vous dit le contraire.)
seulement dans le cas théorique, quand les hashcodes sont toujours différents et le seau pour chaque code de hachage est également différent, le O(1) existera. Dans le cas contraire, il est d'ordre constant, c'est-à-dire que sur incrément de hashmap, son ordre de recherche reste constant.
les éléments dans le HashMap sont stockés comme un tableau de liste liée (noeud), chaque liste liée dans le tableau représente un seau pour la valeur de hachage unique d'une ou plusieurs clés.
En ajoutant une entrée dans le HashMap, le hashcode de la clé est utilisé pour déterminer l'emplacement du seau dans le tableau, quelque chose comme:
location = (arraylength - 1) & keyhashcode
ici le & représente bitwise et l'opérateur.
par exemple: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")
Pendant l'opération, il utilise la même façon de déterminer l'emplacement de seau pour la clé. Dans le meilleur des cas, chaque hashcode est unique et produit un seau unique pour chaque clé, dans ce cas la méthode get passe du temps seulement pour déterminer l'emplacement du seau et récupérer la valeur qui est constante O(1).
dans le pire des cas, toutes les clés ont le même hashcode et sont stockées dans le même seau, ce qui a pour résultat de traverser toute la liste qui mène à O(n).
dans le cas de java 8, le panier de la liste liée est remplacé par un bloc-notes si la taille dépasse 8, ce qui réduit L'efficacité de la recherche du pire cas à O(log n).
bien sûr, la performance du hashmap dépendra de la qualité de la fonction hashCode() pour l'objet donné. Cependant, si la fonction est implémentée de telle sorte que la possibilité de collisions est très faible, elle aura une très bonne performance (ce n'est pas strictement O(1) dans chaque cas possible mais c'est dans la plupart cas possibles).
par exemple l'implémentation par défaut dans L'Oracle JRE est d'utiliser un nombre (qui est stocké dans l'instance de l'objet pour qu'il ne change pas - mais il désactive également le verrouillage biaisé, mais c'est une autre discussion) donc le risque de collisions est très faible.