Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Mise en œuvre des ensembles de hachage

Dans cours

CS-108: Pratique de la programmation orientée-objet

Les étudiants perfectionnent leurs connaissances en Java et les mettent en pratique en réalisant un projet de taille conséquente. Ils apprennent à utiliser et à mettre en œuvre les principaux types de collections (listes, ensembles, tables associatives), e ...

Description

Cette séance de cours couvre les détails d'implémentation des ensembles de hachage, y compris des concepts tels que le hachage, la structure de la table, le redimensionnement et les méthodes telles que l'ajout, le retrait et le rehachage. L'instructeur démontre la structure du code en utilisant IntelliJ IDEA.

Enseignant·e

Michel Schinz

Source officielle

Concepts associés (32)

Fonction de hachage

Quand il s'agit de mettre dans un tableau de taille raisonnable (typiquement résidant dans la mémoire principale de l'ordinateur) un ensemble de données de taille variable et arbitraire, on utilise une fonction de hachage pour attribuer à ces données des indices de ce tableau. Par conséquent, une fonction de hachage est une fonction qui associe des valeurs de taille fixe à des données de taille quelconque. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage, codes de hachage, résumés, signatures ou simplement hachages.

Table de hachage

Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif. Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.

Hachage universel

En mathématiques et en informatique, le hachage universel, en anglais universal hashing, (dans un algorithme probabiliste ou un bloc de données) est une méthode qui consiste à sélectionner aléatoirement une fonction de hachage dans une famille de fonctions de hachages qui ont certaines propriétés mathématiques. Cela permet de minimiser la probabilité de collision de hachage. Plusieurs familles de fonctions de hachages sont connues (pour hacher des entiers, des chaînes de caractères ou des vecteurs), et leur calcul est souvent très efficace.

Fonction de hachage parfait

droite|vignette|240x240px| Une fonction de hachage parfait pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. droite|vignette|240x240px| Une fonction de hachage parfait minimal pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. En informatique, une fonction de hachage parfait h pour un ensemble S est une fonction de hachage qui associe des éléments distincts de S à un ensemble de m entiers, sans collisions. En termes mathématiques, c'est une fonction injective.

Collision (informatique)

vignette|Schéma d'une collision entre deux résultats d'une fonction de hachage En informatique, une collision désigne une situation dans laquelle deux données ont un résultat identique avec la même fonction de hachage. Les collisions sont inévitables dès lors que l'ensemble de départ (données fournies) de la fonction de hachage est d'un cardinal strictement supérieur à l'ensemble d'arrivée (empreintes). Ce problème est une déclinaison du principe des tiroirs. La conséquence de ces collisions dépend de leurs applications.

Afficher plus

Séances de cours associées (35)

Mise en œuvre des ensembles : Hashing

Couvre la mise en œuvre des ensembles à l'aide du hachage et des opérations d'ensemble.

Égalité, ordre et hachage

Explique le hachage, l'égalité et l'ordre en Java, en mettant l'accent sur la compatibilité des méthodes pour un comportement de collecte correct.

Comparaison d'objets : Comparable vs Comparator

Couvre les concepts d'interfaces Comparable et Comparator en Java, en expliquant comment les classes implémentent ces interfaces pour permettre la comparaison d'objets.

Mise en œuvre des listes à liens singuliers

Couvre l'implémentation de listes liées séparément en Java, en se concentrant sur des concepts tels que les nœuds, la gestion de la taille, l'ajout, la suppression et l'obtention d'éléments.

Collections : Hashcode et méthodes égales

Explique l'importance du hashcode et égalise les méthodes en Java.

Afficher plus

Concepts associés (32)

Fonction de hachage

Table de hachage

Hachage universel

Fonction de hachage parfait

Collision (informatique)

Afficher plus