Qu'est-ce qu'un tableau associatif?

Un tableau associatif, appelé aussi une table de hachage ou hachage carte, est semblable à un tableau standard, sauf l'indice de la matrice 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 à l'information d'une manière efficace. Au cœur d'un tableau associatif est un tableau standard qui est indexé par des entiers, comme c'est normalement le cas. Un algorithme spécial appelé une fonction de hachage convertit l'indice de chaîne en un indice entier pour trouver la valeur. Il s'agit d'une conversion uniforme, de sorte que l'indice de nombre entier réel n'a jamais besoin d'être stockée mais à la place est calculée à partir de la chaîne de caractères en fonction des besoins de chaque moment.
 

La terminologie utilisée pour faire référence à un tableau associatif peut être légèrement différent de ce qui est utilisé quand on parle d'un tableau normal. Quel serait normalement appelé un indice - l'emplacement numérique d'un élément dans un tableau - est appelé la clé. Les données associées à la clé est appelé la valeur. Cela signifie que, dans un tableau associatif, une touche est associée à une valeur qui est corrélée à un indice référençant un élément dans une matrice 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'indice d'une valeur numérique basée sur la clé. Il existe plusieurs types de fonctions de hachage, certains sont conçus pour fonctionner sur les touches qui sont des nombres entiers et certains conçus pour fonctionner sur les touches qui sont des chaînes. Dans le cas d'une clé entière, une méthode populaire consiste à diviser la valeur de clé par la taille du tableau et utiliser le reste de la division de, je l'espère, obtenir une valeur d'index unique.
 

La fonction de hachage peut être beaucoup plus complexe pour les touches qui sont des chaînes. Certaines méthodes comprennent l'ajout de la valeur numérique de chaque caractère de la chaîne, puis en divisant par un nombre, ou en utilisant seulement les premiers caractères de la chaîne pour obtenir un numéro unique. Il ya plusieurs façons de tirer un certain nombre d'une chaîne de caractères.
 

Lorsque vous traitez avec une grande quantité de paires clé-valeur dans un tableau associatif, un problème qui peut se poser est appelé collision. Collision se produit quand l'indice entier provenant d'une clé est identique à l'indice de nombre entier d'une autre touche. Ces deux touches puis pointez efficacement à la même index dans le tableau de valeur. Il existe plusieurs solutions à la collision, principalement parce qu'il a une forte probabilité de se produire dans la plupart des applications pratiques.
 

Une solution à la collision est d'avoir chaque indice de valeur réellement être une liste liée de sorte que, lorsque plus d'une clé qui décide de l'emplacement de l'index, l'emplacement peut contenir plus d'une valeur. C'est ce qu'on appelle le chaînage et est un moyen simple de manipulation d'une collision, mais elle peut aussi ralentir le temps nécessaire pour récupérer les informations. Une autre méthode de traiter avec une collision est appelé sondage linéaire. Lorsqu'une collision se produit, linéaire sondage œuvres en se déplaçant dans le tableau de la valeur jusqu'à un indice utilisé est trouvé. Cette solution peut aider à garder les données réparties uniformément dans le tableau associatif, mais elle peut aussi augmenter la quantité de temps nécessaire pour rechercher une valeur.