Complexité temporelle de la table de hachage

il est impossible de savoir à l'avance combien de collisions vous obtiendrez avec votre fonction de hachage, ainsi que des choses comme le besoin de redimensionner. Cela peut ajouter un élément d'imprévisibilité à la performance d'une table de hachage, ce qui rend pas vrai O(1). Cependant, pratiquement toutes les implémentations de tables de hachage offrent O(1) sur la vaste, vaste, vaste majorité des inserts. C'est la même chose que l'insertion de tableau - c'est O(1) sauf si vous avez besoin de redimensionner, auquel cas C'est O(n), plus l'incertitude de collision.

en réalité, les collisions de hachage sont très rares et la seule condition dans laquelle vous devez vous soucier de ces détails est quand votre code spécifique a une fenêtre de temps très étroite dans laquelle il doit fonctionner. Pour pratiquement chaque cas d'utilisation, les tables de hachage sont O(1). Plus impressionnant que l'insertion O (1) est O (1) lookup.

pour certaines utilisations des tables de hachage, il est impossible de les créer de la "bonne" taille à l'avance, parce qu'on ne sait pas combien d'éléments devront être tenus simultanément pendant la durée de vie de la table. Si vous voulez garder un accès rapide, vous avez besoin de redimensionner la table de temps en temps comme le nombre d'éléments augmente. Ce redimensionnement prend le temps linéaire par rapport au nombre d'éléments déjà dans la table, et se fait généralement sur une insertion, lorsque le nombre d'éléments de passe d'un seuil.

ces opérations de redimensionnement peuvent être faites rarement assez que le coût amorti de l'insertion est encore constant (en suivant une progression géométrique pour la taille de la table, par exemple en doublant la taille chaque fois qu'elle est redimensionnée). Mais une insertion de temps en temps prend du temps O(n) parce qu'elle déclenche un redimensionnement.

dans la pratique, ce n'est pas un problème à moins que vous construisez dur des applications en temps réel.

insérant une valeur dans une table de hachage prend, sur le cas moyen, O(1) Temps . La fonction de hachage est calculée, l'opposé est choisi à partir de la table de hachage, puis élément est inséré. Dans le pire des cas, tous les éléments auront hashé à la même valeur, ce qui signifie que soit la liste complète doit être traversées ou, dans le cas d'adressage ouvert, toute la table doit être sondée jusqu'à ce qu'une place vide soit trouver. Par conséquent, dans le pire des cas, l'insertion prend du temps

refer: http://www.cs.unc.edu / ~ plaisted / comp550 / Neyer%20paper.pdf (section de table de hachage)