Concept
Filtre de Bloom
Concepts associés (7)
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.
Cuckoo hashing
Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches in a variation of the behavior referred to as brood parasitism; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table.
Self-balancing binary search tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".
Ensemble (informatique)
En informatique, un ensemble ou set est un type abstrait qui peut stocker certaines valeurs, sans ordre particulier, et sans répétition. Il s'agit d'une mise en œuvre informatique de la notion mathématique d'ensemble fini. Un ensemble stocke des valeurs, sans ordre défini, et ne contient pas de données en double (la tentative d'insertion d'une donnée déjà présente est sans effet). Contrairement à la plupart des autres types de collections les ensembles sont plus utilisés pour tester l'appartenance d'une valeur à cet ensemble que pour en extraire des données.
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].
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.