Pourquoi l'accès à un élément d'un dictionnaire par la touche O(1) même si la fonction de hachage peut ne pas être en 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 bonne fonction de hachage qui est très efficace, il peut prendre de nombreuses opérations.

Cela peut-il être expliqué?

  • O la notation est sur la mesure de la the growth de la complexité avec des entrées différentes. Ce n'est pas le nombre d'opérations que vous avez. Par exemple: avec 1 de la valeur, vous avez x secondes, avec n valeurs, vous devez roughly x*n secondes => O (n). x pourrait être de nombreuses opérations combinées.
  • Structures de données n'ont pas O la notation de la complexité, des opérations sur eux.
  • Donc, l'opération nous en parler?
  • Il explique certains faits au sujet de O(1) complexités sur dictionnaire, peut-être liée à un meilleur mot.
  • OP clairement dit que l'accès par clé est que l'opération en question.
  • Pour l'enregistrement, il n'est pas que de nombreuses instructions, soit. Les processeurs Intel ont le matériel des instructions pour le faire SHA hachages, donc une recherche dans le dictionnaire pourrait être fait en seulement quelques instructions de montage.
  • Je pense que cette question n'est pas un doublon, car il se concentre sur le hachage ffunction pas être const temps.
  • "beaucoup d'opérations" et O(1) sont parfaitement compatibles - O(1) ou à temps constant signifie que, comme le nombre d'éléments de l'approche de l'infini, il existe une certaine constante qui délimite le temps d'exécution. Cette constante peut être arbitraire grande à l'aide d'une fonction de hachage qui est garantie dans un délai d'un an ne serait pas empêcher le système de O(1).
  • Pensez à un hachage de recherche en une seule opération.
  • Double Possible de Pouvez les tables de hachage vraiment être O(1)?

InformationsquelleAutor monogate | 2016-05-20
  1. 113

    la HashFunc lui-même a beaucoup d'opérations derrière les coulisses

    Qui est certainement vrai. Cependant, le nombre de ces opérations dépend de la taille de la clé, non pas sur la taille de la table de hachage dans lequel 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 dix mille entrées.

    C'est pourquoi l'appel de la fonction de hachage est souvent considéré comme O(1). Cela fonctionne très bien pour de taille fixe touches (partie intégrante des valeurs et des chaînes de longueur fixe). Il fournit également un décent approximation pour la variable de la taille des touches avec une limite supérieure pratique.

    En règle générale, 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 aussi qu'il est impossible d'avoir une table de hachage de n articles distincts, sauf si au moins un élément est représenté par au moins log(n) bits.
    • Malheureusement, toutes les opérations sont exponentielle si vous ne bloquez pas les entrées' taille en bits. Mais ce n'est pas très intéressant, ou un résultat utile, à droite?
    • Il n'est pas possible d'avoir plus d'éléments dans en mémoire une table de hachage peut être unique assigné les touches qui s'inscrivent dans un pointeur de taille variable.
    • the number of these operations depends on the size of the key et sur la taille des données cryptées.
    • k n'a pas besoin d'être une limite supérieure. La recherche du temps est linéaire dans la taille de la clé, donc c'est en effet O(k) où k est la taille de la clé. Si k est comprise comme une limite supérieure alors il est réellement O(1).
    InformationsquelleAutor dasblinkenlight
  2. 131

    O(1) ne veut pas dire instantanée. O(1) signifie que la constante sans égard à la taille des données. La fonction de hachage prend une certaine quantité de temps, mais ce temps n'évolue pas avec la taille de la collection.

    • Mais 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. La déclaration que la recherche d'un hashset est en fait fondé sur l'hypothèse que le calcul de la valeur de hachage est O(1), ce qui est pratiquement toujours, mais pas nécessairement le cas.
    • Même pas forcément stupide et artificiel. Une liste personnalisée de mise en œuvre qui veut permettre aux deux listes qui détiennent l'égalité des articles à comparer tels que l'égalité se peut que vous perdiez GetHashCode() de combiner les codes de hachage des éléments d'une certaine façon. Si je devais mettre en place une telle classe, pour une mise en œuvre initiale, je voudrais mettre en œuvre GetHashCode() exactement comme ça. Je voudrais bien sûr la modifier par la suite.
    • Que serait un O(m) de hachage, où m est la taille de l'intérieur de la collections. Il n'est pas lié à la taille de l'extérieur de la collection (le hachage en fonction de la structure). Vous aurez besoin d'avoir les éléments de la collection à la recherche à tous les articles de la même collection en fonction de hachage qu'ils sont actuellement en de ces éléments pour avoir un O(n) (ou toute fonction de n) pour leur code de hachage. serait assez stupide et artificiel.
    • Oh, c'est ce que vous avez voulu dire. Ouais, ce serait stupide. 🙂 Je ne peux pas venir avec à distance scénario plausible, où vous pourriez voulez que.
    • L'idée générale de hachage est d'éviter de O(n) temps de recherche, et donc la création d'une fonction de hachage qui est O(n) serait totalement à l'encontre du but. Vous pourriez le faire, mais ce serait comme la mise en œuvre de plus de manière récursive avec Peano numéros: possible, mais pas vraiment pratique.
    • sûr, mais si vous avez raison que c'est une mauvaise idée, il est possible, de sorte que vous devez penser lorsque vous ne contrôlez pas le hachage.
    • Pour autant que je suis concerné, ce serait comme considérer la possibilité que le tableau d'indexation est O(n). Il pourrait se produire si les tableaux sont mis en œuvre que les listes liées, mais je ne vais pas à vous inquiéter à ce sujet.
    • mais c'est pas possible pour un tableau à O(N), et il est possible pour un GetHashCode avoir n'importe quelle complexité, il est juste préférable O(1).
    • ne pas recevoir la table de hachage en tant que paramètre, alors comment peut-il être dépend de la taille de la table?
    • c'est rare, mais pas rare, pour un objet à disposer d'une référence à son conteneur. Vous pouvez simplement explicitement de le transmettre si vous le vouliez, mais il pourrait également venir à travers les couches d'indirection.
    • N'oubliez pas que pour un hachage à une clé valide pour un dictionnaire, il doit être stable, c'est à dire pas de changement après que l'objet a été ajouté au dictionnaire. Donc, il ne fonctionne que par hachage sur certaines partie immuable de l'objet. Sinon, vous allez rompre le contrat de plus de dictionnaire des implémentations. Rappelez-vous aussi que, au moins pour Java le contrat est if a.equals(b) then hash(a)==hash(b). Avoir la collection dans le cadre de la fonction de hachage sera la cause de l'ensemble du dictionnaire d'arrêter de travailler, si cela provoque le hachage de changer si la collecte des changements.

    InformationsquelleAutor Paarth
  3. 15

    Cela signifie que quelle que soit la taille de votre collection peut être, il faudra encore 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 disons petit plus ponctuellement prendre environ 0.002 ms pour accéder à l'un d'entre eux, ainsi que le dictionnaire de 25 membres devraient prendre quelque chose de similaire. Big O signifie que la complexité algorithmique plus de la taille de la collection au lieu de réelle des déclarations ou des fonctions exécutées

    • Mais en même temps, si votre fonction de hachage est vraiment mauvais, vous pouvez vous retrouver avec beaucoup de valeurs dans le seau, donc O(1) ne tient plus
    • pas nécessaire que a la fonction est mauvais. Il se peut que les données d'entrée est conçu. C'est pourquoi O(1) est ici amortis de la complexité, non pas le "vrai" complexité.
    • Il ne signifie pas que chaque membre prendra le même laps de temps, il vient de (à peu près) signifie que la limite supérieure sur que le temps d'accès n'augmente pas avec la taille de la collection. Examiner comment une table de hachage poignées disambiguating collisions. De même, à la recherche d'un élément pour un binaire un arbre de recherche est en O(log2 n), car le pire des cas est log2 avec la taille de N, mais un élément proche de la racine prendra moins de temps qu'un élément feuille, par exemple.
    • Ce n'est pas réellement ce que le "amorti" clarification de l'O(1) signifie. Le fait que c'est un ammortized O(1) pour tenir compte du fait qu'environ 1/N des ajouts (si vous ajoutez à l'ensemble) il sera nécessaire de réaffecter une nouvelle sauvegarde de tableau, qui est un O(N) opérations, de sorte que vous pouvez effectuer N additions en O(N) fois, pour un amorti O(1) en outre, alors qu'un seul ajout est fait également en O(N) (lorsqu'il n'est pas amorti). Il est séparé de la clarification de la complexité asymptotique qu'il assume les hachages sont suffisamment bien réparties.
    InformationsquelleAutor Vidas Vasiliauskas
  4. 12

    Si un dictionnaire/map est mis en œuvre comme un HashMap, il a un meilleur des cas, la complexité de O(1), depuis que j'ai le meilleur des cas, elle nécessite exactement le calcul du hash-code de l'élément clé de la récupération, si il n'y a pas de clé de collisions.

    Un de hachage carte 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, puisque dans ce cas, il se dégrade à une analyse linéaire de l'ensemble de la matrice qui contient les données.

    Aussi, O(1) ne veut pas dire instantanément, cela signifie qu'il a un constante montant. Afin de choisir la bonne mise en œuvre pour un dictionnaire peut ainsi dépendre du nombre d'éléments dans la collection, puisque le fait d'avoir une très haute constante des coûts de la fonction sera bien pire si il y a seulement quelques entrées.

    C'est pourquoi dictionaryies/maps sont mis en œuvre différemment pour les différents scénarios. Pour Java, il existe plusieurs implémentations différentes, C++ utilise le rouge/noir-arbres, etc. Vous avez choisi en fonction du nombre de données et en fonction de leur meilleur/moyenne/pire cas d'exécution-efficacité.

    • Il n'a pas à être de cette façon, par exemple, Java 8 est HashMap stations à l'équilibre de l'arbre dans le cas où il détecte plusieurs collisions.
    • peut-être vrai, mais alors c'est le classique de hachage carte plus. Il existe de nombreuses implémentations différentes pour les cartes/dictionnaires, de la fourrure exactement ce cas. J'ai modifié la réponse à signaler.
    InformationsquelleAutor Martin C.
  5. 6

    Théoriquement, il est toujours en O(n), car dans le pire des cas, toutes vos données sont peut-être identiques hachage et être regroupés dans ce cas vous aurez à linéairement aller à travers tout cela.

    InformationsquelleAutor twihoX
  6. 3

    Veuillez voir le post de Ce n' "O(1) temps d'accès" signifie?

    Le nombre d'opérations dans une fonction de hachage est sans importance tant qu'il prend le même (constant) montant de temps 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 d'accéder à un élément dans une collection de 2,000,000,000 éléments prend .001 mme. Bien que la fonction de hachage peut contenir plusieurs centaines de si les déclarations et plusieurs calculs.

    • Quantité constante de temps, pas linéaire.
    • Ne serait pas une fonction de hachage doivent contenir plus "si les déclarations et plusieurs calculs" pour produire une assez longue valeur de hachage pour identifier de manière unique de 2 milliards d'éléments qu'il serait pour 200?
    InformationsquelleAutor Ezra
  7. 1

    de la documentation:

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

    De sorte qu'il peut être O(1) mais peut être plus long.
    Ici vous pouvez trouver un autre thread concernant la table de hachage de la performance: Table de hachage - pourquoi est-il plus rapide que les tableaux?

    InformationsquelleAutor JeReT
  8. 1

    Une fois que vous laissez pour le fait que de plus en plus grands dictionnaires de prendre plus de mémoire, d'aller plus loin en bas de la hiérarchie du cache et éventuellement hors de ralentir l'espace de swap sur le disque, il est difficile de prétendre que c'est vraiment O(1). La performance du dictionnaire obtiendrez plus lent qu'il est plus grand, probablement donner O(log N) le temps de la complexité. Ne me croyez pas? Essayez vous-même avec 1, 100, 1000, 10000, et ainsi de suite dictionnaire des éléments, jusqu'à-dire 100 milliards de dollars, et de mesurer combien de temps il prend, dans la pratique, pour rechercher un élément.

    Toutefois, si vous faire l'hypothèse simplificatrice que la mémoire de votre système est une mémoire à accès aléatoire, et peut être consulté en temps constant, il peut demander que le dictionnaire est O(1). Cette hypothèse est fréquente, même si elle n'est pas vraiment vrai pour n'importe quelle machine avec le disque de l'espace de swap, et encore assez discutable, en tout cas, étant donné les différents niveaux de cache du PROCESSEUR.

    • Vous avez un point, mais lorsque nous parlons de la complexité algorithmique, il est logique de supposer matériel parfait. Le point est de définir les caractéristiques d'un algorithme, pas différent de la vie réelle les implémentations matérielles. D'ailleurs, si vous avez de grandes suffisamment de données, la complexité de l'algorithme est vraiment ce qui compte le plus: est-il par exemple O(1), (logN), O(n) ou O(n^2).
    • Il y a aussi la question de la clé de hachage collision avec une plus grande taille des dictionnaires. Une fois que vous obtenez assez grand la plupart des nouvelles entrées seront en collision avec une entrée existante, causant une recherche linéaire dans chaque compartiment de hachage et finissant en O(n). Sauf si vous prenez les clés de hachage s'allonger à mesure que la taille augmente... mais vous n'avez pas de O(1). Je suis d'accord que, dans la pratique, vous pouvez le traiter comme de la constante de temps, mais je préfère rester à l'écart de la forme O-notation pour quelque chose qui n'est qu'une approximation pour assez petites tailles, pas une preuve formelle de toute taille.
    InformationsquelleAutor Ed Avis