Hashset contre Treeset

Question

J'ai toujours aimé les arbres, ce bel O (n * lg (n)) et la propreté de ceux-ci. Cependant, chaque ingénieur logiciel que j'ai connu m'a demandé clairement pourquoi j'utiliserais un TreeSet . D'un point de vue CS, je ne pense pas que cela ait autant d'importance que ce que vous utilisez, et je ne me soucie pas de bidouiller avec les fonctions de hachage et les buckets (dans le cas de Java).

Dans quels cas dois-je utiliser un HashSet sur un TreeSet ?

Answer 1

HashSet est beaucoup plus rapide que TreeSet (constante de temps par rapport à log-temps pour la plupart des opérations comme ajouter, supprimer et contient), mais n'offre pas des garanties de classement comme TreeSet.

HashSet:

• la classe offre constante de la performance en temps pour les opérations de base (ajouter, supprimer, contient et la taille).
• il ne garantit pas que l'ordre des éléments restent constants au cours du temps
• itération de la performance dépend de la capacité initiale et le facteur de charge de la HashSet.
  • C'est assez en sécurité pour accepter facteur de charge par défaut, mais vous pouvez spécifier une capacité initiale qui est environ deux fois la taille à laquelle vous vous attendez à l'ensemble de croître.

TreeSet:

• garanties log(n) coût du temps pour les opérations de base (ajouter, supprimer et contient)
• garantit que les éléments de jeu sera triée (par ordre croissant, naturel, ou spécifiée par l'intermédiaire de son constructeur)
• n'offrent pas les paramètres de réglage pour l'itération de la performance
• offre un peu de pratique méthodes pour faire face à l'ensemble ordonné comme first(), last(), headSet(), et tailSet() etc

Points importants:

• Les deux garantie sans doublon de la collecte des éléments
• Il est généralement plus rapide pour ajouter des éléments à la HashSet et ensuite de les convertir à la collecte d'un TreeSet pour un double-gratuits triés traversée.
• Aucun de ces mise en œuvre sont synchronisés. Si plusieurs threads accèdent à un ensemble simultanément, et au moins l'un des threads modifie l'ensemble, il doit être synchronisé à l'extérieur.
• LinkedHashSet est en quelque sorte intermédiaire entre HashSet et TreeSet. Mis en œuvre comme une table de hachage avec une liste chaînée de courir à travers elle, cependant elle offre d'insertion-commandé itération qui n'est pas la même que triées de la traversée de la garantie par TreeSet.

Donc, le choix de l'utilisation dépend entièrement de vos besoins, mais j'ai l'impression que même si vous avez besoin d'une collection ordonnée, alors vous devriez préfèrent encore HashSet pour créer le Jeu, puis de le convertir en TreeSet.

• par exemple, SortedSet<String> s = new TreeSet<String>(hashSet);

Answer 2

Un avantage à ne pas encore parlé d'un TreeSet est qu'elle a plus de "localité", qui est un raccourci pour dire (1) si les deux entrées sont à proximité, dans l'ordre, un TreeSet lieux à proximité les uns des autres dans la structure de données, et partant, dans la mémoire; et (2) ce stage a l'avantage du principe de localité, qui dit que des données similaires est souvent accessible par une application avec une fréquence similaire.

Ceci est en contraste à un HashSet, qui écarte les entrées de tous les plus de mémoire, peu importe ce que leurs clés.

Lorsque le temps de latence des coûts de la lecture à partir d'un disque dur est des milliers de fois le coût de la lecture à partir du cache ou de la RAM, et lorsque les données est vraiment accessible avec de la localité, le TreeSet peut être un bien meilleur choix.

Answer 3

HashSet O(1) pour accéder à des éléments, de sorte qu'il n'est certainement question. Mais le maintien de l'ordre des objets dans le décor n'est pas possible.

TreeSet est utile si le maintien de l'ordre(En termes de valeurs et de ne pas l'ordre d'insertion) questions à vous. Mais, comme vous l'avez remarqué, vous êtes commercial de l'ordre pour les plus lents de temps d'accès à un élément: O(log n) pour les opérations de base.

À partir de la javadoc TreeSet:

Cette application fournit la garantie log(n) coût du temps pour les opérations de base (add, remove et contains).

Answer 4

1.Hash set autorise un objet nul

2.Tress set n'autorisera pas d'objet nul. Si vous essayez d'ajouter une valeur nulle, je jetterai une exception de pointeur nul

3.Hash réglé beaucoup plus vite que l'ensemble de l'arbre.

par exemple

  TreeSet<String> ts =new TreeSet<String>();
 ts.add(null) //throw null pointer exception

 HashSet<String> hs =new HashSet<String>();
 hs.add(null) //runs fine
 

Answer 5

La raison pour laquelle la plupart des utilisations, HashSet , c'est que les opérations sont (en moyenne) O(1) au lieu de O(log n). Si le jeu contient des éléments standard vous ne serez pas "déconner avec les fonctions de hachage", comme ce qui a été fait pour vous. Si l'ensemble contient des classes personnalisées, vous devez implémenter hashCode utilisation HashSet (bien qu'Efficace Java montre comment), mais si vous utilisez un TreeSet que vous avez à faire c' Comparable ou de fournir un Comparator. Cela peut être un problème si la classe n'ont pas d'ordre particulier.

J'ai parfois utilisé TreeSet (ou réellement TreeMap) pour de très petites séries de cartes (< 10 éléments) bien que je n'ai pas vérifié pour voir si il n'y a aucun gain réel en agissant de la sorte. Pour les grands ensembles, la différence peut être considérable.

Maintenant, si vous avez besoin de la triés, TreeSet est approprié, même si les mises à jour sont fréquentes et la nécessité pour un résultat trié est rare, parfois en copiant le contenu à une liste ou un tableau d'un classement peut être plus rapide.