Hashset vs Treeset

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

ceci contraste avec un HashSet , qui il répand les entrées dans toute la mémoire, peu importe leurs clés.

quand le coût de latence de la lecture d'un disque dur est des milliers de fois le coût de la lecture à partir de la mémoire cache ou RAM, et quand les données sont réellement accessibles avec la localité, le TreeSet peut être un bien meilleur choix.

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

TreeSet est 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 l'ordre pour un temps plus lent pour accéder à un élément: O (log n) pour les opérations de base.

De la javadoc TreeSet :

cette implémentation fournit un log(n) Temps garanti pour les opérations de base ( add , remove et contains ).

1.HashSet permet l'objet null.

2.TreeSet n'autorise pas l'objet null. Si vous essayez d'ajouter une valeur nulle, cela lancera une NullPointerException.

3.HashSet est beaucoup plus rapide que TreeSet.

p.ex.

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

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

basé sur la belle réponse visuelle sur les cartes de @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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

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 l'ensemble contient des éléments standards, vous ne serez pas" jouer avec des fonctions de hachage " comme cela a été fait pour vous. Si L'ensemble contient des classes personnalisées, vous devez implémenter hashCode pour utiliser HashSet (bien que Java efficace montre comment), mais si vous utilisez un TreeSet vous devez le faire Comparable ou fournir un Comparator . Cela peut être un problème si la classe n'ont 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'ai pas vérifié pour voir s'il y a un réel gain à 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 que même alors si les mises à jour sont fréquentes et la nécessité d'un résultat trié est rare, parfois la copie de la contenu à une liste ou un tableau d'un classement peut être plus rapide.

si vous n'insérez pas assez d'éléments pour donner lieu à de fréquentes reprises (ou collisions, si votre HashSet ne peut pas redimensionner), un HashSet vous donne certainement l'avantage d'un accès à temps constant. Mais sur les 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.

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 un meilleur une explication que je ne peux tirer. (Ou voir sa liste de publication )

HashSet implémentations sont, bien sûr, beaucoup plus rapide -- moins de frais généraux parce qu'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 à cet endroit met aussi en évidence une approche "intermédiaire" intéressante de la question de L'arbre par rapport à celle du hachage. Java fournit un HashSet linked, qui est un HashSet avec un la liste liée "orientée vers l'insertion" qui la traverse, c'est-à-dire le dernier élément de la liste liée est aussi le plus récemment inséré dans le hachage. Cela vous permet d'éviter l'incongruité d'un hachage non ordonné sans encourir le coût accru d'un arbre.

la TreeSet est l'une des deux collections triées (l'autre étant TreeMap). Il utilise une structure d'arbre rouge-noir (mais vous le saviez), et garantit que les éléments seront en ordre ascendant, selon l'ordre naturel. Éventuellement, vous pouvez construire un arbre avec un constructeur qui vous permet de donner à la collection votre règles propres pour ce que la commande 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 commandée de HashSet qui maintient une liste à double lien pour tous les éléments. Utilisez cette classe au lieu de HashSet quand vous vous souciez de l'itération de l'ordre. Lorsque vous itérez à travers un HashSet le l'ordre est imprévisible, alors Qu'un LinkedHashSet vous permet d'itérer à travers les éléments dans l'ordre où ils ont été insérés

beaucoup de réponses ont été données, basées sur des considérations techniques, en particulier autour de la performance. Selon moi, le choix entre TreeSet et HashSet importe.



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



Si, pour les objets de votre besoin de manipuler, d'un naturel commander n'a pas de sens, alors n'utilisez pas TreeSet .

C'est un ensemble trié, puisqu'il implémente SortedSet . Cela signifie donc que vous devez annuler la fonction compareTo , qui devrait être compatible avec ce qui retourne la fonction equals . Par exemple, si vous disposez d'un ensemble d'objets d'une classe appelée Étudiant, je ne pense pas qu'un TreeSet aurait du sens, puisque il n'y a pas d'ordre naturel entre les élèves. Vous pouvez les commander par leur moyenne, d'accord, mais ce n'est pas un "ordre naturel". La fonction compareTo renvoie 0 lorsque deux objets représentent le même élève, mais aussi lorsque deux étudiants de la même catégorie. Dans le second cas, equals retournerait faux (à moins que vous ne décidiez de rendre ce dernier vrai lorsque deux élèves différents ont la même note, ce qui ferait que la fonction equals aurait un sens trompeur, pour ne pas dire un sens erroné.)

Veuillez noter que cette cohérence entre equals et compareTo est facultatif, mais fortement recommandé. Sinon, le contrat d'interface Set est rompu, ce qui rend votre code trompeur pour d'autres personnes, ce qui peut aussi conduire à un comportement inattendu.

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

Pourquoi avoir des pommes alors que vous pouvez avoir des oranges?

sérieusement les gars et les filles - si votre collection est grande, lire et écrit à des millions de fois, et vous payez pour les cycles CPU, alors le choix de la collection n'est pertinent que si vous en avez besoin pour mieux performer. Cependant, dans la plupart des cas, cela n'a pas vraiment d'importance, quelques millisecondes ici et là passé inaperçu en termes humains. Si ça comptait tant que ça, Pourquoi tu n'écris pas de code en assembleur ou en C? [lancer une autre discussion]. Donc, le point est si vous êtes heureux en utilisant la collection que vous avez choisi, et il résout votre problème [même si ce n'est pas spécifiquement le meilleur type de collecte pour la tâche] assommez-vous. Le logiciel est malléable. Optimisez votre code si nécessaire. Oncle Bob dit que L'Optimisation prématurée est la racine de tout le mal. oncle Bob le dit

d'Édition de Message ( réécriture complète ) Lorsque l'ordre 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) essai en boucle devrait révéler si elle est.

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