Différence entre TreeSet et HashSet

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)

Citation:

---

Envoyé par sjrd

tu les obtiendras en ordre croissant (selon la méthode compareTo() de Comparable)

---

Ou selon la méthode compare() du Comparator qu'on lui donne si les objets qu'on veut trier possèdent déjà un ordre "naturel" (ex : trier des String par nombre de caractères)

Citation:

---

Envoyé par bestcasaoui

Bonjour,
Quel est la difference entre TreeSet et HashSet ?

Merci

---

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 8-) ) 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...

Citation:

---

Envoyé par Roman_Adamski

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).

---

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.

Citation:

---

Envoyé par Roman_Adamski

Un de mes collègues m'a dit que les TreeSet était ThreadSafe contrairement aux HashSet, est-ce vrai ?

---

Non. Dis-lui qu'un dénommé thelvin lui file une torgnole virtuelle.

Citation:

---

Envoyé par Roman_Adamski

Dans ce cas pourquoi ne pas implémenter les classes ThreadSafeHashSet et ThreadSafeLinkedHashSet (ou tout autre nom un peu plus court 8-) ) 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...

---

Jette un œil à Collections.synchronizedSet() et Collections.synchronizedSortedSet()

Citation:

---

Envoyé par sjrd

Par ailleurs, TreeSet repose sur la méthode compareTo() pour fonctionner.

Si tu as besoin d'avoir un ensemble trié -> TreeSet
Sinon -> HashSet (car plus rapide)

---

J'ai crée ce code:

Code:

---

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);

---

Avec la classe copmarator

Code:

---

1 2 3 4 5

public class copmarator implements Comparator<Pays>{   @Override public int compare(Pays o1, Pays o2) { return o1.id-o2.id; }

---

et ça a marché! sans pour autant définir la méthode compareTo() de l'interface Comparable.

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.

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.