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

Vous semblez mélanger le comportement du pire des cas avec l'exécution moyenne (attendue). 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, couplée à un demi-hachage 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 analysés, en utilisant equals 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, il faudra parfois comparer avec quelques éléments, mais généralement c'est beaucoup plus proche de O(1) que de O(n). À des fins pratiques, c'est tout ce que vous devez savoir.

Rappelez - vous 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 w. r. t. le nombre d'éléments dans le conteneur. Donc, s'il faut en moyenne 4 comparaisons pour trouver un élément dans un conteneur avec 100 éléments, il faut également une moyenne de 4 comparaisons pour trouver un élément dans un conteneur avec 10000 éléments, et pour tout autre nombre d'éléments (il y a toujours un peu de variance, en particulier autour des points où le hachage tableau rehashes, et quand il y a un très petit nombre d'articles).

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 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 finalement pas rechercher en temps constant (et la notation O est définie en termes de nombres qui peuvent devenir arbitrairement grands).

Mais il ne s'ensuit pas que la complexité en temps réel est O(n) because parce qu'il n'y a pas de règle qui dit que les seaux doivent être mis en œuvre comme une liste linéaire.

En fait, Java 8 implémente les compartiments comme 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).
Comme n devient grand, le nombre d'éléments dans chaque compartiment est en moyenne 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. Il peut être trompeur lorsqu'il est appliqué à certains algorithmes, et les tables de hachage en sont un exemple. Nous choisissons le nombre de seaux basés sur le nombre d'éléments que nous nous attendons à traiter. Lorsque n est à peu près de 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) où k est le nombre de compartiments.

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 table de hachage étant O(1) fait référence au temps attendu dans le cas moyen, pas aux performances strictes du pire cas. Pour une table de hachage résolvant les collisions avec chaînage (comme hashmap 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 n'est pas supérieur à 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 considérer le pire des cas temps 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 Θ(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 à temps constant, vous peut lire sur dynamic perfect hashing qui résout récursivement 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 de développer 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.

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 présentes, vous devez faire 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 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é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 meilleurs cas de recherche et les cas moyens restent constants, c'est-à-dire O(1).

Universitaires mis à part, d'un point de vue pratique, les HashMaps doivent être acceptés comme ayant un impact sur les performances sans conséquence (sauf si votre profileur vous indique le contraire.)

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

Les éléments à l'intérieur du HashMap sont stockés sous la forme d'un tableau de liste chaînée (nœud), chaque liste chaîné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 manière pour déterminer l'emplacement du seau pour clé. Dans le meilleur des cas, chaque hashcode est unique et entraîne 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 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 entraîne une traversée de la liste entière qui conduit à O(n).

Dans le cas de java 8, le compartiment de liste chaînée 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).

Bien sûr, 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 soit 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 des 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 de sorte que cela ne change pas-mais cela désactive également le verrouillage biaisé, mais c'est une autre discussion), donc le risque de collisions est très faible.