À retenir
- Permet un accès ultra-rapide aux données, peu importe la quantité d'informations stockées.
- Repose sur une fonction de hachage (un calcul mathématique).
- La gestion des collisions est l'élément critique pour maintenir de bonnes performances.
L'adressage dispersé est une méthode qui permet de ranger et de retrouver des informations instantanément grâce à une formule mathématique. Au lieu de chercher un élément un par un dans une liste (comme on lirait un dictionnaire de A à Z), on applique un calcul à la donnée pour obtenir directement son numéro de « case » de rangement. C'est un peu comme si le nom d'un livre vous indiquait directement son numéro d'étagère et sa place exacte dans une bibliothèque sans passer par le catalogue.
Étymologie
Le terme est une traduction française de l'anglais hashing ou scattered addressing. Il combine « adressage » (l'attribution d'un emplacement) et « dispersé », car les données sont réparties de manière apparemment aléatoire dans l'espace mémoire disponible, plutôt que d'être rangées les unes à la suite des autres.
Exemples d'usage
- Les dictionnaires en langage Python ou les objets en JavaScript, qui permettent de trouver une valeur à partir d'une clé très rapidement.
- La gestion des mots de passe : on ne stocke pas le mot de passe, mais le résultat de son adressage dispersé (empreinte) pour vérification.
- L'indexation de fichiers dans un système de stockage pour accélérer l'accès aux documents.
Cas d'usage
Cette technique est omniprésente dans le développement de bases de données, la création de systèmes de cache pour accélérer les sites web, et dans la conception de compilateurs pour gérer les variables d'un programme.
Bonnes pratiques
Le principal défi est d'éviter les « collisions », c'est-à-dire quand deux données différentes obtiennent la même adresse après calcul. Il est essentiel de choisir une fonction de calcul performante et de prévoir une méthode pour gérer ces doublons (comme le chaînage ou l'adressage ouvert) afin de ne pas ralentir le système.
Synonymes
Antonymes
Conseil
Pour bien comprendre ce concept, imaginez que vous triez des dossiers : au lieu de les classer par ordre alphabétique, vous décidez que chaque dossier va dans un tiroir numéroté selon le nombre de lettres de son titre. C'est le principe de base : une règle simple définit la place sans avoir besoin de comparer les dossiers entre eux.
Questions fréquentes
Est-ce que l'adressage dispersé prend plus de place en mémoire ?
Généralement oui, car on réserve souvent plus de cases que nécessaire pour limiter les risques de collisions et garder un accès rapide.
Quelle est la différence avec un index classique ?
Un index nécessite souvent une recherche (même rapide), alors que l'adressage dispersé vise un accès direct via un calcul unique.
Peut-on retrouver la donnée d'origine à partir de son adresse ?
Non, le calcul est généralement à sens unique ; l'adresse sert à trouver où est rangée la donnée, elle ne contient pas la donnée elle-même.