Concept
Fonction de hachage parfait
Concepts associés (7)
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.
Filtre de Bloom
En informatique, et plus précisément en algorithmique, un filtre de Bloom est une structure de données inventée par Burton Howard Bloom en 1970. C'est une implémentation du type abstrait Ensemble. Cette structure est probabiliste, c'est-à-dire qu'elle utilise des probabilités, et que sa correction est probabiliste. Plus précisément, lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir : avec certitude l'absence d'un élément (il ne peut pas y avoir de faux négatif) ; avec une certaine probabilité la présence d'un élément (il peut y avoir des faux positifs).
Algorithme probabiliste
En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].
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.
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.
Tableau (structure de données)
En informatique, un tableau est une structure de données représentant une séquence finie d'éléments auxquels on peut accéder efficacement par leur position, ou indice, dans la séquence. C'est un type de conteneur que l'on retrouve dans un grand nombre de langages de programmation. Dans les langages à typage statique (comme C, Java et OCaml), tous les éléments d’un tableau doivent être du même type. Certains langages à typage dynamique (tels APL et Python) permettent des tableaux hétérogènes.