Concept
Table de hachage
Concepts associés (35)
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.
Arbre bicolore
Un arbre bicolore, ou arbre rouge-noir ou arbre rouge et noir est un type particulier d'arbre binaire de recherche équilibré, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomme symmetric binary B-trees (littéralement « arbres B binaires symétriques »). Chaque nœud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa « couleur » (rouge ou noir).
Index (base de données)
En informatique, dans les bases de données, un index est une structure de données utilisée et entretenue par le système de gestion de base de données (SGBD) pour lui permettre de retrouver rapidement les données. L'utilisation d'un index simplifie et accélère les opérations de recherche, de tri, de jointure ou d'agrégation effectuées par le SGBD. L’index placé sur une table va permettre au SGBD d'accéder très rapidement aux enregistrements, selon la valeur d'un ou plusieurs champs.
Linear probing
Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key. It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel and first analyzed in 1963 by Donald Knuth. Along with quadratic probing and double hashing, linear probing is a form of open addressing. In these schemes, each cell of a hash table stores a single key–value pair.
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).
Recherche séquentielle
vignette|Diagramme de recherche séquentielle La recherche séquentielle ou recherche linéaire est un algorithme pour trouver une valeur dans une liste. Elle consiste simplement à considérer les éléments de la liste les uns après les autres, jusqu'à ce que l'élément soit trouvé, ou que toutes les cases aient été lues. Elle est aussi appelée recherche par balayage. La recherche séquentielle consiste à prendre les éléments de la liste les uns après les autres, jusqu'à avoir trouvé la cible, ou avoir épuisé la liste.
Table de correspondance
Une table de correspondance (aussi appelé tableau de correspondances, ou Lookup Table (LUT) en anglais) est un terme informatique et électronique désignant une liste d'association de valeurs. Elle se comporte sur le même modèle qu'une table de vérité désignant sa sortie de manière unique en fonction de ses entrées et du contenu de la table. Il s'agit d'une structure de données stockée en mémoire, employée pour remplacer un calcul par une opération plus simple de consultation.
Bibliothèque standard
vignette|Binario cropped Une bibliothèque standard pour un langage de programmation est une bibliothèque logicielle qui est utilisée dans toute implémentation de ce langage. Une bibliothèque standard peut inclure : Fonctions Macros Variables globales Classes Gabarits (templates) La plupart des bibliothèques standard incluent : des algorithmes (par exemple pour le tri) ; des structures de données (telles que les listes, les arbres et les tables de hachage) ; des routines d'entrées-sorties et d'appel système.
Matrice Judy
En informatique, une matrice Judy est une structure de données mettant en œuvre un type de tableau associatif offrant de hautes performances et une faible utilisation de la mémoire. Contrairement à la plupart des autres bases de données clé-valeur, les matrices Judy n'utilisent pas de hachage, exploitent la compression sur leurs clés (qui peuvent être des entiers ou des chaînes de caractères) et peuvent représenter efficacement des données éparses, c'est-à-dire qu'ils peuvent avoir de grandes plages d'indices non attribués sans augmenter considérablement l'utilisation de la mémoire ou le temps de traitement.
Dynamic perfect hashing
In computer science, dynamic perfect hashing is a programming technique for resolving collisions in a hash table data structure. While more memory-intensive than its hash table counterparts, this technique is useful for situations where fast queries, insertions, and deletions must be made on a large set of elements. static hashing#FKS Hashing The problem of optimal static hashing was first solved in general by Fredman, Komlós and Szemerédi.