Pourquoi accéder à un élément d'un dictionnaire par la touche O(1) même si la fonction de hachage peut ne pas être O(1)?
je vois comment vous pouvez accéder à votre collection par clé. Cependant, la fonction de hachage lui-même a beaucoup d'opérations derrière les coulisses, n'est-ce pas?
en supposant que vous avez une fonction de hachage agréable qui est très efficace, il peut encore prendre de nombreuses opérations.
peut-on expliquer cela?
8 réponses
le
HashFunclui - même a beaucoup d'opérations dans les coulisses
C'est certainement vrai. Toutefois , 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 pour calculer la fonction de hachage est le même pour une clé dans un tableau avec dix ou dix mille entrées.
C'est pourquoi l'appel de la fonction de hachage est souvent considéré O(1). Cela fonctionne très 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 touches de taille variable avec une limite supérieure pratique.
généralement, cependant, le temps d'accès d'une table de hachage est O(k), où k est la limite supérieure sur la taille de la clé de hachage.
O(1) ne signifie pas instantané. O(1) signifie constante sans égard à la taille des données . La fonction de hachage prend un certain temps, mais ce temps ne varie pas avec la taille de la collection.
cela signifie que peu importe la taille de votre collection peut être, il faudra presque la même quantité de temps pour récupérer l'un de ses membres.
donc, en d'autres mots Dictionnaire avec 5 membres va dire pourrait prendre environ 0,002 ms pour accéder à l'un d'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 de déclarations ou de fonctions réelles exécutées
si un dictionnaire/carte est mis en œuvre comme un HashMap , il a un meilleure complexité de cas de O(1) , car je meilleur cas, il nécessite exactement le calcul du code de hachage de l'élément clé pour la récupération, s'il n'y a pas de collisions de clés.
Un hachage "plan 151960920" peut avoir un pire cas d'exécution de la complexité de O(n) si vous avez beaucoup de clé de collisions ou d'une très mauvaise fonction de hachage, depuis dans ce cas, il se dégrade en scan linéaire de l'ensemble du tableau qui contient les données.
aussi, O(1) ne signifie pas instantanément , cela signifie qu'il a un constante montant. Ainsi, choisir la bonne implémentation pour un dictionnaire peut tout aussi bien dépendre du nombre d'éléments dans la collection, car avoir un coût constant très élevé pour la fonction sera bien pire s'il y a seulement quelques entrées.
C'est pourquoi les dictionnaires/cartes sont appliqués différemment selon les scénarios. Pour Java il y a plusieurs implémentations différentes, C++ utilise des arbres rouges/noirs, etc. Vous les avez choisis en fonction du nombre de données et de leur efficacité d'exécution meilleure/moyenne/pire cas.
théoriquement, il est encore O (n), parce que dans le pire des cas, toutes vos données peuvent finir par avoir le même hachage et être regroupés ensemble, dans ce cas, vous devez passer linéairement par tout cela.
s'il vous Plaît voir le post Quoi "O(1) temps d'accès"?
le nombre d'opérations dans une fonction de hachage n'est pas pertinent tant qu'il prend le même temps (constant) pour chaque élément de la collection. Par exemple, accéder à un élément dans une collection de 2 éléments prend .001 ms, mais aussi l'accès à un élément dans une collection de 2,000,000,000 d'éléments prend .001 ms. Bien que la fonction de hachage peut contenir des centaines de si déclarations et calculs multiples.
à partir de la documentation:
récupérer une valeur en utilisant sa clé est très rapide, proche de O(1), car le système T:.Collection.Générique.La classe Dictionary`2 est implémentée comme une table de hachage.
donc il peut être O(1) mais peut être plus lent. Ici vous pouvez trouver un autre fil concernant la performance hashtable: table de hachage - pourquoi est-il plus rapide que les tableaux?
une fois que l'on tient compte du fait que les dictionnaires de plus en plus gros prennent plus de mémoire, descendent plus loin dans la hiérarchie du cache et finissent par ralentir l'espace de pagination sur le disque, il est difficile d'affirmer que c'est vraiment O(1). Les performances du dictionnaire seront plus lentes au fur et à mesure qu'il s'agrandira, ce qui donnera probablement une complexité de temps O(log N). Ne me croyez pas? Essayez-le pour vous-même avec 1, 100, 1000, 10000 et ainsi de suite sur des éléments de dictionnaire, jusqu'à dire 100 milliards, et mesurer combien de temps cela prend en pratique pour rechercher un élément.
cependant si vous faites l'hypothèse simplificatrice que toute la mémoire dans votre système est de la mémoire d'accès aléatoire, et peut être accédé en temps constant, alors vous pouvez prétendre que le dictionnaire est O(1). Cette hypothèse est courante, même si elle n'est pas vraiment vraie pour n'importe quelle machine avec de l'espace d'échange de disque, et encore assez discutable dans tous les cas étant donné les différents niveaux de cache CPU.