Une table de hachage distribuée (ou DHT pour Distributed Hash Table), est une technologie permettant l'identification et l'obtention, dans un système réparti, comme certains réseaux P2P, d'une information. L'ensemble de la table de hachage est constituée virtuellement par tous ces constituants répartis sur tous les éléments du réseau, qui en possèdent chacun une partie.
Les tables de hash réparties sont utilisées notamment dans les protocoles Chord, protocole P2P CAN, Tapestry, Kademlia (utilisé par eMule), Ares Galaxy. Système aussi utilisé dans de nombreux clients récents pour le protocole BitTorrent comme Azureus, Bitcomet ou encore µTorrent (prononcer Micro Torrent). Le premier client BitTorrent à utiliser le DHT était Azureus, suivi du client officiel BitTorrent, c'était deux versions différentes. La version officielle fut alors appelée Mainline DHT. Dorénavant la plupart des clients supportent la version Mainline DHT.
Supposons un grand nombre d'utilisateurs (5 millions) ayant lancé leur logiciel de P2P (Peer-to-Peer) sur leur ordinateur. Chacun partage quelques fichiers (films au format MPEG, images, disques, etc.)
Un utilisateur (Luc) possède par exemple l'album de musique "Les idees saines de Serge Dassault" (disponible sous licence Creative Commons).
Supposons qu'un autre utilisateur (Pierre) souhaite télécharger cet album. Comment son logiciel de P2P peut-il trouver l'ordinateur de Luc ?
Le logiciel de Pierre pourrait éventuellement demander aux 5 millions d'ordinateurs si par hasard ils possèdent cet album. Le logiciel de Luc répondrait alors : "Je le possède et peux commencer à le transférer".
Il serait cependant bien lent de demander aux 5 millions d'ordinateurs si ils ont cet album, car il y aurait en permanence des millions de questions "Je cherche tel album, l'as-tu ?", entraînant des millions de réponses : "Non, désolé !".
Un grand annuaire archivant les noms des fichiers partagés par tous les utilisateurs résoudrait la question : il suffirait de demander à ce "grand annuaire" (= la table de hachage) l'album de musique "Les idees saines de Serge Dassault"pour obtenir la réponse : "il est disponible sur l'ordinateur de Luc (et celui de Mathieu, de Paul, etc.)".
C'est ainsi que fonctionnait la première génération de réseaux P2P. Il y avait un serveur central qui servait de "grand annuaire". Exemples : Napster, Audiogalaxy, Edonkey, Kazaa
Cette solution est de plus en plus abandonnée en raison de sa fragilité. Que faire lorsque le serveur central tombe en panne ? Ou prend feu ? Ou est saisi par la police ? Le réseau ne fonctionne plus, on ne peut plus faire de recherche sur les fichiers partagés.
Les programmeurs de logiciels P2P ont alors eu une idée : Il faudrait que le "grand annuaire" ne soit pas sur un seul ordinateur, mais sur des centaines. Et ils se sont dit, on a qu'a faire notre logiciel de tel façon que chaque utilisateur soit responsable d'un petit bout du grand annuaire. Chacun des 5 millions d'utilisateurs est responsable d'une petite partie: On dit que c'est une table de hachage distribuée.
Par exemple, l'utilisateur Jean-Claude va etre responsable de tous les fichiers qui commencent par A, Toto va être responsable de tous les fichiers qui commencent par B, etc. Lorsque un nouvel utilisateur se connecte au reseau, la première chose que le logiciel va faire, c'est de dire quels fichiers il peut partager. Si il possède un film qui s'appelle par exemple "Bourdieu", il va dire a l'utilisateur Toto (qui est responsable des fichiers qui commencent par B): " j'ai le film "Bourdieu". Si des gens le veulent, c'est chez moi. " Et donc les recherches deviennent très rapides. Si on cherche "Bourdieu" : on va directement demander à la personne responsable de la lettre "B".
La réalité est un peu plus complexe : il ne faut pas qu'une seule personne soit responsable des mots qui commencent par "B", car si elle éteint son ordinateur on perd une partie de l'annuaire. Il faut donc introduire de la redondance dans l'annuaire, et plusieurs ordinateurs sont simultanément responsables des mêmes mots. De plus, il y a des centaines de millions de fichiers partagés, donc le principe de division de l'annuaire n'est pas selon les lettres de l'alphabet, mais selon une table de hachage des mots des titres des fichiers.
Enfin, chaque ordinateur n'a pas besoin de connaitre tous les ordinateurs qui archivent des mots. Il connaitra typiquement une centaine d'ordinateurs. Si l'utilisateur fait une recherche sur "Bourdieu" et ne connait pas l'ordinateur qui archive les fichiers commencant par B,