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 : Hashing

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 la mise en œuvre d'ensembles utilisant le hachage, en se concentrant sur la classe SHashSet. Les sujets incluent la création d'une table de hachage, l'ajout d'éléments, la suppression d'éléments, la vérification de l'existence d'éléments et l'itération de l'ensemble. La séance de cours traite également de l'utilisation des itérateurs et des consommateurs dans le contexte des opérations définies.

Enseignant·e

Michel Schinz

Source officielle

Proximité ontologique

Informatique théorique

Théorie des langages de programmation: Langage de programmation de haut niveau

Concepts associés (32)

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.

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.

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.

Java syntax

The syntax of Java is the set of rules defining how a Java program is written and interpreted. The syntax is mostly derived from C and C++. Unlike in C++, in Java there are no global functions or variables, but there are data members which are also regarded as global variables. All code belongs to classes and all values are objects. The only exception is the primitive types, which are not represented by a class instance for performance reasons (though can be automatically converted to objects and vice versa via autoboxing).

Java version history

The Java language has undergone several changes since JDK 1.0 as well as numerous additions of classes and packages to the standard library. Since J2SE 1.4, the evolution of the Java language has been governed by the Java Community Process (JCP), which uses Java Specification Requests (JSRs) to propose and specify additions and changes to the Java platform. The language is specified by the Java Language Specification (JLS); changes to the JLS are managed under JSR 901.

Afficher plus

Séances de cours associées (35)

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.

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 ensembles : Partie I

Couvre l'implémentation de classes héritables pour les ensembles simplifiés en Java.

É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.

Motifs de conception: Observateur

Couvre la mise en œuvre du modèle de conception Observer en Java.

Afficher plus

Concepts associés (32)

Table de hachage

Fonction de hachage

Fonction de hachage parfait

Java syntax

Java version history

Afficher plus