Recherche d'un élément dans une table

Les structures de données servent d'abord à contenir des données. Selon les opérations à réaliser sur ces données, on choisira une structure particulière, par exemple l'une des trois structures les plus usuelles : d'ensemble, de liste ou de table. Il est fréquent que les données soient des associations d'une clé (ou identificateur) et d'une information ; par exemple, l'association nom $\to$ numéro de téléphone (c'est simplement ce que l'on appelle une application en mathématiques). La structure de table offre les trois opérations suivantes :

• l'insertion dans la table d'une clé et de l'information associée ;
• la recherche de l'information associée à une clé ;
• (éventuellement) la suppression d'une association de clé donnée.

L'API Java 2 offre l'interface java.util.Map avec ces mêmes fonctionnalités (les types interfaces de java sont décrits en § 3.1). Par souci de généricité, on représente en Java la clé et son information par des instances de la classe Object ; souvent, la clé est une chaîne de caractères (par exemple, un nom), et l'information est d'un type quelconque. Plutôt que de retourner un void, il est préférable que les méthodes insérer() et supprimer() retournent un boolean qui indique si l'opération est réussie. Le type abstrait de cette structure de données peut être défini en Java comme l'interface suivante (les noms traditionnels de ces opérations en anglais sont put, get, remove) :

interface Table {
  boolean insérer(Object clé, Object valeur);
  Object rechercher(Object clé);
  boolean supprimer(Object clé);
}

Il en existe au moins deux implémentations efficaces : les tables de hachage et les arbres bicolores. Avant de les présenter, il est utile de montrer une implémentation plus simple et comment tenter de l'améliorer. Notons d'ailleurs que les trois opérations ne sont pas toujours réalisées avec la même fréquence. Dans le cas d'un annuaire, les interrogations (ou recherches) sont beaucoup plus fréquentes que les insertions ou les suppressions ; on peut donc chercher à optimiser les recherches plutôt que les deux autres opérations.