Un tableau associatif, appelé aussi une table de hachage ou une carte de hachage, est semblable à un tableau standard, sauf l'indice du tableau peut être une chaîne au lieu d'un entier. Dans de nombreuses applications de base de données et à 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 à des informations 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 constante, de sorte que l'indice de nombre entier réelle ne doit jamais être stocké mais est calculée à partir de la chaîne au besoin à chaque fois.
La terminologie utilisée pour désigner un tableau associatif peut être légèrement différent de ce qui est utilisé lorsque l'on parle d'un tableau normal. Ce qui 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ée 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 un ensemble standard de 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 conçu pour fonctionner sur les touches qui sont entiers et certains sont conçus pour travailler 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 de la matrice et utiliser le reste de la division, je l'espère, obtenir une valeur d'indice 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 y a 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 dérivée d'une clé est identique à l'indice de nombre entier d'une autre touche.Ces deux touches puis mettent effectivement à la même index dans le tableau de valeur. Il existe différentes solutions à la collision, principalement parce qu'il a une forte probabilité de se produire dans la plupart des applications pratiques.
Une solution de collision est d'avoir chaque indice de valeur réellement être une liste chaînée de sorte que, lorsque plusieurs décide clés à cet endroit 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 gérer une collision, mais elle peut aussi ralentir le temps qu'il faut 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, les travaux linéaires de sondage en se déplaçant dans le tableau de la valeur jusqu'à ce qu'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.
