Hashset vs Treeset

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?

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

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.

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

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

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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

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.

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 )

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.

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

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.

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

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.

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