Je suis novice en algorithme. J'ai lu et je suis conscient que big-O de put (clé K, valeur V) dans Hashmap est O (1). Quand je suis allé au cœur de la classe HashMap
for (int binCount = 0; ; ++binCount) {
Comme vous pouvez le voir, lors de l'ajout d'un nouvel élément à hashmap, il itérera max n (tous les éléments de hashmap) avec "For Loop" ci-dessus:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//...
if ((p = tab[i = (n - 1) & hash]) == null)
//...
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// ...
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// ...
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// ...
}
}
...
return null;
}
Maintenant, big-O de For Loop ici est O (n) -> Pourquoi big-O de put (K key, V value ) dans HashMap peut être O (1)? Où est-ce que je comprends mal?
Merci beaucoup.
3 Réponses :
L'idée est qu'un seul bac de la table de hachage a un nombre constant attendu d'éléments. Par conséquent, la boucle que vous avez mentionnée s'exécuterait dans le temps prévu O (1) (en supposant que le hashCode () de vos clés n'est pas terrible).
Plus précisément, pour l'implémentation HashMap , il existe un facteur de charge dont la valeur est de 0,75 par défaut. Cela signifie qu'en moyenne, chaque casier du HashMap doit avoir <= 0,75 éléments (une fois qu'il y a plus d'entrées de facteur de charge * nombre de casiers dans le HashMap , le nombre de cases est doublé pour maintenir cet invariant). Par conséquent, la boucle mentionnée devrait avoir une seule itération en moyenne.
Le HashMap est en fait une collection (soutenue par un tableau) de buckets qui sont soutenus par un arbre rouge-noir (à partir de Java 8). Si vous avez une fonction de hachage très médiocre qui place tous les éléments dans le même bac, les performances se dégraderont en O(log(n))
De Baeldung ,
HashMap a une complexité O (1), ou complexité en temps constant, pour mettre et obtenir les éléments. Bien sûr, de nombreuses collisions pourraient dégrader les performances en complexité temporelle O (log (n)) dans le pire des cas, lorsque tous les éléments atterrissent dans un seul compartiment. Ceci est généralement résolu en fournissant une bonne fonction de hachage avec une distribution uniforme.
À partir de la documentation , < / p>
Cette implémentation fournit des performances en temps constant pour les opérations de base (get et put), en supposant que la fonction de hachage répartit correctement les éléments entre les buckets.
La notation Big-O a à voir avec les performances d'une fonction par rapport au nombre d'éléments sur lesquels elle opère. Le simple fait d'avoir une boucle for ne fait pas soudainement augmenter les performances d'une recherche Hashmap d'un montant fixe pour chaque élément de la Hashmap .
Il existe des modèles dans Big-O notation. Les boucles sur l'ensemble des éléments sont O (n) mais les boucles en général ne signifient pas que la recherche est O (n) . Pour illustrer, je vais utiliser l'exemple (idiot) ci-dessous
Fonction avec O (1) performance
public void add_still_o_one(int x, int y) {
int[2] numbers;
numbers[0] = x;
numbers[1] = y;
int result = 0;
for (int index = 0; index < numbers.length; index++) {
result += numbers[index];
}
return result;
}
Fonction avec des performances O (1) , avec des boucles ajoutées
public void add_o_one(int x, int y) {
return x + y;
}
Alors que je m'attendrais à ce que ce dernier soit un peu moins efficace, il n'y a aucun moyen de modifier sa vitesse d'exécution en choisissant des nombres différents (ou plus). Par conséquent, il s'agit toujours de O(1).
Dans votre Hashmap, le bouclage sur les listes de seaux modifie la vitesse par rapport à l'entrée; mais cela ne le modifie pas d'une quantité constante pour chaque élément. De plus, la plupart des implémentations de hashmap augmentent leur taille de compartiment à mesure que la carte se remplit. Cela signifie que ce que vous voyez n'est pas un cas courant, et est susceptible d'être rarement appelé (à moins que vous n'implémentiez un très mauvais hashcode).
Bien que vous puissiez considérer que "quelque chose de plus grand que O (1) ", il est très difficile de faire fonctionner le code d'une manière incompatible avec O (1 ) à moins que vous ne cassiez spécifiquement l'algorithme (en fournissant des objets qui ont tous la même valeur, par exemple).
pourquoi posez-vous exactement la même question deux fois? Votre premier a déjà été fermé comme doublon