Complexité d'exécution des tables de hachage (insertion, recherche et suppression)

Question

Pourquoi les complexités d'exécution de ces fonctions sur une table de hachage sont-elles toujours différentes ?

Sur wiki, la recherche et la suppression sont O(n) (je pensais que l'intérêt des tables de hachage était d'avoir une recherche constante, alors quel est l'intérêt si la recherche est O(n)).

Dans des notes de cours datant d'il y a quelque temps, je vois une large gamme de complexités en fonction de certains détails, y compris une avec tous les O(1). Pourquoi utiliser une autre implémentation si je peux obtenir tous les O(1) ?

Si j'utilise des tables de hachage standard dans un langage comme C++ ou Java, quelle est la complexité temporelle à laquelle je peux m'attendre ?

Answer 1

Tables de hachage sont O(1) moyenne et amorti la complexité des cas, mais il souffre de O(n) cas le plus défavorable complexité temporelle. [Et je pense que c'est là que se situe votre confusion]

Les tables de hachage souffrent des problèmes suivants O(n) La plus grande complexité temporelle est due à deux raisons :

1. Si trop d'éléments ont été hachés dans la même clé : la recherche dans cette clé peut prendre O(n) temps.
2. Une fois qu'une table de hachage a passé son équilibrage de la charge - il doit réorganiser [créer un nouveau tableau plus grand et réinsérer chaque élément dans le tableau].

Cependant, on dit qu'il est O(1) moyenne et amortie parce que :

1. Il est très rare que plusieurs éléments soient hachés avec la même clé [si vous avez choisi une bonne fonction de hachage et que vous n'avez pas un équilibre de charge trop important.
2. L'opération de rehash, qui est O(n) ne peut se produire qu'après la fin de l'année. n/2 qui sont toutes supposées O(1) : Ainsi, lorsque vous additionnez le temps moyen par opération, vous obtenez : (n*O(1) + O(n)) / n) = O(1)

Note : en raison de la question du rehashing, une application en temps réel et des applications qui nécessitent une faible consommation d'énergie ne peuvent pas être prises en compte dans le calcul des coûts. latence - ne doivent pas utiliser une table de hachage comme structure de données.

EDITAR: Un autre problème avec les tables de hachage : cache
Les performances des tables de hachage de grande taille peuvent également être affectées par les performances de la mémoire cache. Les tables de hachage souffrent de mauvaises performances en matière de cache et donc pour les grandes collections - le temps d'accès peut être plus long, puisqu'il faut recharger la partie concernée du tableau de la mémoire vers le cache.

Answer 2

Idéalement, une table de hachage est O(1) . Le problème se pose lorsque deux clés ne sont pas égales, mais qu'elles aboutissent au même hachage.

Par exemple, imaginons les chaînes de caractères suivantes "C'était la meilleure des époques, c'était la pire des époques" y "Œufs verts et jambon" ont toutes deux abouti à une valeur de hachage de 123 .

Lorsque la première chaîne est insérée, elle est placée dans le godet 123. Lorsque la deuxième chaîne est insérée, le système constate qu'une valeur existe déjà pour le godet 123 . Il compare alors la nouvelle valeur à la valeur existante et constate qu'elles ne sont pas égales. Dans ce cas, un tableau ou une liste chaînée est créé pour cette clé. À ce stade, la récupération de cette valeur devient O(n) car la table de hachage doit itérer à travers chaque valeur de ce seau pour trouver la valeur souhaitée.

C'est pourquoi, lorsqu'on utilise une table de hachage, il est important d'utiliser une clé avec une très bonne fonction de hachage qui soit à la fois rapide et qui ne produise pas souvent des valeurs en double pour différents objets.

Cela a-t-il un sens ?

Answer 3

Certaines tables de hachage ( hachage de coucou ) ont une consultation garantie en O(1)

Answer 4

Peut-être regardiez-vous la complexité de l'espace ? Celle-ci est O(n). Les autres complexités sont conformes aux attentes de la table de hachage entrée. La complexité de la recherche s'approche de O(1) à mesure que le nombre de godets augmente. Si, dans le pire des cas, la table de hachage ne contient qu'un seul godet, la complexité de la recherche est de O(n).

Modification en réponse au commentaire Je ne pense pas qu'il soit correct de dire que O(1) est le cas moyen. Il s'agit en réalité (comme le dit la page wikipedia) de O(1+n/k) où K est la taille de la table de hachage. Si K est suffisamment grand, le résultat est effectivement O(1). Mais supposons que K soit de 10 et N de 100. Dans ce cas, chaque panier aura en moyenne 10 entrées, de sorte que le temps de recherche n'est certainement pas O(1) ; il s'agit d'une recherche linéaire sur un maximum de 10 entrées.

Answer 5

Cela dépend de la façon dont vous implémentez le hachage, dans le pire des cas cela peut aller jusqu'à O(n), dans le meilleur des cas c'est 0(1) (généralement vous pouvez y arriver si votre DS n'est pas si grand facilement).