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.
