Table haché (Hash Table)
L'une des méthodes, à la fois simples et des plus efficaces pour classés l'information dans un tableau afin de le retrouvé rapidement, consiste à utiliser une clef et une valeur. Elle permettra grâce à sa clef, de retrouver facilement l'information à un endroit hypothétique où l'on devrait la trouvé ! Cette méthode de programmation est connu sous le nom de table haché ou Hash Table en anglais.
La recherche
Ainsi, le but d'utiliser cette méthode, c'est en quelque sorte de ne pas utilisé une recherche dichotomique ! Car, la recherche dichotomique, surnommé recherche binaire, à l'inconvénient de diviser par deux l'espace de recherche récursivement, jusqu'à ce qu'on arrive à son emplacement. De l'autre côté la table haché, elle définit un endroit précise où l'information (la valeur) doit se trouvé, mais il y a parfois un risque de collision (qu'une même position soit occupé par deux clefs).
Pour obtenir un bon algorithme d'entreposage et de recherche d'informations, il faudra donc une méthode de code haché (hash coding en anglais) allant être orienté par deux critères :
- Une fonction de code haché H(K), doit produire le moins de collisions possibles dans une distributions de clefs K valide et occuper un espace d'adresse selon un intervalle de 0 à M-1 dans un tableau.
- Une méthode de traitement des collisions potentiel offrant la possibilité de placer de retrouver intelligemment une clef K parmi toutes celle situé à une position indique dans le tableau.
Il existe plusieurs fonction de table haché, mais aucune n'est universelle et ne répond à tous les contextes. Par contre, en général, lorsqu'on ne sait rien de la distribution des clefs (K), on choisira une fonction H donnant une distribution uniforme des valeurs H(k), avec comme hypothèse que toutes les clefs K soit parfaites.