Bonjour,
Quel est la difference entre TreeSet et HashSet ?
Merci
Bonjour,
Quel est la difference entre TreeSet et HashSet ?
Merci
TreeSet<T> implémente SortedSet<T>, alors que HashSet<T> n'implémente "que" Set<T>.
Dit autrement, ça veut dire que TreeSet implémente un ensemble ordonné : si tu itères sur les éléments du TreeSet, tu les obtiendras en ordre croissant (selon la méthode compareTo() de Comparable).
Par ailleurs, TreeSet repose sur la méthode compareTo() pour fonctionner. HashSet repose sur la méthode hashCode().
Si tu as besoin d'avoir un ensemble trié -> TreeSet
Sinon -> HashSet (car plus rapide)
sjrd, ancien rédacteur/modérateur Delphi.
Auteur de Scala.js, le compilateur de Scala vers JavaScript, et directeur technique du Scala Center à l'EPFL.
Découvrez Mes tutoriels.
Je sais que désormais vivre est un calembour,
La mort est devenue un état permanent,
Le monde est aux fantômes, aux hyènes et aux vautours.
Moi je vous dis bravo et vive la mort.
D'abord, un Set est un ensemble sans doublons.
Un TreeSet est un ensemble ordonné soit selon l'odre naturel, soit selon l'ordre indiqué dans le comparateur de l'object en generic.
Set<Personne> tree= new TreeSet<Personne>(new Personne()) ;
ici la classe Personne implemente l'interface Comparator.
L'ajout et la suppresion de TreeSet se fait en log(n) ou n est sa taille.
HashSet est un Set sans tri. L'ajout et la suppresion sont tres rapide . L'ajout et la suppresion se fait en temps constant.
J'aurai quelques questions supplémentaires sur le même sujet :
Pourquoi utiliser un TreeSet plutôt qu'un LinkedHashSet qui permet également un ordonnancement de ses élements ? Après tout le TreeSet est construit au fur et à mesure qu'on y rentre des élements, et au cours de sa construction il peut devenir très désequilibré réduisant grandement ses performances (l'accès se fait alors en o(n) plutôt qu'en o(log(n))) et nécessitant de rééquilibrer l'arbre, ce qui est couteux en temps CPU.
En comparaison, les accès dans un LinkedHashSet se font toujours en temps constant : o(1) (bien qu'un temps constant plus élevé que pour les HashSet standard).
Un de mes collègues m'a dit que les TreeSet était ThreadSafe contrairement aux HashSet, est-ce vrai ? Dans ce cas pourquoi ne pas implémenter les classes ThreadSafeHashSet et ThreadSafeLinkedHashSet (ou tout autre nom un peu plus court ) qui serait également threadsafe, juste en synchronisant les méthodes d'accès ? On conserverait ainsi les performances temps constant des hashSet tout en étant ThreadSafe...
LinkedHashSet n'implémente pas SortedSet. Puisqu'il n'est pas trié. Il se contente de conserver l'ordre d'insertion des éléments, il ne les trie pas.
Non. Dis-lui qu'un dénommé thelvin lui file une torgnole virtuelle.
Jette un œil à Collections.synchronizedSet() et Collections.synchronizedSortedSet()
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
J'ai crée ce code:
Avec la classe copmarator
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 TreeSet<Pays> mySet3 = new TreeSet<>(new copmarator()); mySet3.add(new Pays(5,"italie")); mySet3.add(new Pays(12,"Canada")); mySet3.add(new Pays(30,"UAE")); mySet3.add(new Pays(30,"UAE")); for(Pays p : mySet3){ System.out.println(p); } System.out.println(mySet3);
et ça a marché! sans pour autant définir la méthode compareTo() de l'interface Comparable.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 public class copmarator implements Comparator<Pays>{ @Override public int compare(Pays o1, Pays o2) { return o1.id-o2.id; }
Oui, bon. TreeSet repose sur un système de comparaison de ses éléments deux à deux.
Ou bien c'est le fait que les éléments du TreeSet implémentent Comparable et se comparent à l'aide de leur méthode compareTo(),
ou bien c'est en fournissant un Comparator au TreeSet qui se charge de comparer les éléments avec sa méthode compare().
Les deux sont utilisables, et c'est ma foi bien pratique, certes.
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
Logique!
Juste une question, pourquoi les TreeSet n'acceptent pas les doublons (sans avoir redéfinir la méthode equals() et hashcode() comme dans le cas du hashSet)?
Parce que ce sont des Set, et que le principe d'un Set est qu'il n'y a pas de doublon.
C'est vrai qu'on peut trouver une utilité à une Collection qui trie ses éléments dans un arbre binaire de recherche tout en acceptant les doublons. Ce qui n'est pas le cas de TreeSet.
Mais on peut trouver ça avec un simple TreeMap<TaClasse, Integer> dont les valeurs sont le nombre de fois qu'on a l'élément.
TreeSet précise bien que sa méthode de comparaison, inférieur, supérieur ou égal, est basée uniquement sur le résultat de compareTo() ou compare() en fonction de celui qui est utilisé. hashcode() et equals() ne sont pas utilisées, car elles ne permettent pas de déterminer en cas d'inégalité, si c'est inférieur ou supérieur.
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager