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. Les valeurs sont généralement utilisées pour être les indices d'une table de taille raisonnable appelée table de hachage. Le hachage ou adressage de stockage dispersé est donc l'utilisation d'une fonction de hachage pour créer les indices d'une table de hachage. Les fonctions de hachage sont utilisées dans les applications de stockage et d'indexation de données pour accéder aux données en un temps réduit, en fait quasi-constant. Elles requièrent un espace de stockage à peine plus grand que l'espace total requis pour les données. Ainsi, le hachage est une forme d'accès aux données efficace en termes de calcul et d'espace de stockage. L'intérêt des fonctions de hachage repose sur de bonnes propriétés statistiques. En effet, le comportement dans le pire des cas est mauvais, mais il se manifeste avec une probabilité extrêmement faible, en fait négligeable, et le comportement dans le cas moyen est optimal (collision minimale ). Les fonctions de hachage sont liées (et souvent confondues avec) les sommes de contrôle, les clés de contrôle, les empreintes numériques, la compression avec perte, les générateurs de nombres aléatoires, les codes correcteur et les chiffrements. Bien que les concepts se chevauchent dans une certaine mesure, chacun a ses propres utilisations et exigences et est conçu et optimisé différemment.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (32)

Personnes associées (14)

Concepts associés (43)

Cours associés (27)

Séances de cours associées (184)

Liquid-liquid phase separation (LLPS) of proteins and RNAs has emerged as the driving force underlying the formation of membrane-less organelles. Such biomolecular condensates have various biological

OXFORD UNIV PRESS2021

Inverse Modelling and Predictive Inference in Continuum Mechanics: a Data-Driven Approach

Claire Marianne Charlotte Capelo

The explosive growth of machine learning in the age of data has led to a new probabilistic and data-driven approach to solving very different types of problems. In this paper we study the feasibility

2020

Time in cryptography

Gwangbae Choi

Time travel has always been a fascinating topic in literature and physics. In cryptography, one may wonder how to keep data confidential for some time. In this dissertation, we will study how to make

EPFL2020

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

CS-322: Introduction to database systems

This course provides a deep understanding of the concepts behind data management systems. It covers fundamental data management topics such as system architecture, data models, query processing and op

CS-250: Algorithms

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, ma

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.

Une somme de contrôle (checksum en anglais) est une courte séquence de données numériques calculée à partir d'un bloc de données plus important (par exemple un fichier ou un message) permettant de vérifier, avec une très haute probabilité, que l'intégrité de ce bloc a été préservée lors d'une opération de copie, stockage ou transmission. On parle aussi parfois d'empreinte numérique. Pour l'utilisateur final, les sommes de contrôle se présentent typiquement sous la forme de nombres au format hexadécimal.

Mise en œuvre des ensembles de hachage

Couvre les détails d'implémentation des jeux de hachage et des méthodes associées à l'aide d'IntelliJ IDEA.

Influence sociale et choix

Explore l'influence sociale, la démocratie, l'autonomie individuelle, l'égalité et les modèles de prise de décision.

Mise en œuvre des ensembles : Hashing

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