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

Fonctions de hachage et tables

Dans cours

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, s ...

Description

Cette séance de cours couvre le concept de tables de hachage, en commençant par le lemme d'anniversaire qui analyse la probabilité des fonctions injectives. Il explique ensuite Direct-Address Tables, fonctions de hachage, collisions, et Chained-Hash-Search. L'instructeur discute également de l'analyse des recherches réussies et infructueuses dans les tables de hachage.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Enseignant·e·s (3)

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Mikhail Kapralov

Source officielle

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.

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 cryptographique

Une fonction de hachage cryptographique est une fonction de hachage qui, à une donnée de taille arbitraire, associe une image de taille fixe, et dont une propriété essentielle est qu'elle est pratiquement impossible à inverser, c'est-à-dire que si l'image d'une donnée par la fonction se calcule très efficacement, le calcul inverse d'une donnée d'entrée ayant pour image une certaine valeur se révèle impossible sur le plan pratique. Pour cette raison, on dit d'une telle fonction qu'elle est à sens unique.

Afficher plus

Séances de cours associées (42)

Analyse des tables de hachage

Couvre l'analyse des tables de hachage, y compris les opérations de recherche et les collisions attendues.

Ingénierie des systèmes décentralisés: DHT de corbeille

Couvre le Chord DHT en ingénierie décentralisée des systèmes, en mettant l'accent sur la fiabilité, la redondance et l'entretien des structures.

Analyse probabiliste: Paradoxe de l'embauche et de l'anniversaire

Explore l'analyse probabiliste dans les algorithmes, couvrant le problème de l'embauche et le paradoxe de l'anniversaire, ainsi que les tables de hachage et les fonctions.

Chord: Recherche & Routage

Couvre l'algorithme Chord pour la recherche et le routage dans les tables de hachage distribuées.

Construction en deux phases : tableaux et tableaux Hash

Explique la construction en deux phases pour les tableaux, les tables de hachage et les arbres de recherche en parallèle.

Afficher plus

Concepts associés (32)

Table de hachage

Fonction de hachage

Fonction de hachage parfait

Hachage universel

Fonction de hachage cryptographique

Afficher plus