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

En pratique, c'est O(1), mais il s'agit en fait d'une simplification terrible et mathématiquement insensée. 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 de l'adressage, mais loin de l'infini.

Lorsque l'on dit que l'entrée/sortie d'un hashmap est O(1), on devrait en fait dire que le temps nécessaire à l'entrée/sortie est plus ou moins constant et ne dépend pas du nombre d'éléments du hashmap, dans la mesure où le hashmap peut ê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, il est certain qu'au bout d'un certain temps, le nombre de bits décrivant un élément augmentera également, car il n'y aura plus d'éléments différents pouvant être décrits. Par exemple, si nous avons utilisé un hashmap pour stocker des nombres de 32 bits et que plus tard nous augmentons la taille du problème de sorte que nous aurons plus de 2^32 éléments de bits 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 en réalité O(log N).

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

Enfin, si la recherche d'un élément dans n'importe quelle structure de données était O(1), nous créerions de l'information à partir de rien. Avec une structure de données de n éléments, je peux sélectionner un élément de n façons différentes. Avec cela, je peux coder une information de log(n) bits. Si je peux coder cela en zéro bit (c'est ce que signifie O(1)), alors j'ai créé un algorithme ZIP à compression infinie.