0
Je reçois la partie Θ (1) est le temps qui sert à calculer la table de hachage, mais je ne comprends pas la partie Θ (α). Selon moi, la complexité temporelle est Θ (n). Supposons que α est la longueur attendue et que la table a m emplacements. Pour s'assurer que la clé ne se trouve pas dans la table, nous devons rechercher chaque slot, et chaque slot a une longueur excepté α, donc le temps total est α fois m, alors c'est Θ (n).Pourquoi un temps de recherche infructueux pour une table de hachage est-il une complexité temporelle Θ (1 + α)?
Quelqu'un pourrait-il me dire quelle partie je n'ai pas bien comprise? Tester si une clé donnée se trouve dans la table de hachage n'a pas besoin de tester tous les emplacements.
Merci! Je pense que je comprends. Ainsi, chaque clé donnée est calculée en fonction de hachage, et obtient un certain nombre qui se dirige vers un certain endroit. De cette façon, il suffit de regarder cette fente. Ai-je raison? – Root
Oui, c'est comme ça que fonctionne une table de hachage. La fonction de hachage mappe la clé à un seul emplacement (ce que vous appelez "emplacement"). Des clés différentes peuvent avoir la même valeur de hachage, c'est-à-dire qu'elles sont mappées sur le même emplacement (ce que l'on appelle une collision). Par conséquent, vous devez comparer toutes les clés dans ce slot avec une clé donnée (pas sa valeur hash!) Pour savoir si elle est réellement là ou non. – Guenther