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

J'ai vu des revendications intéressantes sur les hashmaps SO re 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 de l'un 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 O(1).

Quelqu'un peut-il expliquer s'ils sont O (1) et, si oui, comment ils y parviennent?

Une caractéristique particulière d'un HashMap est que contrairement, disons, aux arbres équilibrés, son comportement est probabiliste. Dans ces cas, il serait généralement plus utile de parler de complexité en termes de probabilité qu'un événement du pire des cas se produise. Pour une carte de hachage, c'est bien sûr le 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 avec même un nombre modeste d'éléments est susceptible de connaître 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 de hachage. On pourrait plutôt penser à la probabilité d'au plus 2 collisions.

p _{collision x 2} = (n / capacité) ²

C'est beaucoup plus bas. Étant donné que 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 réellement changer l'algorithme! Nous pouvons généraliser ceci pour

p _{collision xk} = (n / capacité) ^k

Et maintenant, nous pouvons ignorer un certain nombre arbitraire de collisions et nous retrouver avec une probabilité minime de plus de collisions que ce que nous comptons. Vous pouvez obtenir la probabilité à un niveau arbitrairement minuscule en choisissant le k correct, le tout sans modifier l'implémentation réelle de l'algorithme.

Nous en parlons en disant que la carte de hachage a un accès O (1) avec une probabilité élevée

Vous semblez confondre le comportement du pire des cas 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 n'utilisant pas un hachage parfait) mais cela est rarement pertinent en 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 très petit facteur (2, en fait) dans le cas attendu, dans une marge de variance très étroite.

En Java, HashMap fonctionne en utilisant hashCode pour localiser un compartiment. Chaque compartiment est une liste d'éléments résidant dans ce compartiment. Les éléments sont scanné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.

Donc, parfois, il devra comparer avec quelques éléments, mais généralement il est beaucoup plus proche de O (1) que de O (n). Pour des raisons pratiques, c'est tout ce que vous devez 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 vérifiés reste 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 de 100 articles, il faut également 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 un peu de variance, en particulier autour des points auxquels la table de hachage se répète, et lorsqu'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 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 comme le nombre d'éléments devient arbitrairement grand, vous ne pourrez finalement pas rechercher en temps constant (et la notation O est définie en termes de nombres qui peuvent devenir arbitrairement grand).

Mais il ne s'ensuit pas que la complexité en temps réel est O(n) car il n'y a pas de règle qui stipule que les seaux doivent être implémentés sous forme de liste linéaire.

En fait, Java 8 implémente les buckets comme TreeMapsune fois qu'ils dépassent un seuil, ce qui rend l'heure réelle 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).
Lorsque n devient grand, le nombre d'éléments dans chaque compartiment est en moyenne de n / b. Si la résolution de collision est effectuée 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 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 bon exemple. Nous choisissons le nombre de seaux en fonction du nombre d'éléments que nous prévoyons de traiter. Lorsque n est à peu près de la même taille que b, alors la recherche est à peu près en temps constant, mais nous ne pouvons pas l'appeler O (1) car O est défini en termes de limite comme n → ∞.

O(1+n/k) où k est le nombre de seaux.

Si l'implémentation est définie, k = n/alphaalors c'est O(1+alpha) = O(1)puisque alphaest une constante.

Nous avons établi que la description standard des recherches de table de hachage étant O (1) se réfère au temps moyen prévu dans le cas, pas aux performances strictes dans le pire des cas. Pour une table de hachage résolvant des collisions avec chaînage (comme la table de hachage de Java), 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 ne dépasse pas un facteur constant supérieur à la taille de la table.

Il a également été expliqué qu'à 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 temps prévu le plus défavorable , 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 Θ (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 attendus à temps constant, vous pouvez en savoir plus sur le hachage dynamique parfait qui résout les collisions de manière récursive avec une autre table de hachage!

Ce n'est O (1) que 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 du HashMap sont stockés sous forme de tableau de liste liée (nœud), chaque liste liée du tableau représente un compartiment pour la valeur de hachage unique d'une ou plusieurs clés.
Lors de l'ajout d'une entrée dans le 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 & 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 aboutit à un compartiment unique pour chaque clé.Dans ce cas, la méthode get passe du temps uniquement à déterminer l'emplacement du compartiment et à récupérer la valeur qui est la 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 bucket, cela se traduit par une traversée de la liste entière qui mène à O (n).

Dans le cas de java 8, le compartiment Linked List est remplacé par un TreeMap si la taille augmente à plus de 8, cela réduit l'efficacité de la recherche dans le pire des cas à O (log n).

Cela vaut essentiellement pour la plupart des implémentations de table 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 la table, vous n'avez qu'à faire une seule recherche, donc le temps d'exécution est O (1). S'il y a des collisions, 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 où 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, c'est-à-dire O (n). Cependant, la probabilité que cela se produise est négligeable et les cas de recherche meilleurs et moyens restent constants, c'est-à-dire O (1).

Les universitaires mis à part, d'un point de vue pratique, les HashMaps devraient être acceptés comme ayant un impact sans conséquence sur les performances (à moins que votre profileur ne vous dise le contraire).

Seulement dans le cas théorique, lorsque les codes de hachage sont toujours différents et que le compartiment pour chaque code de hachage est également différent, le O (1) existera. Sinon, il est d'ordre constant ie sur incrément de hashmap, son ordre de recherche reste constant.

Bien entendu, les performances du 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 la possibilité de collisions est très faible, elle aura de très bonnes performances (ce n'est pas strictement O (1) dans tous les cas possibles mais c'est dans la plupart cas).

Par exemple, l'implémentation par défaut dans Oracle JRE 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 c'est une autre discussion) donc le risque de collisions est très lent.