Arbre binaire de recherche -> lookup en O(longueur de la chaîne).
Table de hachage -> lookup en (temps de calcul du hash)+O(1+(probabilité de collision))

Ce sont des chaînes d'octets ou de bits? Parce que pour des chaînes d'octets, tu peux aussi essayer les arbres d'ordre 256 (l'ordre est le nombre de nœuds fils, par exemple arbre binaire == arbre d'ordre 2), ça te fera en théorie un lookup 8 fois plus rapide.