Les tables de hachage peuvent-elles vraiment être O (1)

Question

Il semble être de connaissance commune que les tables de hachage peut atteindre O(1) mais qui n'a jamais fait sens pour moi. Quelqu'un peut-il expliquer cela?

A. La valeur est un entier plus petit que la taille de la table de hachage, de sorte que la valeur est sa propre hash, donc il n'y a pas de table de hachage, mais si il n'y avait, il serait O(1), et d'être inefficace.

B. Vous devez calculer la valeur de hachage, de sorte que la commande est O(n) pour la taille des données à regardé. La recherche peut être O(1) après O(n) de travail, mais qui vient encore de O(n) dans mes yeux.

Et à moins d'avoir un idéal de hachage ou une grande table de hachage, il ya probablement plusieurs articles par seau de sorte qu'il devient une petite recherche linéaire à un certain point, de toute façon.

Je pense que les tables de hachage sont géniaux, mais je n'ai pas l'O(1) désignation, sauf si c'est juste censé être théorique.

La page Wikipedia de l'article pour les tables de hachage systématiquement les références de la constante recherche de temps, et ignore totalement le coût de la fonction de hachage. Est-ce vraiment une bonne idée?

Edit:

Pour résumer ce que j'ai appris:

C'est techniquement vrai, car la fonction de hachage n'est pas nécessaire d'utiliser toutes les informations sur la clé et donc, peuvent être des constantes de temps, et parce qu'un assez grand tableau peut apporter des collisions à proximité de la constante de temps.

Il est vrai, dans la pratique car au fil du temps, il fonctionne aussi longtemps que la fonction de hachage et de la taille de la table sont choisis pour minimiser les collisions, même si cela signifie souvent pas à l'aide d'une constante de temps de la fonction de hash.

Answer 1

Vous avez deux variables ici, m et n, où m est la longueur de l'entrée et n est le nombre d'éléments dans la table de hachage.

Le O(1) recherche de la performance demande de règlement au moins deux hypothèses:

• Vos objets peuvent être de l'égalité par rapport à O(1) fois.
• Il y aura peu de collisions de hachage.

Si vos objets sont de taille variable et un contrôle d'égalité, il faut examiner tous les bits alors les performances deviendra O(m). La fonction de hachage, cependant, ne ont pas à être en O(m) - il peut être O(1). Contrairement à un hachage cryptographique, une fonction de hachage pour une utilisation dans un dictionnaire n'a pas à regarder tous les bits de l'entrée afin de calculer la valeur de hachage. Les implémentations sont libres de regarder seulement un nombre fixe de bits.

Pour suffisamment beaucoup d'éléments, le nombre d'éléments sera plus grande que le nombre possible de hachages et alors vous obtiendrez des collisions causant la hausse de rendement au-dessus de O(1), par exemple O(n) pour une simple liste chaînée de la traversée (ou O(n*m) si les deux hypothèses sont fausses).

Dans la pratique, si l'O(1) demande même si c'est faux, est approximativement vrai pour beaucoup de situations du monde réel, et en particulier les situations où les hypothèses susmentionnées, maintenez-la enfoncée.

Answer 2

Vous devez calculer la valeur de hachage, de sorte que la commande est O(n) pour la taille des données à regardé. La recherche peut être O(1) après O(n) de travail, mais qui vient encore de O(n) dans mes yeux.

Quoi? Pour hacher un seul élément prend à temps constant. Pourquoi serait-il en être autrement? Si vous êtes à l'insertion d' n éléments, alors oui, vous avez pour calculer n de la cendre, et qui prend le temps linéaire... pour rechercher un élément, vous calculer une hachage unique de ce que vous recherchez, puis trouver le seau avec de que. Vous n'avez pas re-calculer les hachages de tout ce qui se trouve déjà dans la table de hachage.

Et à moins d'avoir un idéal de hachage ou une grande table de hachage, il ya probablement plusieurs articles par seau de sorte qu'il devient une petite recherche linéaire à un certain point, de toute façon.

Pas nécessairement. Les compartiments ne sont pas nécessairement des listes ou des tableaux, elles peuvent être de tout type de conteneur, tel qu'un équilibre de MARCHÉ. Cela signifie que O(log n) pire des cas. Mais c'est pourquoi il est important de choisir une bonne fonction de hachage pour éviter de mettre trop d'éléments dans un seau. Comme KennyTM a souligné, sur la moyenne, vous pouvez toujours obtenir de l' O(1) du temps, même si de temps en temps vous avez à creuser par le biais d'un seau.

Le compromis de tables de hachage est bien sûr l'espace de la complexité. Vous êtes commercial de l'espace pour le temps, ce qui semble être le cas habituel dans le calcul de la science.

---

Vous mentionnez à l'aide de cordes comme clés dans l'un de vos autres commentaires. Vous êtes préoccupé par la quantité de temps qu'il faut pour calculer le hash d'une chaîne, car il se compose de plusieurs caractères? Comme quelqu'un l'a souligné encore une fois, vous n'avez pas nécessairement besoin de regarder tous les caractères à calculer la valeur de hachage, même si elle peut produire une meilleure valeur de hachage si vous l'avez fait. Dans ce cas, si il y a une moyenne m caractères dans votre clé, et vous toutes utilisées pour le calcul de hachage, alors je suppose que vous avez raison, que les recherches prendrait O(m). Si m >> n , alors vous pourriez avoir un problème. Vous seriez probablement mieux avec un BST dans ce cas. Ou choisir un moins cher fonction de hachage.

Answer 3

Le hachage est de taille fixe - à la recherche du compartiment de hachage est un coût fixe de l'opération. Cela signifie qu'il est O(1).

Le calcul de la valeur de hachage n'a pas à être particulièrement coûteux - nous ne parlons pas des fonctions de hachage cryptographiques ici. Mais c'est par le par. La fonction de hachage calcul lui-même ne dépend pas du nombre n d'éléments; alors qu'il peut dépendre de la taille des données dans un élément, ce n'est pas ce que n désigne. Ainsi, le calcul de la valeur de hachage ne dépend pas de n , et est également en O(1).