Hachage

Le hachage est super efficace. Il faut un temps O(1) pour rechercher, insérer et supprimer un élément à l'aide du hachage. Un élément peut être trouvé en un temps O(log n) dans un arbre de recherche bien équilibré. Existe-t-il un moyen plus efficace de rechercher un élément dans un conteneur ? Ce chapitre présente une technique appelée hachage. Vous pouvez utiliser le hachage pour implémenter une carte ou un ensemble pour rechercher, insérer et supprimer un élément en un temps O(1).

Qu’est-ce que le hachage ?

Le hachage utilise une fonction de hachage pour mapper une clé à un index. Avant d'introduire le hachage, passons en revue la map, qui est une structure de données implémentée à l'aide du hachage. Rappelons qu'une map (introduite dans la section) est un objet conteneur qui stocke les entrées. Chaque entrée contient deux parties : une clé et une valeur. La clé, également appelée clé de recherche, permet de rechercher la valeur correspondante. Par exemple, un dictionnaire peut être stocké dans une carte, dans laquelle les mots sont les clés et les définitions des mots sont les valeurs.

Une carte est également appelée un dictionnaire, une table de hachage ou un tableau associatif.

Le Java Collections Framework définit l'interface java.util.Map pour la modélisation de cartes. Trois implémentations concrètes sont java.util.HashMap, java.util.LinkedHashMap et java.util.TreeMap. java.util.HashMap est implémenté à l'aide du hachage, java.util.LinkedHashMap à l'aide de LinkedList et java.util.TreeMap à l'aide du rouge -arbres noirs.

Si vous connaissez l'index d'un élément dans le tableau, vous pouvez récupérer l'élément en utilisant l'index en temps O(1). Cela signifie-t-il que nous pouvons stocker les valeurs dans un tableau et utiliser la clé comme index pour trouver la valeur ? La réponse est oui, si vous pouvez mapper une clé à un index. Le tableau qui stocke les valeurs est appelé une table de hachage. La fonction qui mappe une clé à un index dans la table de hachage est appelée une fonction de hachage. Comme le montre la figure ci-dessous, une fonction de hachage obtient un index à partir d'une clé et utilise l'index pour récupérer la valeur de la clé. Le hachage est une technique qui récupère la valeur en utilisant l'index obtenu à partir de la clé sans effectuer de recherche.

Comment concevoir une fonction de hachage qui produit un index à partir d'une clé ? Idéalement, nous aimerions concevoir une fonction qui mappe chaque clé de recherche à un index différent dans la table de hachage. Une telle fonction est appelée une fonction de hachage parfaite. Cependant, il est difficile de trouver une fonction de hachage parfaite. Lorsque deux clés ou plus sont mappées sur la même valeur de hachage, nous disons qu'une collision s'est produite. Bien qu’il existe des moyens de gérer les collisions, qui seront abordés plus loin dans ce chapitre, il est préférable de les éviter en premier lieu. Ainsi, vous devez concevoir une fonction de hachage rapide et facile à calculer qui minimise les collisions.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!