HashSet vs LinkedHashSet

153

Quelle est la différence entre eux? je le sais

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.

Mais dans le code source de LinkedHashSet, il n'y a que des constructeurs appelants de HashSet. Alors, où sont la liste à double lien et l'ordre d'insertion?

Shikarn-O
la source
2
utilisez l'option Intellij (Ctrl + B) pour retrouver la réponse. :)
Delta
bien sûr, vous avez besoin du code source joint. :)
Delta

Réponses:

65

La réponse se trouve dans ce qui constructeurs les LinkedHashSetusages pour construire la classe de base:

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);      // <-- boolean dummy argument
}

...

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);            // <-- boolean dummy argument
}

...

public LinkedHashSet() {
    super(16, .75f, true);                         // <-- boolean dummy argument
}

...

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);   // <-- boolean dummy argument
    addAll(c);
}

Et (un exemple de) un HashSetconstructeur qui prend un argument booléen est décrit et ressemble à ceci:

/**
 * Constructs a new, empty linked hash set.  (This package private
 * constructor is only used by LinkedHashSet.) The backing
 * HashMap instance is a LinkedHashMap with the specified initial
 * capacity and the specified load factor.
 *
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @param      dummy             ignored (distinguishes this
 *             constructor from other int, float constructor.)
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
aioobe
la source
2
Une classe parent ayant des fonctionnalités explicitement pour une classe enfant, un argument ignoré pour distinguer
Traubenfuchs
5
Pas exactement une conception propre utilisant un paramètre factice pour la désambiguïsation du constructeur.
Eric J.
8
C'est une conception raisonnablement propre, car l'API est propre (ce constructeur HashSet est un package privé). Les détails d'implémentation n'ont pas d'importance pour les utilisateurs de la classe. La maintenance de ce code pourrait être plus difficile, mais dans le cas des classes java.util, même de très petites améliorations de performances peuvent le justifier.
lbalazscs
25

LinkedHashSetLes constructeurs de invoquent le constructeur de classe de base suivant:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  map = new LinkedHashMap<E, Object>(initialCapacity, loadFactor);
}

Comme vous pouvez le voir, la carte interne est un fichier LinkedHashMap. Si vous regardez à l'intérieur LinkedHashMap, vous découvrirez le champ suivant:

private transient Entry<K, V> header;

Il s'agit de la liste chaînée en question.

NPE
la source
24

HashSet est un ensemble non ordonné et non trié .
LinkedHashSet est la version commandée de HashSet.

La seule différence entre HashSet et LinkedHashSet est que:
LinkedHashSet gère l'ordre d'insertion.

Lorsque nous parcourons un HashSet , l'ordre est imprévisible alors qu'il est prévisible dans le cas de LinkedHashSet .

La raison pour laquelle LinkedHashSet maintient l'ordre d'insertion est la suivante:
La structure de données utilisée sous-jacente est Double-Linked-List .

Hema Ganapathy
la source
9

Vous devriez regarder la source du HashSetconstructeur qu'il appelle ... c'est un constructeur spécial qui fait du support Mapun LinkedHashMapau lieu de juste un HashMap.

ColinD
la source
Merci, dans HashSet, il existe un constructeur pour créer LinkedHashMap, qui est appelé dans LinkedHashSet et toute la logique est dans LinkedHashMap
Shikarn-O
5

Je vous suggère d'utiliser la LinkedHashSetplupart du temps, car il a globalement de meilleures performances ):

  1. Ordre d' itération prévisible LinkedHashSet (Oracle)
  2. LinkedHashSet est plus cher pour les insertions que HashSet;
  3. En général, des performances légèrement meilleures que HashMap, car la plupart du temps, nous utilisons des structures Set pour les itérations.

Des tests de performance:

------------- TreeSet -------------
 size       add  contains   iterate
   10       746       173        89
  100       501       264        68
 1000       714       410        69
10000      1975       552        69
------------- HashSet -------------
 size       add  contains   iterate
   10       308        91        94
  100       178        75        73
 1000       216       110        72
10000       711       215       100
---------- LinkedHashSet ----------
 size       add  contains   iterate
   10       350        65        83
  100       270        74        55
 1000       303       111        54
10000      1615       256        58

Vous pouvez voir la page de test source ici: L'exemple final de test de performance

Dmytro Melnychuk
la source
2
Je ne vois aucun réchauffement de la JVM avant ces "benchmarks", donc je ne prendrais aucune de ces données au sérieux. Lire la suite
Felix S
3

HashSet: Non ordonné en fait. si u passant le paramètre signifie

Set<Integer> set=new HashSet<Integer>();
for(int i=0;i<set.length;i++)
{
  SOP(set)`enter code here`
}

Out Put: Peut-être 2,1,3pas prévisible. la prochaine fois une autre commande.

LinkedHashSet() qui produisent l'ordre FIFO.

Justin
la source
3

HashSet ne pas conserver l'ordre de l'élément d'insertion
LinkedHashSet maintenir l'ordre de l'élément d'insertion

Exemple

Set<String> set = ...;// using new HashSet<>() OR new LinkedHashSet<>()
set.add("2");
set.add("1");
set.add("ab");
for(String value : set){
   System.out.println(value);
}  

HashSet production

1
ab
2

LinkedHashSet production

2
1
ab
Phan Van Linh
la source
2

HashSet:

La structure de données soulignée est Hashtable. Les objets en double ne sont pas autorisés.L'ordre d'insertion n'est pas conservé et il est basé sur le code de hachage des objets. Une insertion nulle est possible (une seule fois). Il implémente l'interface Serializable, Clonable mais pas RandomAccess. HashSet est le meilleur choix si une opération fréquente est une opération de recherche.

Dans HashSet, les doublons ne sont pas autorisés.Si les utilisateurs essaient d'insérer des doublons alors que nous n'obtiendrons aucune exception de compilation ou d'exécution. La méthode add renvoie simplement false.

Constructeurs:

HashSet h = nouveau HashSet (); crée un objet HashSet vide avec une capacité initiale par défaut de 16 et un taux de remplissage par défaut (facteur de charge) de 0,75.

HashSet h = nouveau HashSet (int initialCapacity); crée un objet HashSet vide avec initialCapacity spécifié et le taux de remplissage par défaut est de 0,75.

HashSet h = new HashSet (int initialCapacity, float fillRatio);

HashSet h = nouveau HashSet (Collection c); crée un objet HashSet équivalent pour la collection donnée. Ce constructeur était destiné à la conversion inter-objet de collection.

LinkedHashSet:

C'est une classe enfant de HashSet. c'est exactement la même chose que HashSet, y compris (Constructeurs et Méthodes) à l'exception des différences suivantes.

Différences HashSet:

  1. La structure de données soulignée est Hashtable.
  2. L'ordre d'insertion n'est pas conservé.
  3. introduit la version 1.2.

LinkedHashSet:

  1. La structure de données soulignée est une combinaison de LinkedList et Hashtable.
  2. L'ordre d'insertion est conservé.
  3. Produit en version 1.4.
Umapathi
la source
1

Si vous regardez les constructeurs appelés à partir de la LinkedHashSetclasse, vous verrez qu'en interne c'est un LinkedHashMapqui est utilisé à des fins de sauvegarde.

récif
la source
0

Toutes les méthodes et tous les constructeurs sont identiques, mais une seule différence est que LinkedHashset conservera l'ordre d'insertion mais n'autorisera pas les doublons.

Hashset ne conservera aucun ordre d'insertion. C'est une combinaison de List et Set simple :)

Anand Mohan
la source