Table de hachage en C++

Est l'insertion/suppression/recherche de temps de C++ std::map O(log n)? Est-il possible de mettre en œuvre un O(1) table de hachage?

En c++11, il est std::unordered_map, si vous avez boost boost::unordered_map
Vous semblez être d'exploitation en vertu de l'idée fausse que std::map est une table de hachage, mais ils sont généralement des arbres binaires.
Bien sûr, je me rends compte qu'il est mis en œuvre à l'aide d'arbres binaires. Mais n'est-ce pas fonctionner, comme une table de hachage?
Les tables de hachage et des arbres binaires peut être fait pour fournir la même interface (comme map / unordered_map), mais ils fonctionnent complètement différent en interne.
Connexes: "permettent de tables de hachage vraiment être O(1)?".

OriginalL'auteur Paul S. | 2012-10-12

  1. 14

    Est l'insertion/suppression/recherche de temps de C++ carte O(log n)?

    Oui.

    Est-il possible de mettre en œuvre un O(1) table de hachage?

    Certainement. La bibliothèque standard fournit également l'un comme std::unordered_map.

    Je vois. Alors quel est l'avantage de std:map sur std:unordered_map?
    le premier est une collection ordonnée de
    std::map utilise un arbre et les besoins de ses clefs, pour être comparables, tandis que std::unordered_map exige de ses clés hashable. Aussi je ne voudrais pas présumer que std::unordered_map est toujours plus rapide, esp. pour les petits de données (mais ne prenez pas mon mot pour lui et de vérifier si vous pensez que c'est important).
    demande également à ses touches d'être comparables; c'est juste une valeur par défaut différente de référence (equal_to) par rapport à map (less)
    Merci pour les précisions! C# a cette triés nice, la distinction entre "comparables" (avec un peu d'ordre) et "equatable".)

    OriginalL'auteur Kos

  2. 6

    C++ a un unordered_map type. La STL contient également un classes hash_map type, mais ce n'est pas dans la norme C++ de la bibliothèque.

    Maintenant, pour un peu d'algorithmique de la théorie. Il est possible de mettre en œuvre un O(1) table de hachage dans des conditions parfaites, et techniquement, les tables de hachage sont en O(1) d'insertion et de recherche. Les conditions parfaites sont dans ce cas que la fonction de hachage doit être parfait (c'est à dire libre de collision), et vous avez de stockage infini.

    Dans la pratique, nous allons prendre un muet de la table de hachage. Pour toute entrée de clé, il renvoie 1. Dans ce cas, lorsqu'il y a collision (c'est à dire sur la deuxième et les suivantes insertions), il aura à chaîne plus loin pour trouver de l'espace libre. Il peut soit aller vers le prochain emplacement de stockage, ou d'utiliser une liste chaînée pour cela.

    En tout cas, dans le meilleur des cas, oui, les tables de hachage sont en O(1) (jusqu'à ce que vous avez épuisé tous vos valeurs de hachage, bien sûr, puisqu'il est impossible d'avoir une fonction de hachage avec une quantité infinie de sortie). Dans le pire des cas (par exemple, avec ma complètement stupide fonction de hachage), les tables de hachage sont des O(n), puisque vous aurez à traverser sur le stockage dans le but de trouver votre valeur réelle à partir de la donnée de hachage, depuis la valeur initiale n'est pas la valeur correcte.

    hash_map est un non-extension standard expédié par la plupart des compilateurs. La norme de hachage carte est appelée unordered_map
    stackoverflow.com/questions/5908581/is-hash-map-part-of-the-stl
    Oups, désolé. J'ai mis à jour mon post à réfléchir, merci.

    OriginalL'auteur slugonamission

  3. 1

    La mise en œuvre de std::map est un arbre. Ce n'est pas directement spécifié dans la norme, mais aussi quelques bons livres en disant: "It is difficult to imagine that it can be anything else". Cela signifie que l'insertion/suppression/recherche de temps pour que la carte est O(log n).

    Classique des tables de hachage lookup temps O(n/num_slots). Une fois le nombre d'éléments dans le tableau est comparable avec le nombre de machines à sous, vous aurez saturated O(1).

    J'ai une question. Est O(0) == O(1)? Est O(0) définie?
    Je ne pense pas que S(0) est valide notation. O(1) signifie "constante de temps".
    ouais, juste un ralenti de la pensée qui m'est venue en lisant votre réponse. merci!
    O(0) serait probablement implique que l'algorithme a récupéré les résultats pour vous avant votre même demandé ce que tu voulais 😉
    hahaha les débuts du Rapport de Minorité?

    OriginalL'auteur Kirill Kobelev