Pourquoi accéder à un élément d’un dictionnaire par la clé O (1) même si la fonction de hachage ne peut pas être O (1)?

Je vois comment vous pouvez accéder à votre collection par clé. Cependant, la fonction de hachage elle-même a beaucoup d’opérations dans les coulisses, n’est-ce pas?

En supposant que vous ayez une belle fonction de hachage qui est très efficace, cela peut prendre de nombreuses opérations.

Est-ce que cela peut être expliqué?

le HashFunc lui-même a beaucoup d’opérations dans les coulisses

C’est certainement vrai. Cependant, le nombre de ces opérations dépend de la taille de la clé et non de la taille de la table de hachage dans laquelle la clé est insérée: le nombre d’opérations à calculer pour la fonction de hachage est le même pour une clé de table de dix ou avec dix mille entrées.

C’est pourquoi l’appel de la fonction de hachage est souvent considéré comme O (1). Cela fonctionne bien pour les clés de taille fixe (valeurs intégrales et chaînes de longueur fixe). Il fournit également une approximation décente pour les clés de taille variable avec une limite supérieure pratique.

En règle générale, cependant, le temps d’access d’une table de hachage est O (k), où k est la limite supérieure de la taille de la clé de hachage.

O(1) ne signifie pas instantané. O(1) signifie constante sans tenir compte de la taille des données . La fonction de hachage prend un certain temps, mais cette durée ne correspond pas à la taille de la collection.

Cela signifie que quelle que soit la taille de votre collection, cela prendra presque le même temps pour récupérer l’un de ses membres.

Donc, en d’autres termes, Dictionnaire avec 5 membres va dire qu’il faut environ 0,002 ms pour accéder à l’un d’entre eux, ainsi que le dictionnaire de 25 membres devrait prendre quelque chose de similaire. Big O signifie complexité algorithmique par rapport à la taille de la collection au lieu d’instructions ou de fonctions exécutées

Si un dictionnaire / map est implémenté en tant que HashMap , il présente la meilleure complexité en O(1) , car dans le meilleur des cas, il nécessite exactement le calcul du code de hachage de l’élément clé en cas de collision. .

Un hash-map peut avoir la complexité d’exécution la plus défavorable de O(n) si vous avez beaucoup de collisions de clés ou une très mauvaise fonction de hachage, car dans ce cas, il se transforme en un balayage linéaire de l’ensemble du tableau contenant les données. .

De plus, O(1) ne signifie pas instantanément , cela signifie qu’il a une quantité constante . Le choix de la bonne implémentation pour un dictionnaire peut ainsi dépendre du nombre d’éléments de la collection, car avoir un coût constant très élevé pour la fonction sera bien pire s’il n’y a que quelques entrées.

C’est pourquoi les dictionnaires / cartes sont implémentés différemment pour différents scénarios. Pour Java, il existe plusieurs implémentations différentes, C ++ utilise des arborescences rouge / noire, etc. Vous les avez choisies en fonction du nombre de données et de leur efficacité d’exécution optimale / moyenne / pire.

Théoriquement, c’est toujours O (n), car dans le pire des cas, toutes vos données peuvent avoir un hachage identique et être regroupées, auquel cas vous devez les parcourir de manière linéaire.

S’il vous plaît voir le post Que signifie “temps d’access O (1)”?

Le nombre d’opérations dans une fonction de hachage n’est pas pertinent tant qu’il prend la même durée (constante) pour TOUS les éléments de la collection. Par exemple, l’access à un élément dans une collection de 2 éléments prend 0,001 ms, mais l’access à un élément dans une collection de 2 000 000 000 d’éléments nécessite 0,001 ms. Bien que la fonction de hachage puisse contenir des centaines d’instructions if et plusieurs calculs.

des docs:

Récupérer une valeur en utilisant sa clé est très rapide, proche de O (1), car la classe T: System.Collections.Generic.Dictionary`2 est implémentée en tant que table de hachage.

Donc, il peut être O (1) mais pourrait être plus lent. Ici vous pouvez trouver un autre sujet concernant les performances de la table de hachage: Table de hachage – pourquoi est-ce plus rapide que les tableaux?

Une fois que vous avez pris en compte le fait que les dictionnaires de plus en plus volumineux prennent plus de mémoire, descendent la hiérarchie du cache et ralentissent le swap sur le disque, il est difficile d’affirmer qu’il s’agit vraiment de O (1). Les performances du dictionnaire deviendront plus lentes à mesure qu’elles grossiront, ce qui donnera probablement une complexité temporelle à O (log N). Ne me crois pas? Essayez-le vous-même avec des éléments de dictionnaire de 1, 100, 1000, etc., soit 100 milliards, et mesurez le temps nécessaire à la recherche d’un élément.

Cependant, si vous faites l’hypothèse simplificasortingce que toute la mémoire de votre système est une mémoire vive et que vous pouvez y accéder à temps constant, vous pouvez alors affirmer que le dictionnaire est O (1). Cette hypothèse est courante, même si elle n’est pas vraiment vraie pour toute machine avec un espace de swap de disque, et rest assez discutable dans tous les cas, compte tenu des différents niveaux de cache du processeur.