Qu'est-ce qu'un tableau associatif?
Un tableau associatif, également appelé table de hachage ou table de hachage, est similaire à un tableau standard, à la différence que son index peut être une chaîne au lieu d'un entier. Dans de nombreuses applications de base de données et dans d'autres programmes traitant de grandes quantités de données, un tableau associatif est un élément essentiel pour aider à trier et à accéder aux informations de manière efficace. Le noyau d'un tableau associatif est un tableau standard indexé avec des entiers, comme ce serait normalement le cas. Un algorithme spécial appelé fonction de hachage convertit l'index de chaîne en un index entier pour rechercher la valeur. Il s'agit d'une conversion cohérente. Par conséquent, l'index entier réel n'a jamais besoin d'être stocké mais est calculé à partir de la chaîne, selon les besoins, à chaque fois.
La terminologie utilisée pour faire référence à un tableau associatif peut être légèrement différente de celle utilisée pour parler d'un tableau normal. Ce qu'on appelle normalement un index - l'emplacement numérique d'un élément dans un tableau - est appelé la clé. La donnée associée à la clé s'appelle la valeur. Cela signifie que, dans un tableau associatif, une clé est associée à une valeur, ce qui correspond à un index référençant un élément d'un tableau standard de la structure de données.
La fonction de hachage est au cœur de chaque tableau associatif. Ceci est un algorithme utilisé pour déterminer l'indice numérique d'une valeur en fonction de la clé. Il existe plusieurs types de fonctions de hachage, certaines conçues pour fonctionner sur des clés qui sont des entiers et d'autres conçues pour fonctionner sur des clés qui sont des chaînes. Dans le cas d'une clé entière, une méthode répandue consiste à diviser la valeur de la clé par la taille du tableau et à utiliser le reste de la division pour obtenir, espérons-le, une valeur d'index unique.
La fonction de hachage peut être beaucoup plus complexe pour les clés qui sont des chaînes. Certaines méthodes incluent l’ajout de la valeur numérique de chaque caractère de la chaîne, puis sa division par un nombre ou l’utilisation des quelques premiers caractères de la chaîne pour obtenir un nombre unique. Il existe de nombreuses façons de dériver un nombre à partir d'une chaîne de caractères.
Lorsque l'on traite un grand nombre de paires clé-valeur dans un tableau associatif, un problème pouvant survenir est appelé collision. La collision survient lorsque l'index entier dérivé d'une clé est identique à l'index entier d'une autre clé. Ces deux clés pointent alors effectivement vers le même index dans le tableau de valeurs. Il existe différentes solutions à la collision, principalement parce qu’elle a une forte probabilité de se produire dans la plupart des applications pratiques.
Une solution à la collision consiste à faire en sorte que chaque index de valeur soit en fait une liste chaînée de sorte que, lorsque plusieurs clés résolvent cet emplacement d'index, celui-ci puisse contenir plusieurs valeurs. C'est ce qu'on appelle le chaînage. Il s'agit d'un moyen simple de gérer une collision, même s'il peut également ralentir le temps nécessaire pour récupérer les informations. Une autre méthode pour traiter une collision est appelée sondage linéaire. En cas de collision, la détection linéaire fonctionne en parcourant le tableau de valeurs jusqu'à ce qu'un index inutilisé soit trouvé. Cette solution peut aider à maintenir les données uniformément réparties dans le tableau associatif, mais elle peut également augmenter le temps requis pour rechercher une valeur.