Qu'est-ce qu'un tableau associatif?

Un tableau associatif, également appelé tableau de hachage ou carte de hachage, est similaire à un tableau standard, sauf que l'index du tableau peut être une chaîne au lieu d'un entier.Dans de nombreuses applications de base de données et dans d'autres programmes qui traitent 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.Au cœur d'un tableau associatif se trouve un tableau standard qui est indexé avec des entiers, comme cela serait normalement le cas.Un algorithme spécial appelé une fonction de hachage convertit l'index de chaîne en un index entier pour trouver la valeur.Il s'agit d'une conversion cohérente, donc l'indice entier réel n'a jamais besoin d'être stocké mais est plutôt calculé à partir de la chaîne au besoin à chaque fois.un tableau normal.Ce qui serait normalement appelé un index mdash;l'emplacement numérique d'un élément à l'intérieur d'un tableau mdash;est appelé la clé.Les données associées à la clé sont appelées la valeur.Cela signifie que, dans un tableau associatif, une clé est associée à une valeur, qui est en corrélation avec un indice faisant référence à un élément dans un tableau standard dans la structure de données.

au cœur de chaque tableau associatif est la fonction de hachage.Il s'agit d'un algorithme utilisé pour déterminer l'index numérique d'une valeur basée sur la clé.Il existe plusieurs types de fonctions de hachage, certaines conçues pour fonctionner sur des clés qui sont des entiers et certaines conçues pour fonctionner sur des clés qui sont des cordes.Dans le cas d'une clé entière, une méthode populaire consiste à diviser la valeur clé par la taille du tableau et à utiliser le reste de la division pour, espérons-le, obtenir une valeur d'index unique.

La fonction de hachage peut être beaucoup plus complexepour les clés qui sont des cordes.Certaines méthodes incluent l'ajout de la valeur numérique de chaque caractère dans la chaîne, puis la diviser par un certain nombre, ou en utilisant uniquement les premiers caractères de la chaîne pour obtenir un numéro unique.Il existe de nombreuses façons de dériver un nombre d'une chaîne de caractères.

Lorsque vous traitez une grande quantité de paires de valeurs clés dans un tableau associatif, un problème qui peut survenir est appelé collision.La collision se produit lorsque l'indice entier dérivé d'une clé est identique à l'indice entier d'une autre clé.Ces deux touches pointent alors efficacement le même index dans le tableau de valeur.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 à avoir chaque index de valeur être une liste liée afin que, lorsque plus d'une clé résout à cet indexEmplacement, l'emplacement peut contenir plus d'une valeur.C'est ce qu'on appelle le chaînage et est un moyen simple de gérer une collision, bien qu'il puisse également ralentir le temps nécessaire pour récupérer les informations.Une autre méthode pour gérer une collision est appelée sondage linéaire.Lorsqu'une collision se produit, le sondage linéaire fonctionne en déplaçant le tableau de valeur jusqu'à ce qu'un index inutilisé soit trouvé.Cette solution peut aider à maintenir les données réparties uniformément dans le tableau associatif, mais il peut également augmenter le temps nécessaire pour consulter une valeur.