Question Hashset vs Treeset


J'ai toujours aimé les arbres, ça O(n*lg(n)) et la propreté de ceux-ci. Cependant, chaque ingénieur logiciel que j'ai connu m'a demandé pourquoi j'utiliserais un TreeSet. Sur un fond de CS, je ne pense pas que cela compte beaucoup pour que vous utilisiez, et je ne me soucie pas de jouer avec les fonctions de hachage et les seaux (dans le cas de Java).

Dans quels cas dois-je utiliser un HashSet au cours d'une TreeSet?


442
2017-09-23 00:11


origine


Réponses:


HashSet est beaucoup plus rapide que TreeSet (temps constant par rapport au temps de connexion pour la plupart des opérations, comme ajouter, supprimer et contenir), mais n'offre aucune garantie de classement comme TreeSet.

HashSet

  • la classe offre des performances à temps constant pour les opérations de base (ajout, suppression, contenu et taille).
  • cela ne garantit pas que l'ordre des éléments restera constant dans le temps
  • la performance de l'itération dépend de la capacité initiale et le facteur de charge du HashSet.
    • Il est tout à fait sûr d'accepter le facteur de charge par défaut, mais vous pouvez spécifier une capacité initiale environ deux fois supérieure à la taille à laquelle vous vous attendez à ce que l'ensemble augmente.

TreeSet

  • garantit le log (n) temps coût pour les opérations de base (ajouter, supprimer et contient)
  • garantit que les éléments d'ensemble seront triés (ascendant, naturel, ou celui spécifié par vous via son constructeur) (implémente SortedSet)
  • n'offre aucun paramètre de réglage pour les performances d'itération
  • propose quelques méthodes pratiques pour gérer l'ensemble ordonné comme first(), last(), headSet(), et tailSet() etc

Les points importants:

  • Les deux garantissent la collecte sans duplication des éléments
  • Il est généralement plus rapide d'ajouter des éléments au HashSet, puis de convertir la collection en TreeSet pour une traversée triée sans doublon.
  • Aucune de ces implémentations n'est synchronisée. C'est-à-dire que si plusieurs threads accèdent simultanément à un ensemble et qu'au moins l'un des threads modifie l'ensemble, il doit être synchronisé de manière externe.
  • LinkedHashSet est en quelque sorte intermédiaire entre HashSet et TreeSet. Implémenté sous forme de table de hachage avec une liste chaînée passant par lui, cependant,il fournit une itération ordonnée par insertion qui n'est pas identique à la traversée triée garantie par TreeSet.

Donc un choix d'utilisation dépend entièrement de vos besoins mais je pense que même si vous avez besoin d'une collection ordonnée, vous devriez toujours préférer HashSet pour créer l'ensemble et ensuite le convertir en TreeSet.

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

805
2017-12-16 18:59



Un avantage non encore mentionné d'un TreeSet est qu'il a une plus grande "localité", qui est un raccourci pour dire (1) si deux entrées sont à proximité dans l'ordre, un TreeSet les place les uns près des autres dans la structure de données, et donc dans la mémoire; et (2) ce placement tire parti du principe de localité, qui dit que des données similaires sont souvent accédées par une application avec une fréquence similaire.

Ceci est en contraste avec un HashSet, qui répand les entrées partout dans la mémoire, peu importe ce que leurs clés sont.

Lorsque le coût de la latence 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 sont réellement accessibles avec la localité, le TreeSet peut être un meilleur choix.


35
2017-09-30 18:28



HashSet est O (1) pour accéder aux éléments, donc c'est certainement important. Mais le maintien de l'ordre des objets dans l'ensemble n'est pas possible.

TreeSet est utile si le maintien d'une commande (en termes de valeurs et non l'ordre d'insertion) vous concerne. Mais, comme vous l'avez noté, vous êtes en train de négocier un ordre de temps plus lent pour accéder à un élément: O (log n) pour les opérations de base.

Du javadocs pour TreeSet:

Cette implémentation garantit un coût en temps log (n) garanti pour les opérations de base (add, remove et contains).


25
2017-09-23 00:13



1.HashSet permet un objet nul.

2.TreeSet n'autorisera pas d'objet nul. Si vous essayez d'ajouter une valeur nulle, une exception NullPointerException sera générée.

3.HashSet est beaucoup plus rapide que TreeSet.

par exemple.

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

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

20
2017-11-16 05:26



La raison pour laquelle la plupart utilisent HashSet 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érangé par les fonctions de hachage" comme cela a été fait pour vous. Si le jeu contient des classes personnalisées, vous devez implémenter hashCode utiliser HashSet (bien que Java efficace montre comment), mais si vous utilisez un TreeSet tu dois le faire Comparable ou fournir un Comparator. Cela peut être un problème si la classe n'a pas d'ordre particulier.

J'ai parfois utilisé TreeSet (ou en fait TreeMap) pour de très petits ensembles / cartes (<10 éléments), bien que je n’aie pas vérifié s’il y avait un réel avantage à le faire. Pour les grands ensembles, la différence peut être considérable.

Maintenant, si vous avez besoin du trié, alors TreeSet est approprié, bien qu'alors même si les mises à jour sont fréquentes et que le besoin d'un résultat trié soit peu fréquent, parfois copier le contenu dans une liste ou un tableau et les trier peut être plus rapide.


12
2017-09-23 00:27



S'appuyant sur charmant réponse visuelle sur Maps par @shevchyk voici ma prise:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashSet       ║      TreeSet      ║     LinkedHashSet   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Add/remove   ║        O(1)         ║     O(log(n))     ║        O(1)         ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableSet    ║                     ║
║  Interfaces  ║         Set         ║       Set         ║         Set         ║
║              ║                     ║    SortedSet      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║    not allowed    ║                     ║
║  Null values ║       allowed       ║ 1st element only  ║      allowed        ║
║              ║                     ║     in Java 7     ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═══════════════════════════════════════════════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

11
2018-04-12 08:18



Si vous n'insérez pas suffisamment d'éléments pour provoquer des ré-assemblages fréquents (ou des collisions, si votre HashSet ne peut pas être redimensionné), un HashSet vous donne certainement l'avantage d'un accès constant à l'heure. Cependant, en fonction de l'implémentation, vous pouvez obtenir de meilleures performances avec Treesets sur des décors avec beaucoup de croissance ou de contraction.

Le temps amorti peut être proche de O (1) avec un arbre fonctionnel rouge-noir, si ma mémoire est bonne. Le livre d'Okasaki aurait une meilleure explication que je ne pourrais en tirer. (Ou voir sa liste de publications)


10
2017-09-23 00:21



Les implémentations de HashSet sont, bien sûr, beaucoup plus rapides - moins de frais généraux car il n'y a pas de commande. Une bonne analyse des différentes implémentations de Set en Java est fournie à http://java.sun.com/docs/books/tutorial/collections/implementations/set.html.

La discussion indique également une approche «intermédiaire» intéressante de la question Tree vs Hash. Java fournit un LinkedHashSet, qui est un HashSet avec une liste chaînée "orientée insertion" qui le parcourt, c'est-à-dire que le dernier élément de la liste liée est aussi le dernier à être inséré dans le Hash. Cela vous permet d'éviter l'inexactitude d'un hachage non ordonné sans encourir le coût accru d'un TreeSet.


7
2017-09-23 00:25