Un hashmap Java est-il vraiment O (1)?
https://stackoverflow.com/questions/1055243
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai vu des affirmations intéressantes sur SO concernant les hashmaps Java et leur O(1) temps de recherche. Quelqu'un peut-il expliquer pourquoi il en 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 ensemble de données contenant des collisions.
Dans ce cas, la recherche serait O(n) plutôt que <=>.
Quelqu'un peut-il expliquer s'il est O (1) et, dans l'affirmative, comment y parvient-il?
La solution
L’une des caractéristiques particulières d’une carte de hachage est que, contrairement aux arbres équilibrés, par exemple, son comportement est probabiliste. Dans ces cas, il est généralement plus utile de parler de complexité en termes de probabilité d’événement pire. Pour une carte de hachage, il s’agit bien entendu du cas d’une collision par rapport au niveau de remplissage de la carte. Une collision est assez facile à estimer.
p
collision = n / capacité
Ainsi, une carte de hachage comportant même un nombre modeste d’éléments risque au moins une collision. La notation Big O nous permet de faire quelque chose de plus convaincant. Observez cela 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.
p
collision x 2 = (n / capacité) 2
C'est beaucoup plus bas. Comme le coût de la gestion d'une collision supplémentaire est sans incidence sur les performances Big O, nous avons trouvé un moyen d'améliorer les performances sans changer réellement l'algorithme! Nous pouvons généraliser cela à
p
collision x k = (n / capacité) k
Et maintenant, nous pouvons ignorer un nombre arbitraire de collisions et aboutir à une probabilité extrêmement infime de plus de collisions que nous n'en comptons. Vous pouvez obtenir la probabilité à un niveau arbitrairement minime en choisissant le k correct, sans modifier l’implémentation réelle de l’algorithme.
Nous en parlons en disant que la table de hachage a un accès O (1) avec une probabilité élevée
Autres conseils
Vous semblez confondre le comportement dans le cas le plus défavorable avec une exécution moyenne (attendue). Le premier est bien O (n) pour les tables de hachage en général (c’est-à-dire qu’il n’utilise pas un hachage parfait), mais cela est rarement pertinent dans la pratique.
Toute implémentation de table de hachage fiable, associée à un hachage décent, a une performance d'extraction de O (1) avec un facteur très faible (2, en fait) dans le cas attendu, avec 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 numérisés, en utilisant des égaux pour la comparaison. Lors de l'ajout d'éléments, HashMap est redimensionné dès 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 dont vous avez besoin de savoir.
N'oubliez pas que o (1) ne signifie pas que chaque recherche n'examine qu'un seul élément. Cela signifie que le nombre moyen d'éléments cochés reste constant dans 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 de 100 articles, il devrait en faire en moyenne 4 comparaisons pour trouver un article dans un conteneur de 10000 articles, et pour tout autre nombre d'articles (il y a toujours peu de variance, en particulier autour des points où la table de hachage est réorganisée, et quand il y a un très petit nombre d’articles).
Ainsi, les collisions n'empêchent pas le conteneur d'avoir des opérations o (1), tant que le nombre moyen de clés par compartiment 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, une carte de hachage n'est pas vraiment O(1) à proprement parler, car à mesure que le nombre d'éléments devient arbitrairement grand, vous ne pourrez éventuellement pas effectuer de recherche en temps constant (et la notation O est définie) en termes de nombre qui peut devenir arbitrairement grand).
Mais il ne s'ensuit pas que la complexité en temps réel est O(n) - car aucune règle ne dit que les compartiments doivent être implémentés sous forme de liste linéaire.
En fait, Java 8 implémente les compartiments comme TreeMaps une fois qu'ils dépassent un seuil, ce qui donne l'heure actuelle O(log n).
Si le nombre de compartiments (appelez-le b) est maintenu constant (cas habituel), la recherche est en réalité O (n).
Comme n devient grand, le nombre d'éléments dans chaque compartiment est en moyenne n / b. Si la résolution de la collision est effectuée de l’une des manières habituelles (liste liée par exemple), la recherche est effectuée sur O (n / b) = O (n).
La notation O concerne ce qui se passe lorsque n devient de plus en plus grand. Cela 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 auxquels nous nous attendons. Lorsque n est environ de la même taille que b, 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 & # 8594; & # 8734;.
O(1+n/k) où k est le nombre de compartiments.
Si l'implémentation définit k = n/alpha, il s'agit de O(1+alpha) = O(1) car alpha est une constante.
Nous avons établi que la description standard des recherches dans les tables de hachage, étant O (1), fait référence à la durée moyenne attendue par cas, et non à la performance dans le pire des cas. 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 + & # 945;) avec une bonne fonction de hachage , où & # 945; 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'il était possible à proprement parler de construire une entrée nécessitant des recherches O ( n ) pour toute fonction de hachage déterministe. Mais il est également intéressant de prendre en compte le
cas attendu , qui est différent du temps de recherche moyen. En utilisant le chaînage, c’est O (1 + la longueur de la plus longue chaîne), par exemple & # 920; (journal n / journal journal n ) lorsque & # 945; = 1.
Si des solutions théoriques vous permettent d'obtenir des recherches dans le pire des cas dans le pire des cas, vous pouvez en savoir plus sur hachage dynamique parfait qui résout les collisions 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 mauvaises fonctions de hachage.
Que vous ayez besoin d'agrandir la table lorsque vous ajoutez des éléments ou non n'est pas pertinent pour la question, car il s'agit du temps de recherche.
Les éléments à l'intérieur de HashMap sont stockés sous la forme d'un tableau de liste liée (nœud), chaque liste liée du tableau représentant un compartiment pour la valeur de hachage unique d'une ou de plusieurs clés.
Lors de l'ajout d'une entrée dans HashMap, le hashcode de la clé est utilisé pour déterminer l'emplacement du compartiment dans le tableau, quelque chose comme:
location = (arraylength - 1) & keyhashcode
Ici, le & amp; représente l'opérateur AND au niveau du bit.
Par exemple: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")
Pendant l'opération get, il utilise la même méthode pour déterminer l'emplacement du compartiment pour la clé. Dans le meilleur des cas, chaque clé a un hashcode unique et génère un compartiment unique pour chaque clé. Dans ce cas, la méthode get consacre du temps uniquement à déterminer l'emplacement du compartiment 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 compartiment, ce qui conduit à parcourir toute la liste, ce qui conduit à O (n).
Dans le cas de java 8, le compartiment de la liste liée est remplacé par une TreeMap si la taille dépasse 8, ce qui réduit l'efficacité de la recherche dans le pire des cas à 0 (log n).
Cela vaut 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 aucune collision dans la table, vous ne devez effectuer qu'une seule recherche. Par conséquent, la durée d'exécution est O (1). En cas de collision, vous devez effectuer plus d’une recherche, 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 des cas 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, par exemple O (n). Cependant, la probabilité que cela se produise est négligeable et les recherches dans les cas les meilleurs et les cas moyens restent constantes, c’est-à-dire O (1).
Hormis les universitaires, d’un point de vue pratique, HashMaps devrait être accepté 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 chaque compartiment est différent, le O (1) existera. Sinon, il est d'ordre constant, c'est-à-dire que, lors de l'incrémentation de hashmap, son ordre de recherche reste constant.
Bien sûr, les performances de hashmap dépendront de la qualité de la fonction hashCode () pour l’objet donné. Cependant, si la fonction est implémentée de telle sorte que le risque de collision soit très faible, les performances seront très bonnes (il ne s’agit pas strictement de O (1) dans tous les cas possibles, mais dans la plupart des cas).
Par exemple, l'implémentation par défaut dans l'environnement JRE Oracle consiste à utiliser un nombre aléatoire (qui est stocké dans l'instance d'objet afin qu'il ne change pas - mais il désactive également le verrouillage biaisé, mais il s'agit d'une autre discussion). des collisions est très faible.
