Recherche de String dans une collection

Bonjour. Je recherche la structure de donnée la mieux adaptée pour rechercher une chaine de caractère parmi d'autres dans une collection. Mes chaines de caractères sont déjà triées selon l'ordre lexicographique, et je ne devrais ni insérer , ni supprimer de données. Je n'ai pas de doublons, donc un SET me semble être approprié. Un arbre me semblait etre le meilleur choix, jusqu'a ce que je lise que contains est effectué en temps constant pour un HashSet.

Pour moi temps constant signifie O(1). Je me trompe ?
Pour l'arbre, contains() est effectuée en log(n) , j'avais appris que c'était ce qui se faisait de mieux pour une recherche dans un ensemble.

Bref, je ne sais pas comment on peut avoir du temps constant pour recherche une chaine de caractère dans un HashSet... Et si on avait vraiment du temps constant quel serait l'intéret d'avoir un TreeSet par rapport au HashSet?

Bref, j'ai du manquer quelques chose là...

Ce que dit la FAQ collection, (traduite directement de la javadoc)

Citation:

---

java.util.HashSet :
Le java.util.HashSet est la plus utile des implémentations.
Note : L'ordre d'itération des éléments est aléatoire.
Complexité : Les opérations add, remove, contains and size sont exécutées en un temps constant.



java.util.TreeSet :
Le java.util.TreeSet contient un ensemble d'éléments ordonnés (il implémente également l'interface java.util.SortedSet). Les éléments sont ordonnés en fonction de leur ordre naturel (voir java.util.Comparable), ou en fonction d'un java.util.Comparator précisé à la construction du TreeSet.
Complexité : Les opérations add, remove, contains and size sont exécutées en un temps log(n).

---

Une HashSet est composé de plusieurs blocs.
Voici un exemple théorique des Strings : il y a 26 blocs. Dans le premier bloc, le mot qui commence par A, dans le deuxième par B, etc. Et pour accéder à un mot, on regarde sa première lettre, on accède au bloc, puis on le parcourt. Donc le temps d'accès est très court. En contre partie, une HashSet prend de la place en mémoire car il faut créer tous les bloc (même s'ils sont vide).
En pratique Java utilise la méthode hashCode() pour organiser les objets par bloc.

Oui, un algorithme en temps constant est en O(1).

D'après la documentation, un TreeSet est ordonné alors que HashSet ne l'est pas.

La structure de données utilisée pour maintenir cette propriété implique d'avoir des primitives en log(n).

Dans ton cas, tu as un ensemble ordonné mais tu ne le modifie pas. Cette propriété n'est donc jamais perdue. Autrement dit, utilises le HashSet sans te poser de questions.

Question subsidiaire : un ensemble ordonné est-il une liste deguisée?

Tes données doivent-elles être toujours triées dans cette collection ? Si c'est le cas, prends un TreeSet. Sinon, prends un HashSet.

Si tu cherches la performance absolue, demande-toi si le log(n) du TreeSet n'est pas suffisamment petit. Pour rappel, c'est généralement du log2(n) et donc une collection de 1 000 000 d'objets fera au plus Math.ceil(Math.log(2, 1000000)) opérations de comparaisons (soit 20).