La plus simple des implémentations de la structure abstraite de table se fait à l'aide d'un tableau, et l'algorithme de recherche le plus élémentaire est la recherche séquentielle, qui parcourt le tableau jusqu'à ce qu'un objet de clé donnée soit trouvé ou bien que la fin du tableau soit atteinte :
class TableParTableau implements Table {
static class Association {
Object clé;
Object information;
Association(Object clé, Object information) {
if (clé == null || information == null)
throw new NullPointerException();
this.clé = clé;
this.information = information;
}
}
private Association[] tableau;
private int nbElements;
TableParTableau(int n) {
tableau = new Association[n];
}
public boolean insérer(Object clé, Object information) {
if (nbElements < tableau.length) {
tableau[nbElements] = new Association(clé, information);
nbElements++;
return true;
} else return false;
}
public Object rechercher(Object clé) {
for (int i=0; i<nbElements; i++) {
if (tableau[i].clé != null &&
tableau[i].clé.equals(clé)) {
return tableau[i].information;
}
}
return null; // objet non trouvé
}
public boolean supprimer(Object clé) {
for (int i=0; i<nbElements; i++) {
if (tableau[i].clé != null &&
tableau[i].clé.equals(clé)) {
tableau[i].clé = null;
tableau[i].information = null;
return true;
}
}
return false;
}
}
La classe TableParTableau définit une classe membre statique Association pour contenir les couples (clé, information). Java permet en effet la définition d'une classe dans le corps d'une autre classe :
class A {
class B {}
}
La classe B est dite imbriquée dans la classe A. Une classe imbriquée peut être déclarée static , auquel cas elle ne peut accéder qu'aux membres statiques de la classe englobante, de façon analogue à une méthode statique. Une classe statique est une classe d'intérêt local. Une classe imbriquée non statique est appelée une classe intérieure : une instance d'une classe intérieure n'existe qu'au sein d'une instance de la classe englobante. Une classe intérieure peut accéder à tous les membres de la classe englobante.
Le constructeur Association() s'assure que ses arguments sont non nuls, de sorte qu'on peut utiliser la valeur null pour indiquer qu'un élément a été supprimé. L'élément du tableau occupé par un élément supprimé n'est pas réutilisé par l'insertion, ce qui permet de faire l'insertion en temps constant.
On notera que le << return tableau[i].information; >> placé dans la boucle de recherche permet de s'en échapper (c'est-à-dire de ne pas exécuter les itérations suivantes) en retournant immédiatement une valeur. Si l'on souhaitait s'échapper de la boucle sans retourner immédiatement, on placerait un << break; >> à la même place.
Le nombre maximum de comparaisons d'objets (invocation de la méthode equals()) effectuées par cet algorithme est de N, le nombre d'éléments insérés, ce maximum étant atteint quand la clé cherchée n'est pas trouvée ; en moyenne, il procède à N/2 comparaisons. Cela est très mauvais, et on sait faire beaucoup mieux.