Exercice 2 - Temps moyen de recherche d'un noeud

On considère une fonction de hachage $h$ qui répartit uniformément les clés dans une table de hachage de taille $m$ dans laquelle les collisions sont résolues par chaînage.

1. Si $n$ clés sont présentes dans la table, quelle est la longueur moyenne d'une liste.
2. Quelle est la durée moyenne d'une recherche infructueuse dans la table ?
3. On part du principe que si $r(x)$ est le rang d'insertion de la clé $x$ dans la table, les $n$ valeurs que peut prendre $r(x)$ sont équiprobables. Déterminer la durée moyenne d'une recherche de $x$.
4. Quelle est la durée moyenne de recherche d'une clé présente dans la table ?
5. Quelle est la durée moyenne moyenne de recherche d'une clé dans une table de hachage de taille $m$ contenant $\mathcal{O}(m)$ clés ?