Complexité get / put HashMap

131

Nous avons l'habitude de dire que les HashMap get/putopérations 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 du tas JVM. Sommes-nous sûrs qu'il est assez bon de prétendre que les get/putsont O (1)?

La mémoire disponible est un autre problème. Comme je le comprends des javadocs, le HashMap load factordevrait être 0,75. Que faire si nous n'avons pas assez de mémoire dans JVM et que le load factordépasse la limite?

Donc, il semble que O (1) n'est pas garanti. Est-ce que cela a du sens ou est-ce que je manque quelque chose?

Michael
la source
1
Vous voudrez peut-être rechercher le concept de complexité amortie. Voir par exemple ici: stackoverflow.com/questions/3949217/time-complexity-of-hash-table La pire complexité des cas n'est pas la mesure la plus importante pour une table de hachage
Dr G
3
Correct - il est amorti O (1) - n'oubliez jamais cette première partie et vous n'aurez pas ce genre de questions :)
Ingénieur
Le pire des cas de complexité en temps est O (logN) depuis Java 1.8 si je ne me trompe pas.
Tarun Kolla

Réponses:

216

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, getdevra les parcourir en appelant equalschacun d'eux pour trouver une correspondance.

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

Dans JDK 8, HashMapa été peaufiné de sorte que si les clés peuvent être comparées pour la commande, alors tout seau densément peuplé est implémenté sous forme d'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 ce sera vrai quelle que soit la structure de données que vous utilisez.

Jon Skeet
la source
@marcog: Vous supposez O (n log n) pour une seule recherche ? Cela me semble stupide. Cela dépendra de la complexité des fonctions de hachage et d'égalité, bien sûr, mais cela ne dépendra probablement pas de la taille de la carte.
Jon Skeet du
1
@marcog: Alors, que supposez-vous être O (n log n)? Insertion de n éléments?
Jon Skeet du
1
+1 pour une bonne réponse. Souhaitez-vous s'il vous plaît fournir des liens comme cette entrée wikipedia pour la table de hachage dans votre réponse? De cette façon, le lecteur le plus intéressé pourrait comprendre pourquoi vous avez donné votre réponse.
David Weiser
2
@SleimanJneidi: C'est toujours le cas si la clé n'implémente pas Comparable <T> `- mais je mettrai à jour la réponse quand j'aurai plus de temps.
Jon Skeet
1
@ ip696: Oui, putest "amorti O (1)" - généralement O (1), parfois O (n) - mais rarement assez pour s'équilibrer.
Jon Skeet
9

Je ne suis pas sûr que le hashcode par défaut soit l'adresse - j'ai lu la source OpenJDK pour la génération de hashcode il y a quelque temps, et je me souviens que c'était quelque chose d'un peu plus compliqué. Toujours pas quelque chose qui garantit une bonne distribution, peut-être. Cependant, c'est dans une certaine mesure sans intérêt, car peu de classes que vous utiliseriez comme clés dans une table de hachage 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, cela est basé sur la source de lecture - 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 inférieurs, c'est là où il est nécessaire pour tous sauf les hashmaps les plus énormes. Cela aide à gérer les hachages qui ne le font pas eux-mêmes, bien que je ne puisse penser à aucun cas courant où vous verriez cela.

Enfin, ce qui se passe lorsque la table est surchargée, c'est qu'elle dégénère en un ensemble de listes chaîné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.

Tom Anderson
la source
6
Bon sang. Je choisis de croire que si je n'avais pas eu à taper ceci sur un écran tactile de téléphone mobile, j'aurais pu battre Jon Sheet au coup de poing. Il y a un badge pour ça, non?
Tom Anderson
8

L'opération HashMap dépend du 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 serait O (1). Considérons un scénario où une mauvaise implémentation de hashCode retourne toujours 1 ou tel hachage qui a une collision de hachage. Dans ce cas, la complexité temporelle serait O (n).

Venant maintenant à la deuxième partie de la question sur la mémoire, alors oui la contrainte de mémoire serait prise en charge par JVM.

Pranav
la source
8

Il a déjà été mentionné que les hashmaps sont O(n/m)en moyenne, si nc'est le nombre d'éléments et mla taille. Il a également été mentionné qu'en principe, le tout pourrait se réduire en une seule liste liée avec O(n)le temps de requête. (Tout cela suppose que le calcul du hachage est un temps constant).

Cependant, ce qui n'est pas souvent mentionné, c'est qu'avec une probabilité au moins 1-1/n(donc pour 1000 articles, c'est 99,9% de chances), le plus grand seau ne sera pas rempli plus que O(logn)! Correspondant ainsi à la complexité moyenne des arbres de recherche binaires. (Et la constante est bonne, une borne plus serrée l'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: Universal Hashing . Cela peut être aussi simple que a*x>>m). Et bien sûr, la personne qui vous donne les valeurs de hachage ne sait pas comment vous avez choisi vos constantes aléatoires.

TL; DR: Avec une probabilité très élevée, le pire des cas de complexité get / put d'une hashmap est O(logn).

Thomas Ahle
la source
(Et notez que rien de tout cela ne suppose des données aléatoires. La probabilité résulte uniquement du choix de la fonction de hachage)
Thomas Ahle
J'ai également la même question concernant la complexité d'exécution d'une recherche dans une carte de hachage. Il semblerait que ce soit O (n) car les facteurs constants sont censés être supprimés. Le 1 / m est un facteur constant et est donc abandonné en laissant O (n).
nickdu
4

Je suis d'accord avec:

  • la complexité amortie générale de O (1)
  • une mauvaise hashCode()implémentation peut entraîner plusieurs collisions, ce qui signifie que dans le pire des cas, chaque objet va dans le même compartiment, donc O ( N ) si chaque compartiment est sauvegardé par un List.
  • depuis Java 8, HashMapremplace dynamiquement les nœuds (liste chaînée) utilisés dans chaque bucket par TreeNodes (arbre rouge-noir lorsqu'une liste dépasse 8 éléments) résultant en une pire performance de O ( logN ).

Mais ce n'est PAS la vérité si nous voulons être précis à 100%. L'implémentation hashCode()et le type de clé Object(immuable / mis en cache ou étant une collection) peuvent également affecter la complexité réelle 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 du premier est, comme prévu, O (1). Mais, pour le reste, nous devons également calculer hashCode()l'élément de recherche, ce qui signifie que nous pourrions devoir parcourir des tableaux et des listes dans notre algorithme.

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

* Notez que l'utilisation d'une Stringclé est un cas plus complexe, car elle est immuable et Java met en cache le résultat de hashCode()dans une variable privée hash, donc elle n'est calculée 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 pire cas, car l' String.hashCode()implémentation de Java vérifie si hash == 0avant de calculer hashCode. Mais bon, il y a des chaînes non vides qui produisent un hashcodezéro, comme "f5a5a608", voir ici , auquel cas la mémorisation peut ne pas être utile.

Kostas Chalkias
la source
2

En pratique, c'est O (1), mais c'est en fait une simplification terrible et mathématiquement absurde. La notation O () indique comment l'algorithme se comporte lorsque la taille du problème tend vers l'infini. Hashmap get / put fonctionne comme un algorithme O (1) pour une taille limitée. La limite est assez grande du point de vue de la mémoire de l'ordinateur et du point de vue de l'adressage, mais loin de l'infini.

Quand on dit que hashmap get / put est O (1) il faut vraiment dire que le temps nécessaire pour le get / put est plus ou moins constant et ne dépend pas du nombre d'éléments dans le hashmap pour autant que le hashmap puisse l'être présenté sur le système informatique actuel. Si le problème dépasse cette taille et que nous avons besoin de hashmaps plus grands, alors, après un certain temps, le nombre de bits décrivant un élément augmentera également à mesure que nous manquerons des différents éléments pouvant être décrits. Par exemple, si nous avons utilisé un hashmap pour stocker des nombres 32 bits et que plus tard nous augmentons la taille du problème afin d'avoir plus de 2 ^ 32 bits éléments dans le hashmap, alors les éléments individuels seront décrits avec plus de 32 bits.

Le nombre de bits nécessaires pour décrire les éléments individuels est log (N), où N est le nombre maximum d'éléments, donc get et put sont vraiment O (log N).

Si vous le comparez à un ensemble d'arbres, qui est O (log n), alors l'ensemble de hachage est O (long (max (n)) et nous sentons simplement que c'est O (1), car sur une certaine implémentation max (n) est fixe, ne change pas (la taille des objets que nous stockons mesurée en bits) et l'algorithme de calcul du hash code est rapide.

Enfin, si trouver un élément dans une structure de données était O (1), nous créerions des informations à partir de rien. Ayant une structure de données de n élément, je peux sélectionner un élément de n manière différente. Avec cela, je peux encoder les informations de log (n) bit. Si je peux encoder cela en zéro bit (c'est ce que signifie O (1)), alors j'ai créé un algorithme ZIP à compression infinie.

Peter Verhas
la source
La complexité de l'ensemble d'arbres ne devrait-elle pas être O(log(n) * log(max(n)))alors? Bien que la comparaison à chaque nœud puisse être plus intelligente, dans le pire des cas, elle doit inspecter tous les O(log(max(n))bits, non?
maaartinus