Tables de hachage (Hash Tables)

1. Le chaînage utilise des listes pour stocker plusieurs éléments dans la même case.
2. L'adressage ouvert stocke tous les éléments directement dans le tableau en cherchant une case vide lors d'une collision.

💡 À retenir : Le chaînage est plus robuste aux collisions, l'adressage ouvert économise la mémoire (pas de pointeurs).

1. Il faut d'abord convertir la chaîne en un nombre (ex: somme des codes ASCII des caractères).
2. Appliquer ensuite la fonction de hachage modulo la taille de la table.

💡 À retenir : La fonction de conversion doit être efficace pour éviter trop de collisions dès le départ.

1. La liste chaînée a une complexité de recherche $O(n)$.
2. La table de hachage permet une recherche en $O(1)$ en moyenne.

💡 À retenir : Le gain de vitesse est énorme pour les grands volumes de données.

1. On calcule le facteur de charge $\alpha = \frac{n}{m}$.
2. Si $\alpha$ approche 1, la table est saturée.

💡 À retenir : En adressage ouvert, il faut redimensionner la table avant que $\alpha$ ne dépasse 0.7.

Non, c'est impossible car l'espace des clés est souvent plus grand que la taille de la table.

💡 À retenir : Une bonne fonction doit être "uniforme" pour minimiser les collisions.

Parce que les collisions successives remplissent des cases adjacentes, créant des blocs de données qui ralentissent la recherche.

💡 À retenir : Le sondage quadratique réduit ce phénomène.

Oui, mais on ne peut pas laisser la case vide (sinon on casse la chaîne de recherche). On utilise un marqueur "DELETED".

💡 À retenir : Le marqueur permet de continuer la recherche sans arrêter le processus.

$O(n)$, si tous les éléments sont hachés vers la même case (collision totale).

💡 À retenir : Le choix d'une bonne fonction de hachage est crucial pour éviter ce cas.

Oui, c'est recommandé pour réduire les collisions, surtout avec la méthode de division.

💡 À retenir : Cela permet une meilleure distribution des clés.

Elle doit être proportionnelle au nombre d'éléments attendus pour maintenir $\alpha$ autour de 0.5 - 0.7.

💡 À retenir : Trop grande = gaspillage, trop petite = collisions.

Non, les tables de hachage ne maintiennent pas l'ordre des éléments.

💡 À retenir : Utilisez un arbre de recherche binaire si l'ordre est nécessaire.

Elle doit être déterministe (même clé = même index), mais peut utiliser une graine (seed) pour la sécurité.

💡 À retenir : La reproductibilité est obligatoire pour retrouver les données.