Comment choisir entre une table de hachage et un arbre de recherche équilibré ?

Les tables de hachage offrent une recherche et une insertion en O(1) en moyenne mais sans ordre, tandis que les arbres de recherche équilibrés permettent des opérations en O(log n) et maintiennent les clés triées, supportant les requêtes par intervalle et le parcours ordonné. Choisissez le hachage pour les recherches de clés pures et un arbre lorsque l'ordre ou les opérations par intervalle sont importants.

Que signifie le coût amorti pour une structure de données ?

Le coût amorti est le coût moyen par opération sur une séquence d'opérations dans le pire des cas. Un tableau dynamique, par exemple, paie occasionnellement O(n) pour se redimensionner mais la moyenne est de O(1) par ajout car les redimensionnements sont rares par rapport aux ajouts peu coûteux.

Structures de données fondamentales

Les structures de données fondamentales sont des méthodes organisées de stockage et d'accès aux données — tableaux, listes chaînées, tables de hachage, arbres, tas et leurs variantes — qui déterminent l'efficacité des opérations qui en découlent.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

Une structure de données est une manière d'organiser et de stocker des données afin que les opérations définies par son type de données abstrait puissent être effectuées efficacement ; les structures de données fondamentales constituent le petit ensemble de structures à usage général à partir desquelles la plupart des autres sont construites.

Scope

Ce domaine couvre les types de données abstraits (listes, dictionnaires, files de priorité, ensembles) et les structures concrètes qui les implémentent, ainsi que le coût de leurs opérations fondamentales (insertion, suppression, recherche, mise à jour) dans le pire des cas et en analyse amortie. Il examine comment le choix d'une structure influence la performance des algorithmes et se connecte aux paradigmes de conception ainsi qu'aux algorithmes de graphes et de chaînes de caractères qui dépendent de ces structures. Il exclut les structures de stockage de bases de données et de systèmes de fichiers traitées dans d'autres sous-domaines.

Sub-topics

Core questions

Quel type de données abstrait une application nécessite-t-elle, et quelle structure concrète l'implémente le mieux ?
Quels sont les coûts dans le pire des cas et les coûts amortis de chaque opération sur une structure donnée ?
Comment les structures échangent-elles la mémoire contre le temps, ou la vitesse de lecture contre la vitesse de mise à jour ?
Comment le maintien d'un invariant (ordre, équilibre, propriété de tas) limite-t-il les coûts des opérations ?
Quand une structure simple est-elle préférable à une structure asymptotiquement plus rapide mais plus complexe ?

Key concepts

type de données abstrait
tableaux et listes chaînées
piles et files
tables de hachage
arbres binaires de recherche
arbres équilibrés
tas et files de priorité
analyse amortie
compromis temps-espace

Key theories

Types de données abstraits versus implémentations: Un type de données abstrait spécifie les opérations et leur sémantique indépendamment de leur représentation ; plusieurs structures de données concrètes peuvent implémenter le même TDA avec des profils de performance différents, permettant aux concepteurs de raisonner séparément sur la correction et le coût.
Analyse amortie: Certaines structures (tableaux dynamiques, splay trees) ont des opérations occasionnellement coûteuses mais des opérations peu coûteuses en moyenne sur une séquence ; l'analyse amortie (méthodes agrégée, comptable, du potentiel) borne rigoureusement ce coût moyen.

Clinical relevance

Les structures de données fondamentales sont les éléments constitutifs de pratiquement tous les logiciels : les tables de hachage sous-tendent les dictionnaires et les index de bases de données, les arbres équilibrés et les arbres B organisent les systèmes de fichiers et les bases de données, les files de priorité pilotent les ordonnanceurs et les simulations d'événements, et le bon choix de structure détermine souvent si un système est évolutif.

History

Les structures de données fondamentales ont été cataloguées dans l'ouvrage de Knuth, The Art of Computer Programming, à partir de 1968. Les arbres auto-équilibrés (arbres AVL, 1962 ; arbres rouge-noir et arbres B dans les années 1970) et les structures avancées telles que les tas de Fibonacci et les splay trees (années 1980, en grande partie grâce à Tarjan et ses collaborateurs) ont étendu le domaine, tandis que l'analyse amortie a fourni une description rigoureuse de leurs performances.

Key figures

Donald Knuth
Robert Sedgewick
Robert Tarjan
Rudolf Bayer

Seminal works

knuth1997vol1
cormen2009
sedgewick2011

Frequently asked questions

Comment choisir entre une table de hachage et un arbre de recherche équilibré ?: Les tables de hachage offrent une recherche et une insertion en O(1) en moyenne mais sans ordre, tandis que les arbres de recherche équilibrés permettent des opérations en O(log n) et maintiennent les clés triées, supportant les requêtes par intervalle et le parcours ordonné. Choisissez le hachage pour les recherches de clés pures et un arbre lorsque l'ordre ou les opérations par intervalle sont importants.
Que signifie le coût amorti pour une structure de données ?: Le coût amorti est le coût moyen par opération sur une séquence d'opérations dans le pire des cas. Un tableau dynamique, par exemple, paie occasionnellement O(n) pour se redimensionner mais la moyenne est de O(1) par ajout car les redimensionnements sont rares par rapport aux ajouts peu coûteux.