Complexité des entrées/sorties de HashMap

Question

Nous avons l'habitude de dire que HashMap get/put sont O(1). Cependant, cela dépend de l'implémentation du hachage. Le hachage d'objet par défaut est en fait l'adresse interne dans le tas de la JVM. Sommes-nous sûrs que c'est suffisant pour prétendre que le get/put sont O(1) ?

La mémoire disponible est un autre problème. D'après ce que je comprends des javadocs, la fonction HashMap load factor devrait être de 0,75. Que se passe-t-il si nous n'avons pas assez de mémoire dans la JVM et que la load factor dépasse la limite ?

Il semble donc que O(1) ne soit pas garanti. Est-ce que cela a un sens ou est-ce que je rate quelque chose ?

Answer 1

Cela dépend de beaucoup de choses. C'est généralement O(1), avec un hachage décent qui lui-même est en temps constant... mais vous pourriez avoir un hachage qui prend beaucoup de temps à calculer, et s'il y a plusieurs éléments dans la carte de hachage qui renvoient le même code de hachage, get devra itérer sur eux en appelant equals sur chacun d'entre eux pour trouver une correspondance.

Dans le pire des cas, un HashMap a un lookup O(n) en raison de la recherche de toutes les entrées dans le même seau de hachage (par exemple, si elles ont toutes le même code de hachage). Heureusement, ce pire scénario ne se produit pas très souvent dans la vie réelle, d'après mon expérience. Donc non, O(1) n'est certainement pas garanti - mais c'est généralement ce que vous devriez supposer lorsque vous considérez les algorithmes et les structures de données à utiliser.

Dans le JDK 8, HashMap a été modifié de sorte que si les clés peuvent être comparées pour l'ordre, alors tout seau à forte densité de population est implémenté comme un arbre, de sorte que même s'il y a beaucoup d'entrées avec le même code de hachage, la complexité est O(log n). Cela peut poser des problèmes si vous avez un type de clé où l'égalité et l'ordre sont différents, bien sûr.

Et oui, si vous n'avez pas assez de mémoire pour la carte de hachage, vous aurez des problèmes... mais cela sera vrai quelle que soit la structure de données utilisée.

Answer 2

Il a déjà été mentionné que les hashmaps sont O(n/m) en moyenne, si n est le nombre d'articles et m est la taille. Il a également été mentionné qu'en principe, l'ensemble pourrait s'effondrer en une liste singulièrement liée avec O(n) le temps d'interrogation. (Tout ceci suppose que le calcul du hachage est un temps constant).

Cependant, ce qui n'est pas souvent mentionné, c'est qu'avec une probabilité minimale. 1-1/n (donc pour 1000 articles, c'est une chance de 99,9%), le plus grand seau ne sera pas rempli plus de O(logn) ! Cela correspond donc à la complexité moyenne des arbres de recherche binaire (et la constante est bonne, une limite plus serrée est (log n)*(m/n) + O(1) ).

Tout ce qui est requis pour cette limite théorique est que vous utilisiez une fonction de hachage raisonnablement bonne (voir Wikipedia : Hachage universel . Cela peut être aussi simple que a*x>>m ). Et bien sûr, la personne qui vous donne les valeurs à hacher ne sait pas comment vous avez choisi vos constantes aléatoires.

TL;DR : Avec une très forte probabilité, la complexité de l'entrée/sortie d'un hashmap dans le pire des cas est la suivante O(logn) .

Answer 3

Je ne suis pas sûr que le hashcode par défaut soit l'adresse - j'ai lu les sources d'OpenJDK pour la génération de hashcode il y a un moment, et je me souviens que c'était quelque chose d'un peu plus compliqué. Ce n'est pas encore quelque chose qui garantit une bonne distribution, peut-être. Cependant, c'est dans une certaine mesure discutable, car peu de classes que vous utiliseriez comme clés dans un hashmap utilisent le hashcode par défaut - elles fournissent leurs propres implémentations, ce qui devrait être bon.

En plus de cela, ce que vous ne savez peut-être pas (encore une fois, ceci est basé sur la lecture des sources - ce n'est pas garanti), c'est que HashMap remue le hachage avant de l'utiliser, pour mélanger l'entropie de tout le mot dans les bits du bas, ce qui est nécessaire pour tous les hachages, sauf les plus gros. Cela aide à gérer les hachages qui ne le font pas eux-mêmes, bien que je ne puisse pas penser à des cas communs où vous verriez cela.

Enfin, lorsque le tableau est surchargé, il dégénère en un ensemble de listes liées parallèles - les performances deviennent O(n). Plus précisément, le nombre de liens traversés sera en moyenne la moitié du facteur de charge.

Answer 4

Le fonctionnement de HashMap est un facteur dépendant de l'implémentation de hashCode. Pour le scénario idéal, disons la bonne implémentation de hachage qui fournit un code de hachage unique pour chaque objet (pas de collision de hachage), alors le meilleur, le pire et le scénario moyen seraient O(1). Considérons un scénario où une mauvaise implémentation de hashCode renvoie toujours 1 ou un tel hash qui a une collision de hash. Dans ce cas, la complexité temporelle serait de O(n).

Pour ce qui est de la deuxième partie de la question concernant la mémoire, oui, la contrainte de mémoire est prise en charge par la JVM.

Answer 5

Je suis d'accord :

• la complexité générale amortie de O(1)
• une mauvaise hashCode() pourrait entraîner des collisions multiples, ce qui signifie que, dans le pire des cas, tous les objets se retrouvent dans le même seau, ce qui signifie que O( N ) si chaque godet est soutenu par une carte de crédit. List .
• depuis Java 8, HashMap remplace dynamiquement les Nodes (liste chaînée) utilisés dans chaque bucket par des TreeNodes (arbre rouge-noir lorsqu'une liste dépasse 8 éléments), ce qui donne une performance maximale de O( logN ).

Mais, c'est no la vérité complète si l'on veut être précis à 100%. La mise en œuvre de hashCode() et le type de clé Object (immuable/caché ou étant une collection) pourrait également affecter la complexité en temps réel en termes stricts.

Supposons les trois cas suivants :

1. HashMap<Integer, V>
2. HashMap<String, V>
3. HashMap<List<E>, V>

Ont-ils la même complexité ? Eh bien, la complexité amortie de la 1ère est, comme prévu, O(1). Mais, pour le reste, nous devons également calculer hashCode() de l'élément de recherche, ce qui signifie que nous pourrions avoir à traverser des tableaux et des listes dans notre algorithme.

Supposons que la taille de tous les tableaux/listes ci-dessus est de k . Alors, HashMap<String, V> y HashMap<List<E>, V> aura une complexité amortie de O(k) et de même, O( k + logN ) le pire cas dans Java8.

*Notez que l'utilisation d'un String est un cas plus complexe, parce qu'elle est immuable et que Java met en cache le résultat de l'opération hashCode() dans une variable privée hash de sorte qu'il n'est calculé qu'une seule fois.

/** Cache the hash code for the string */
    private int hash; // Default to 0

Mais, ce qui précède a également son propre pire cas, parce que la méthode Java String.hashCode() vérifie si hash == 0 avant de calculer hashCode . Mais bon, il y a des chaînes non vides qui produisent une hashcode de zéro, comme "f5a5a608", cf. aquí Dans ce cas, la mémorisation peut ne pas être utile.