Complexité de l'exécution des tables de hachage (insertion, recherche et suppression))
Pourquoi est-ce que je continue à voir différentes complexités d'exécution pour ces fonctions sur une table de hachage?
sur wiki, search et delete sont O (n) (je pensais que le point des tables de hachage était d'avoir une recherche constante donc quel est le point si search est O (n)).
dans certaines notes de cours d'il y a un certain temps, je vois un large éventail de complexités en fonction de certains détails, y compris un avec tous les O(1). Pourquoi utiliser une autre implémentation si je peux obtenir tout O (1)?
si je suis en utilisant des tables de hachage standard dans un langage comme C++ ou Java, qu'est-ce que je peux attendre de la complexité temporelle?
5 réponses
tables de hachageO(1)moyenne amortis complexité de cas, cependant elle souffre de O(n)pire des cas le temps de la complexité. [Et je pense que c'est là que votre confusion est]
les tables de Hash souffrent de O(n) complexité du pire temps pour deux raisons:
- Si trop d'éléments ont été haché dans la même clé: regarder à l'intérieur de cette clé peut prendre
O(n)fuseau. - une fois a table de hachage a passé son balance de charge - il faut ressasser [créer une nouvelle table plus grande, et ré-insérer chaque élément dans la table].
Cependant, il est dit O(1) cas moyen et amorti parce que:
- il est très rare que de nombreux articles soient hachés à la même clé [si vous choisissez une bonne fonction de hachage et que vous n'avez pas un trop grand équilibre de charge.
- l'opération rehash, qui est
O(n), peut tout au plus se passer aprèsn/2ops, qui sont tous supposésO(1): ainsi quand vous additionnez le temps moyen par op, vous obtenez:(n*O(1) + O(n)) / n) = O(1)
Note en raison de la question de reformulation - un temps réel applications et applications qui ont besoin de faible latence - ne devrait pas utiliser une table de hachage comme structure de données.
EDIT: Annother problème avec les tables de hachage: cache
un autre problème où vous pourriez voir une perte de performance dans les grandes tables de hachage est due à la performance de cache. les Tables de hachage souffrent de mauvaises performances de cache, et donc pour une grande collection - le temps d'accès peut prendre plus de temps, puisque vous devez recharger la partie pertinente de la table de la mémoire dans le cache.
idéalement, un hashtable est O(1). Le problème est que si deux clés ne sont pas égales, elles donnent le même hachage.
par exemple, imaginez les chaînes "c'était le meilleur de fois il a été le pire de tous les temps" et "oeufs verts et jambon" les deux abouti à une valeur de hachage 123.
quand la première chaîne est insérée, elle est placée dans le seau 123. Lors de la deuxième chaîne est insérée, il verrait qu'une valeur existe déjà pour seau 123. Il comparerait alors la nouvelle valeur à la valeur existante, et verrait qu'elles ne sont pas égales. Dans ce cas, un tableau ou une liste liée est créé pour cette clé. À ce point, récupérer cette valeur devient O(n) comme le hashtable doit itérer à travers chaque valeur dans ce seau pour trouver la valeur désirée.
pour cette raison, lors de l'utilisation d'une table de hachage, il est important d'utiliser une clé avec une très bonne fonction de hachage qui est à la fois rapide et ne résulte pas souvent en valeurs dupliquées pour les différents objets.
ça a du sens?
Quelques tables de hachage (coucou de hachage) ont garanti O(1) recherche
dépend de la façon dont vous mettez en œuvre le hachage, dans le pire des cas il peut aller à O(n), dans le meilleur des cas il est 0(1) (généralement vous pouvez atteindre si votre DS n'est pas si grand facilement)
peut-être que vous regardiez la complexité de l'espace? Qui est O(n). Les autres difficultés sont comme prévu sur le table de hachage entrée. La complexité de la recherche approche O (1) au fur et à mesure que le nombre de seaux augmente. Si, dans le pire des cas, vous n'avez qu'un seau dans la table de hachage, alors la complexité de la recherche est O(n).
Modifier en réponse au commentaire Je ne pense pas qu'il soit correct de dire que O(1) est le cas moyen. Il l'est vraiment (comme le dit la page wikipedia)) O (1+n / k) où K est la taille de la table de hachage. Si K est assez grand, alors le résultat est effectivement O(1). Mais supposons que K soit de 10 et N de 100. Dans ce cas, chaque seau aura en moyenne 10 entrées, de sorte que le temps de recherche est certainement pas O(1); Il s'agit d'une recherche linéaire à travers jusqu'à 10 entrées.