Je vois comment vous pouvez accéder à votre collection par clé. Cependant, la fonction de hachage elle-même a beaucoup d'opérations en coulisse, n'est-ce pas ?
En supposant que vous disposiez d'une belle fonction de hachage très efficace, de nombreuses opérations peuvent encore être nécessaires.
Peut-on l'expliquer ?
Mais il es Il est possible d'écrire une fonction de hachage qui dépend de la taille de la collection. Ce serait stupide et artificiel, mais vous pouvez le faire. L'affirmation selon laquelle la recherche dans un ensemble de hachage est en fait fondée sur l'hypothèse que le calcul du hachage est O(1), ce qui est pratiquement toujours, mais pas nécessairement, le cas.
@Servy Pas nécessairement aussi stupide et artificiel que ça. Une implémentation de liste personnalisée qui veut permettre à deux listes contenant des éléments égaux de se comparer comme étant elles-mêmes égales peut remplacer GetHashCode() pour combiner les codes de hachage des éléments d'une manière ou d'une autre. Si je devais implémenter une telle classe, pour une implémentation initiale, j'implémenterais GetHashCode() exactement comme ça. Bien sûr, je changerais aussi cela plus tard.
@hvd Ce serait un hachage O(m), où m est la taille des collections internes. Cela ne serait toujours pas lié à la taille de la collection externe (la structure réelle basée sur le hachage). Il faudrait que les éléments de la collection regardent tous les éléments de cette même collection basée sur le hachage dans lesquels ils se trouvent actuellement. pour que ces éléments aient un code de hachage O(n) (ou toute fonction de n). Ce serait plutôt stupide et artificiel.
le site
HashFunca lui-même beaucoup d'opérations en coulisses
C'est certainement vrai. Cependant, le nombre de ces opérations dépend de la taille de l'échantillon. clé et non sur 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 une table de dix ou de 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). Elle fournit également une approximation décente pour les clés de taille variable avec une limite supérieure pratique.
En général, cependant, le temps d'accès d'une table de hachage est O(k), où k est la limite supérieure de la taille de la clé de hachage.
Considérez également qu'il est impossible d'avoir une table de hachage de n éléments distincts, sauf si au moins un élément est représenté par au moins log(n) bits.
Malheureusement, toutes les opérations sont exponentielles si l'on ne limite pas la taille des bits des entrées. Mais ce n'est pas un résultat très intéressant ou utile, n'est-ce pas ?
@Owen : Il n'est pas non plus possible d'avoir plus d'éléments dans une table de hachage en mémoire que ce qui peut être attribué à des clés uniques qui tiennent dans une variable de la taille d'un pointeur.
Cela signifie que, quelle que soit la taille de votre collection, il faudra toujours presque le même temps pour récupérer n'importe lequel de ses membres.
En d'autres termes, un dictionnaire de 5 membres prendra environ 0,002 ms pour accéder à l'un d'entre eux, tout comme un dictionnaire de 25 membres devrait prendre quelque chose de similaire. Big O signifie la complexité algorithmique sur la taille de la collection au lieu des instructions ou fonctions exécutées.
Mais en même temps, si votre fonction de hachage est vraiment mauvaise, vous pouvez vous retrouver avec beaucoup de valeurs dans le seau, donc O(1) ne tiendra plus.
@klappvisor, pas nécessaire que a fonction soit mauvaise. Il se peut que les données d'entrée soient truquées. C'est pourquoi O(1) ici est amorti la complexité, et non la "vraie" complexité.
Cela ne signifie pas que chaque membre prendra le même temps, cela signifie simplement (en gros) que la limite supérieure de ce temps d'accès ne croît pas avec la taille de la collection. Considérez comment une table de hachage gère les collisions de désambiguïsation. De même, la recherche d'un élément pour un arbre de recherche binaire est O(log2 n) parce que le pire cas est log2 avec la taille de N, mais un élément proche de la racine prendra moins de temps qu'un élément de la feuille, par exemple.
Si un dictionnaire/mappage est implémenté en tant que HashMap il a un complexité maximale de O(1) En effet, dans le meilleur des cas, il suffit de calculer le code de hachage de l'élément clé pour le récupérer, s'il n'y a pas de collision de clés.
A carte de hachage peut avoir un complexité d'exécution dans le pire des cas de O(n) si vous avez beaucoup de collisions de clés ou une très mauvaise fonction de hachage, car dans ce cas, elle se dégrade en un balayage linéaire de l'ensemble du tableau qui contient les données.
Aussi, O(1) ne veut pas dire instantanément cela signifie qu'il a un constant montant. Ainsi, le choix de la bonne implémentation pour un dictionnaire peut aussi bien 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/maps sont mis en œuvre différemment selon les scénarios. Pour Java, il existe plusieurs implémentations différentes, le C++ utilise des arbres rouges/noirs, etc. Vous les choisissez en fonction du nombre de données et en fonction de leur efficacité en termes de temps d'exécution dans le meilleur/moyen/pire cas.
Il n'est pas nécessaire que ce soit le cas, par exemple, l'option Java 8 HashMap se rabat sur un arbre équilibré s'il détecte plusieurs collisions.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
39 votes
La notation O consiste à mesurer
the growthde complexité avec différentes entrées. Il ne s'agit pas de savoir combien d'opérations vous avez. Par exemple : avec 1 valeur, vous avezxsecondes, avecnvous devezroughlyx*nsecondes => O (n).xIl pourrait s'agir de plusieurs opérations combinées.33 votes
Les structures de données n'ont pas une complexité de notation O, les opérations sur ces structures en ont une.
3 votes
De quelle opération s'agit-il ?
0 votes
@PatrickHofman Il explique certains faits concernant les complexités O(1) sur le dictionnaire, peut-être que "connexe" est un meilleur mot.
1 votes
Le PO indique clairement que l'accès par clé est l'opération en question.
0 votes
Pour mémoire, il n'y a pas beaucoup d'instructions non plus. Les processeurs Intel ont des instructions matérielles pour faire
SHAde sorte qu'une recherche dans un dictionnaire peut être effectuée en quelques instructions d'assemblage.0 votes
Je pense que cette question n'est pas un doublon, car elle se concentre sur la fonction ffonction hash qui n'est pas const time.
1 votes
"Beaucoup d'opérations" et O(1) sont parfaitement compatibles - O(1) ou temps constant signifie que, lorsque le nombre d'éléments approche l'infini, il existe une constante finie qui limite le temps d'exécution. Cette constante peut être arbitrairement grande - l'utilisation d'une fonction de hachage dont l'exécution est garantie en un an n'empêcherait pas le système d'être O(1).
0 votes
Considérez une consultation de hachage comme une opération unique.
0 votes
Duplicata possible de Les tables de hachage peuvent-elles vraiment être O(1) ?