Quatre besoins, quelle structure ?

• Table de hachage. On ne demande que l'appartenance, jamais l'ordre : c'est exactement le contrat du hachage, et son $O(1)$ moyen est ici décisif. Mesuré sur $200000$ mots : $0,06$ microseconde par recherche, contre $1203$ microsecondes pour une liste d'association — un facteur $20000$.
• Arbre de recherche. Le mot « trié » décide : le parcours infixe donne le classement pour rien, en $\Theta (n)$, quand la table oblige à tout extraire puis trier en $\Theta (n\log n)$. Mesuré sur $200000$ clés : $0,014$ s par l'arbre contre $0,127$ s par la table, soit un facteur $9$ — et il croît en $\log n$.
• Liste d'association. Douze éléments : $O(n)$ vaut $O(12)$. Une table de hachage y coûterait un calcul de haché à chaque accès, une allocation de tableau, et surtout un fichier de plus à lire. La complexité asymptotique ne dit rien à $n=12$ : on choisit ici la structure la plus simple à écrire et à relire.
• Aucune des trois. « Commence par » n'est ni une égalité ni une comparaison de clés entières : c'est une question sur les préfixes. Un ABR sur l'ordre alphabétique la rend possible — les mots de préfixe info forment un intervalle, qu'on extrait en $O(h+k)$ — mais la structure faite pour cela est l'arbre préfixe (trie) du chapitre chap:textes, où l'on descend une lettre par niveau.

La question à se poser, et elle vient avant toutes les autres : de quoi ai-je besoin en plus de l'égalité ? Rien, c'est le hachage. Un ordre, c'est l'arbre. Une structure interne à la clé, c'est un arbre préfixe. La complexité ne départage qu'ensuite.