Principe

Une table de hachage est une structure de données indexée par des valeurs $V = \{1, \ldots, m\}$, comme un tableau. On dit alors que cette table est de taille $m$. Une table de hachage contient des éléments posédant chacun une clé, on note $C = \{1, \ldots, n\}$ l'ensemble des clés. Il existe en règle générale beaucoup plus de clés que d'indices dans une table. On affecte à chaque élément, donc à chaque clé, un (ou plusieurs) indice dans la table. Pour ce faire, on dispose d'une fonction de hachage $h : C \longrightarrow V$, qui à toute clé $c$ associe un indice $h(c)$ permettant de placer (rechercher, ou supprimer) un élément dans la table de hachage.