Complexité de la recherche d'une clé ou d'une valeur dans une table de hachage

Question

Je viens de lire une question d'entretien qui demandait la complexité de récupération d'une clé de hachage par rapport à une valeur de hachage. J'ai toujours pensé que les deux étaient identiques, à O(1 + n/k) (où k est le nombre d'emplacements). Qu'est-ce qui m'échappe ?

Answer 1

Récupération d'un hachage clé est O(lk) pour la longueur de la clé, parce qu'il faut la hacher, mais n/k est censé être constant pour une table de hachage donnée. On parle généralement de O(1), car il ne dépend pas de l'état de la table de hachage, mais de l'état de la table de hachage et de l'état de la table. n mais ce n'est pas le cas strictement O(1) sauf si la taille de la clé est fixe.

Mais la recherche d'un hachage valeur nécessiterait de parcourir l'ensemble de la table pour le rechercher, en supposant que vous ne l'ayez pas commandé à l'avance (il est possible de concevoir des tables de hachage prenant en charge les recherches binaires pour O(log(n)), mais c'est peu courant).

Answer 2

Une valeur de hachage est l'emplacement initial de la recherche. Si les données requises ne sont pas stockées à cet index, la clé de hachage est obtenue par itération jusqu'à ce que les données recherchées soient trouvées.