Discussion :

[K-you]

Bonjour,

Je me pose une question en terme de complexité des structures de données disponibles en Java.

Je souhaite maintenir une liste de String sans doublon avec des ajouts/suppressions successifs. A tout moment, je dois être capable de savoir si une liste contient déjà une String demandée.

Alors le moyen le plus naturel de faire en Java est d'avoir un objet Arraylist<String> et vérifier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

monArrayListe.contains(autreString);

chaque fois. Mais en termes de complexité, la recherche dans une liste est très supérieure à la recherche dans une table de hachage (Hashtable).

Etant donné que je suis sur un serveur (l'espace de stockage n'est donc pas une limite), et que cette requête de recherche se fait très souvent en comparaison des requêtes d'ajouts/suppressions, est-il plus efficace en terme de temps d'exécution de stocker mes Strings dans une Hashtable<String, Short> (Short parce que la Hashtable Java doit avoir 2 dimensions), ou dans une Arraylist de String ? En d'autres termes, est-ce que pour les List Java l'appel à la méthode contains est plus performant qu'un parcourt itératif qui s'avère coûteux sur des listes importantes ?

[Hizin]

Si l'unicité est un critère important, je pencherai plutôt vers un Set (http://docs.oracle.com/javase/6/docs.../util/Set.html).

La plus adaptée à des ajouts/retraits massifs par contre ... je dirai HashSet au vu de ce que je lis dans la doc (temps constant pour contains, add et remove), mais je ne suis pas pleinement convaincu.

[thelvin]

Alors le moyen le plus naturel de faire en Java est d'avoir un objet Arraylist<String>

Non. Un HashSet<String>.

est-il plus efficace en terme de temps d'exécution de stocker mes Strings dans une Hashtable<String, Short> (Short parce que la Hashtable Java doit avoir 2 dimensions), ou dans une Arraylist de String ?

Un HashSet de String. Ça fonctionne avec des tables de hachages comme Hashtable, ce qui fait des performances similaires, mais :
- Ça évite de se traîner une deuxième dimension inutile.
- Hashtable est synchronisé, ce qui n'est pas forcément ce que tu veux et peut se répercuter sur les performances. HashSet n'est pas synchronisé et n'a pas ce problème, mais on peut en avoir une vue synchronisée avec Collections.synchronizedSet() si nécessaire.

En d'autres termes, est-ce que pour les List Java l'appel à la méthode contains est plus performant qu'un parcourt itératif qui s'avère coûteux sur des listes importantes ?

Non, c'est un parcours itératif tout simple, et donc, coûteux.

[adiGuba]

Salut,


Les Set sont fait pour cela. Un Set correspond à une collection d'élément non-ordonné mais unique !


L'implementation HashSet utilise une table de hachage pour un accès plus rapide...


a++


[edit] grillé

[K-you]

Merci, tout est dit. Résolu !