Compartiments de hachage

En informatique, une table de hachage [tableau de hachage] est une structure de données qui donne un accès quasi direct aux objets grâce à une clé [une chaîne ou un nombre entier unique]. Une table de hachage utilise une fonction de hachage pour calculer un index dans un tableau de compartiments ou d’emplacements, dans lequel on peut trouver la valeur souhaitée. Les principales caractéristiques d’une clé sont les suivantes :

• Il peut s’agir de votre numéro de sécurité sociale, votre numéro de téléphone, votre numéro de compte, etc.
• Elle doit être unique.
• Chaque clé est associée à une valeur.

Les compartiments de hachage sont utilisés pour répartir les éléments de données à des fins de tri ou de recherche. L’objectif de cette répartition est de réduire les listes chaînées afin que la recherche d’un élément spécifique puisse se faire dans un délai plus court. Une table de hachage qui utilise des compartiments est en fait la combinaison d’un tableau et d’une liste chaînée. Chaque élément du tableau [la table de hachage] est un en-tête pour une liste chaînée. Tous les éléments qui se trouvent au même endroit seront stockés dans la liste. La fonction de hachage affecte chaque enregistrement au premier emplacement de l’un des compartiments. Si cet emplacement est occupé, le système va parcourir séquentiellement les autres emplacements du compartiment jusqu’à ce qu’il en trouve un de libre. Si un compartiment est complètement plein, l’enregistrement est stocké dans un compartiment de débordement de capacité infinie situé à la fin de la table. Tous les compartiments utilisent le même compartiment de débordement. Toutefois, une bonne solution consiste à utiliser une fonction de hachage qui distribue équitablement les enregistrements entre les compartiments. De cette façon, le compartiment de débordement contiendra le moins d’enregistrements possible.