Hashset vs Treeset

497

J'ai toujours aimé les arbres, c'est gentil O(n*log(n)) et la propreté d'entre eux. Cependant, chaque ingénieur logiciel que j'ai jamais connu m'a demandé pourquoi j'utiliserais a TreeSet. D'un arrière-plan CS, je ne pense pas que cela compte autant que vous utilisez, et je ne me soucie pas de jouer avec les fonctions de hachage et les compartiments (dans le cas de Java).

Dans quels cas dois-je utiliser un HashSetsur un TreeSet?

heymatthew
la source

Réponses:

861

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 commande comme TreeSet.

HashSet

  • la classe offre des performances à temps constant pour les opérations de base (ajouter, supprimer, contenir et taille).
  • il ne garantit pas que l'ordre des éléments restera constant dans le temps
  • les performances d'itération dépendent de la capacité initiale et du facteur de charge du HashSet.
    • Il est assez sûr d'accepter le facteur de charge par défaut, mais vous souhaiterez peut-être spécifier une capacité initiale d'environ deux fois la taille à laquelle vous vous attendez à ce que l'ensemble augmente.

TreeSet

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

Les points importants:

  • Les deux garantissent une collection d'éléments sans doublon
  • 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é en externe.
  • LinkedHashSet est en quelque sorte intermédiaire entre HashSetet TreeSet. Implémenté comme une table de hachage avec une liste liée qui le traverse, il fournit cependant une itération ordonnée par insertion qui n'est pas la même que la traversée triée garantie par TreeSet .

Donc, le choix de l'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 le Set puis le convertir en TreeSet.

  • par exemple SortedSet<String> s = new TreeSet<String>(hashSet);
sactiw
la source
38
C'est seulement moi qui trouve que l'affirmation "HashSet est beaucoup plus rapide que TreeSet (temps constant versus temps de connexion ...)" est tout simplement fausse? Premièrement, il s'agit de complexité temporelle, pas de temps absolu, et O (1) peut être dans de trop nombreux cas plus lent que O (f (N)). Deuxièmement, O (logN) est "presque" O (1). Je ne serais pas surpris si, dans de nombreux cas courants, un TreeSet surpassait un HashSet.
lvella
22
Je veux juste appuyer le commentaire d'Ivella. la complexité temporelle n'est PAS la même chose que le temps d'exécution, et O (1) n'est pas toujours meilleur que O (2 ^ n). Un exemple pervers illustre le point: considérons un ensemble de hachage utilisant un algorithme de hachage qui a pris 1 billion d'instructions machine à exécuter (O (1)) par rapport à toute implémentation courante du tri à bulles (O (N ^ 2) moy / pire) pour 10 éléments . Le tri à bulles gagnera à chaque fois. Le fait est que les classes d'algorithmes apprennent à tout le monde à réfléchir aux approximations utilisant la complexité temporelle, mais dans le monde réel, les facteurs constants importent fréquemment.
Peter Oehlert
17
Peut-être que c'est juste moi, mais le conseil n'est-il pas d'abord de tout ajouter à un hachage, puis de le convertir en un ensemble d'arbres horrible? 1) L'insertion dans un hashset n'est rapide que si vous connaissez à l'avance la taille de votre jeu de données, sinon vous payez un re-hachage O (n), éventuellement plusieurs fois. et 2) Vous payez pour l'insertion TreeSet de toute façon lors de la conversion de l'ensemble. (avec vengeance, car l'itération à travers un hachage n'est pas terriblement efficace)
TinkerTank
5
Ce conseil est basé sur le fait que pour un ensemble, vous devez vérifier si un élément est un doublon avant de l'ajouter; vous gagnerez donc du temps en éliminant les doublons si vous utilisez un hachage sur un arbre. Cependant, compte tenu du prix à payer pour créer un deuxième ensemble pour les non-doublons, le pourcentage de doublons devrait être vraiment excellent pour surmonter ce prix et en faire un gain de temps. Et bien sûr, c'est pour les ensembles moyens et grands car pour un petit ensemble, l'arbre est peut-être plus rapide qu'un hachage.
SylvainL
5
@PeterOehlert: veuillez fournir une référence pour cela. Je comprends votre point, mais la différence entre les deux ensembles n'a guère d'importance avec les petites tailles de collection. Et dès que l'ensemble grandit au point où l'implémentation est importante, log (n) devient un problème. En général, les fonctions de hachage (même complexes) sont plus rapides que plusieurs échecs de cache (que vous avez sur d'énormes arbres pour presque tous les niveaux auxquels vous accédez) pour trouver / accéder / ajouter / modifier la feuille. C'est du moins mon expérience avec ces deux ensembles en Java.
Bouncner
38

Un avantage non encore mentionné de a TreeSetest qu'il a une "localité" plus grande, ce qui est un raccourci pour dire (1) si deux entrées sont proches dans l'ordre, a les TreeSetplace près l'une de l'autre dans la structure de données, et donc dans la mémoire; et (2) ce placement profite du principe de localité, qui dit que des données similaires sont souvent accessibles par une application avec une fréquence similaire.

Ceci contraste avec a HashSet, qui répartit les entrées dans toute la mémoire, quelles que soient leurs clés.

Lorsque le coût de latence de la lecture à partir d'un disque dur est des milliers de fois supérieur à celui de la lecture depuis le cache ou la RAM, et lorsque les données sont réellement accessibles avec la localité, le TreeSetpeut être un bien meilleur choix.

Carl Andersen
la source
3
Pouvez-vous démontrer que si deux entrées sont proches dans l'ordre, un TreeSet les place près l'une de l'autre dans la structure de données, et donc en mémoire ?
David Soroko
6
Tout à fait hors de propos pour Java. Les éléments de l'ensemble sont des objets de toute façon et pointent ailleurs, donc vous n'enregistrez pas grand-chose.
Andrew Gallasch
Outre les autres commentaires faits sur le manque de localité en Java en général, l'implémentation d'OpenJDK de TreeSet/ TreeMapn'est pas optimisée pour la localité. Bien qu'il soit possible d'utiliser un arbre b d'ordre 4 pour représenter un arbre rouge-noir et ainsi améliorer les performances de localisation et de cache, ce n'est pas ainsi que l'implémentation fonctionne. Au lieu de cela, chaque nœud stocke un pointeur sur sa propre clé, sa propre valeur, son parent et ses nœuds enfants gauche et droit, évident dans le code source JDK 8 pour TreeMap.Entry .
kbolino
25

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

TreeSetest utile si le maintien d'un ordre (en termes de valeurs et non d'ordre d'insertion) vous importe. Mais, comme vous l'avez noté, vous échangez un ordre plus lentement pour accéder à un élément: O (log n) pour les opérations de base.

Des javadocs pourTreeSet :

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

duffymo
la source
22

1.HashSet autorise un objet nul.

2.TreeSet n'autorisera pas d'objet nul. Si vous essayez d'ajouter une valeur nulle, cela lèvera une exception NullPointerException.

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
SuReN
la source
3
ts.add (null) cela fonctionnera bien dans le cas de TreeSet si null est ajouté comme premier objet dans TreeSet. Et tout objet ajouté après cela donnera NullPointerException dans la méthode compareTo du comparateur.
Shoaib Chikate
2
Vous ne devriez vraiment vraiment pas ajouter nullà votre jeu de toute façon.
moelleux
TreeSet<String> badassTreeSet = new TreeSet<String>(new Comparator<String>() { public int compare(String string1, String string2) { if (string1 == null) { return (string2 == null) ? 0 : -1; } else if (string2 == null) { return 1; } else { return string1.compareTo(string2); } } }); badassTreeSet.add("tree"); badassTreeSet.add("asdf"); badassTreeSet.add(null); badassTreeSet.add(null); badassTreeSet.add("set"); badassTreeSet.add("tree"); System.out.println(badassTreeSet);
Dávid Horváth
21

Sur la base d'une belle réponse visuelle sur Maps by @shevchyk, voici mon point de vue:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
   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               
╚══════════════╩═══════════════════════════════════════════════════════════════╝
kiedysktos
la source
13

La raison pour laquelle la plupart des utilisateurs HashSetest que les opérations sont (en moyenne) O (1) au lieu de O (log n). Si l'ensemble contient des éléments standard, vous ne "vous amuserez pas avec les fonctions de hachage" comme cela a été fait pour vous. Si l'ensemble contient des classes personnalisées, vous devez implémenter hashCodepour utiliser HashSet(bien que Java efficace montre comment), mais si vous utilisez un, TreeSetvous devez le faire Comparableou 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) de très petits ensembles / cartes (<10 éléments) bien que je n'ai pas vérifié pour voir s'il y avait un réel gain à le faire. Pour les grands ensembles, la différence peut être considérable.

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

Kathy Van Stone
la source
tous les points de données sur ces gros éléments tels que 10K ou plus
kuhajeyan
11

Si vous n'insérez pas suffisamment d'éléments pour entraîner des reprises fréquentes (ou des collisions, si votre HashSet ne peut pas être redimensionné), un HashSet vous offre certainement l'avantage d'un accès constant. Mais sur des ensembles avec beaucoup de croissance ou de rétrécissement, vous pouvez réellement obtenir de meilleures performances avec les arbres, en fonction de l'implémentation.

Le temps amorti peut être proche de O (1) avec un arbre rouge-noir fonctionnel, si la mémoire me sert. Le livre d'Okasaki aurait une meilleure explication que moi. (Ou voir sa liste de publications )

JasonTrue
la source
7

Les implémentations 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 y montre également une approche intéressante de «terrain d'entente» à la question Tree vs Hash. Java fournit un LinkedHashSet, qui est un HashSet avec une liste liée "orientée insertion" qui le traverse, c'est-à-dire que le dernier élément de la liste liée est également le plus récemment inséré dans le Hash. Cela vous permet d'éviter l'imprudence d'un hachage non ordonné sans encourir le coût accru d'un TreeSet.

Joseph Weissman
la source
4

Le TreeSet est l' une des deux collections (l'autre triées étant TreeMap). Il utilise une structure arborescente Rouge-Noir (mais vous le saviez), et garantit que les éléments seront en ordre croissant, selon l'ordre naturel. Facultativement, vous pouvez construire un TreeSet avec un constructeur qui vous permet de donner à la collection vos propres règles pour ce que l'ordre devrait être (plutôt que de compter sur l'ordre défini par la classe des éléments) en utilisant un Comparable ou un Comparateur

et Un LinkedHashSet est une version ordonnée de HashSet qui maintient une liste doublement liée à travers tous les éléments. Utilisez cette classe au lieu de HashSet lorsque vous vous souciez de l'ordre d'itération. Lorsque vous parcourez un HashSet, l'ordre est imprévisible, tandis qu'un LinkedHashSet vous permet de parcourir les éléments dans l'ordre dans lequel ils ont été insérés

subhash laghate
la source
3

De nombreuses réponses ont été apportées, basées sur des considérations techniques, notamment en matière de performances. Selon moi, le choix entre TreeSetet HashSetimporte.

Mais je dirais plutôt que le choix doit d'abord être motivé par des considérations conceptuelles .

Si, pour les objets dont vous avez besoin de manipuler, un ordre naturel n'a pas de sens, alors ne l'utilisez pas TreeSet.
Il s'agit d'un ensemble trié, car il implémente SortedSet. Cela signifie donc que vous devez remplacer la fonction compareTo, qui doit être cohérente avec ce qui retourne la fonction equals. Par exemple, si vous avez un ensemble d'objets d'une classe appelée Student, alors je ne pense pas qu'unTreeSet aurait du sens, car il n'y a pas d'ordre naturel entre les élèves. Vous pouvez les commander par leur note moyenne, d'accord, mais ce n'est pas un "ordre naturel". Une fonctioncompareTo retournerait 0 non seulement lorsque deux objets représentent le même élève, mais aussi lorsque deux élèves différents ont la même note. Pour le deuxième cas, equalsretournerait faux (à moins que vous ne décidiez de rendre vrai ce dernier lorsque deux élèves différents ont la même note, ce qui donnerait à la equalsfonction un sens trompeur, pour ne pas dire un mauvais sens.)
Veuillez noter cette cohérence entre equalset compareToest facultatif, mais fortement recommandé. Sinon, le contrat d'interface Setest rompu, ce qui rend votre code trompeur pour d'autres personnes, ce qui peut également entraîner un comportement inattendu.

Ce lien pourrait être une bonne source d'informations concernant cette question.

Marek Stanley
la source
3

Pourquoi avoir des pommes quand on peut avoir des oranges?

Sérieusement les gars et les filles - si votre collection est grande, lue et écrite à des millions de fois, et que vous payez pour des cycles CPU, le choix de la collection est pertinent UNIQUEMENT si vous en avez BESOIN pour mieux fonctionner. Cependant, dans la plupart des cas, cela n'a pas vraiment d'importance - quelques millisecondes ici et là passent inaperçus en termes humains. Si cela comptait vraiment autant, pourquoi n'écrivez-vous pas de code en assembleur ou en C? [déclencher une autre discussion]. Donc, le fait est que si vous êtes heureux d'utiliser la collection que vous avez choisie, et cela résout votre problème [même si ce n'est pas spécifiquement le meilleur type de collection pour la tâche], assommez-vous. Le logiciel est malléable. Optimisez votre code si nécessaire. L'oncle Bob dit que l'optimisation prématurée est la racine de tout mal. Oncle Bob le dit

user924272
la source
1

Modification du message ( réécriture complète ) Lorsque la commande n'a pas d'importance, c'est quand. Les deux devraient donner Log (n) - il serait utile de voir si l'un est plus de cinq pour cent plus rapide que l'autre. HashSet peut donner O (1) des tests dans une boucle devraient révéler si c'est le cas.

Nicholas Jordan
la source
-3
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}
gli00001
la source
1
Le message a déclaré qu'il est généralement plus rapide d'ajouter des éléments au HashSet, puis de convertir la collection en un TreeSet pour une traversée triée sans doublon. Set <String> s = new TreeSet <String> (hashSet); Je me demande pourquoi ne pas définir directement <String> s = new TreeSet <String> () si nous savons qu'il sera utilisé pour une itération triée, j'ai donc fait cette comparaison et le résultat a montré qui est plus rapide.
gli00001
"Dans quels cas voudrais-je utiliser un HashSet sur un TreeSet?"
Austin Henley
1
mon point est, si vous avez besoin de commander, utiliser TreeSet seul est mieux que de tout mettre dans HashSet puis de créer un TreeSet basé sur ce HashSet. Je ne vois pas du tout la valeur de HashSet + TreeSet dans le message d'origine.
gli00001
@ gli00001: vous avez raté le point. Si vous n'avez pas toujours besoin de trier votre ensemble d'éléments, mais que vous allez le manipuler assez souvent, cela vaudra la peine que vous utilisiez un hachage pour bénéficier la plupart du temps des opérations les plus rapides. Pour les moments occasionnels où vous devez traiter les éléments dans l'ordre, enveloppez-les simplement avec un arbre. Cela dépend de votre cas d'utilisation, mais ce n'est pas vraiment un cas d'utilisation inhabituel (et cela suppose probablement un ensemble qui ne contient pas trop d'éléments et avec des règles de classement complexes).
haylem