Qu'est ce que c'est? A quoi ca sert? avantages (par rapport à quelle méthode)? inconvénients?

une hashtable est une structure de données qui stocke en général des valeurs associées à des strings. la string est la clé qui permet d'accéder à la valeur de la variable correspondante.
 
le + : c'est rapide et simple comme structure, plus simple à mettre en place qu'un arbre binaire, plus rapide pour la recherche qu'une liste chaînée ou un array brute force.
 
le - : c'est une structure qui permet de récupérer une valeur en fonction d'une clé rapidement, ce n'est pas un arbre binaire, donc les valeurs sont insérées n'importe comment et donc pas triées.
 
comment ça marche ? une hashtable est en fait un tableau de listes chaînées. à chaque insertion, une clé est calculée (le plus souvent par un checksum avec des nombres magiques) qui sera utilisée comme index dans le tableau de listes chaînées.
 
disons qu'on insère des structures qui contiennent un nom de variable (fixe) et sa valeur correspondante :
 
struct svariable
{
  char* str;
  int val;
}
 
lors d'une insertion, la hashtable calcule la clé correspondante à str : key. ça peut être une bête somme des caractères cette string. cette valeur est ensuite ramenée à la taille de la hashtable (le nombre de liste chaînées en fait) : key = key % tableSize.
 
ensuite la hashtable parcourt sa liste chaînée myLinkedLists[key] pour trouver une entrée vide. puis, insertion classique dans une liste chaînée.
 
pour récupérer la variable à partir de son nom, même opération : on calcule la clé à partir de la string, puis on parcourt la liste chaînée[key] en faisant sur chaque entrée un strcmp() pour voir si on a la bonne entrée.
 
 
vala. c'est tout simple, rapide, et pratique. à noter que c'est le système qu'utilise php pour ses variables.

L'avantage (unique) de la hash_table face à la map (ou arbre de recherche), c'est que la compexité de la recherche d'un élément de la table n'est dépendante que sur le remplissage de la table (nombre de listes chainées dans le vecteur de listes chaînées qui ont plus d'un élément), plus le temps de calucl de la clé.
Note, un crc de l'objet est souvent une bonne clé de hashage, surtout que l'on veut que la répartition des clés modulo la longueur du vecteur soit la plus uniforme possible.
Une bonne table de hashage doit donc pouvoir se redimensionner lorsqu'elle est trop pleine (par exemple 75% des entrées non vides).
 
 
Un correcteur orthographique utilise souvent les tables de hashage. Les compilos aussi.
 
Le comportement extérieur d'une table de hashage est celui de tout conteneur associatif.

Le desavantage des hashtables : les collisions.
Ex deux string different ont la meme valeur de clef...  
Il faut pas oublier de les gerer c tout