HashSet vs LinkedHashSet

153

Was ist der Unterschied zwischen ihnen? ich weiß das

Ein LinkedHashSet ist eine geordnete Version von HashSet, die eine doppelt verknüpfte Liste über alle Elemente hinweg verwaltet. Verwenden Sie diese Klasse anstelle von HashSet, wenn Sie sich für die Iterationsreihenfolge interessieren. Wenn Sie ein HashSet durchlaufen, ist die Reihenfolge nicht vorhersehbar, während Sie mit einem LinkedHashSet die Elemente in der Reihenfolge durchlaufen können, in der sie eingefügt wurden.

Im Quellcode von LinkedHashSet gibt es jedoch nur aufrufende Konstruktoren von HashSet. Wo ist also die doppelt verknüpfte Liste und die Einfügereihenfolge?

Shikarn-O
quelle
2
Verwenden Sie die Option Intellij (Strg + B), um die Antwort zu finden. :)
Delta
Natürlich müssen Sie den Quellcode anhängen. :)
Delta

Antworten:

65

Die Antwort liegt in dem Konstruktoren die LinkedHashSetverwendet die Basisklasse zu konstruieren:

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

Und (ein Beispiel für) einen HashSetKonstruktor, der ein boolesches Argument verwendet, wird beschrieben und sieht folgendermaßen aus:

/**
 * 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
quelle
2
Eine übergeordnete Klasse mit expliziter Funktionalität für eine
untergeordnete
5
Nicht gerade ein sauberes Design, das einen Dummy-Parameter für die Disambiguierung von Konstruktoren verwendet.
Eric J.
7
Das Design ist relativ sauber, da die API sauber ist (dieser HashSet-Konstruktor ist paketprivat). Die Implementierungsdetails spielen für die Benutzer der Klasse keine Rolle. Die Pflege dieses Codes könnte schwieriger sein, aber im Fall von java.util-Klassen können dies bereits durch sehr kleine Leistungsverbesserungen gerechtfertigt sein.
lbalazscs
25

LinkedHashSetDie Konstruktoren von 'rufen den folgenden Basisklassenkonstruktor auf:

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

Wie Sie sehen können, ist die interne Karte a LinkedHashMap. Wenn Sie nach innen schauen LinkedHashMap, werden Sie das folgende Feld entdecken:

private transient Entry<K, V> header;

Dies ist die betreffende verknüpfte Liste.

NPE
quelle
24

HashSet ist ungeordnet und unsortiert Set.
LinkedHashSet ist die bestellte Version von HashSet.

Der einzige Unterschied zwischen HashSet und LinkedHashSet besteht darin, dass:
LinkedHashSet die Einfügereihenfolge beibehält.

Wenn wir ein HashSet durchlaufen , ist die Reihenfolge unvorhersehbar, während sie im Fall von LinkedHashSet vorhersehbar ist .

Der Grund dafür, wie LinkedHashSet die Einfügereihenfolge beibehält, ist folgender:
Die zugrunde liegende verwendete Datenstruktur ist Double-Linked-List .

Hema Ganapathy
quelle
9

Sie sollten sich die Quelle des HashSetKonstruktors ansehen, den es aufruft ... es ist ein spezieller Konstruktor, der die Sicherung zu Mapeinem LinkedHashMapstatt nur zu einem macht HashMap.

ColinD
quelle
Danke, in HashSet gibt es einen Konstruktor zum Erstellen von LinkedHashMap, der in LinkedHashSet aufgerufen wird und dessen gesamte Logik sich in LinkedHashMap befindet
Shikarn-O
5

Ich schlage vor , Sie verwenden die LinkedHashSetmeiste Zeit, weil es insgesamt eine bessere Leistung ):

  1. Vorhersagbaren Iteration um LinkedHashSet (Oracle)
  2. LinkedHashSet ist für Einfügungen teurer als HashSet;
  3. Im Allgemeinen etwas bessere Leistung als HashMap, da wir die meiste Zeit Set-Strukturen zum Iterieren verwenden.

Leistungstests:

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

Sie können die Quelltestseite hier sehen: Das endgültige Beispiel für Leistungstests

Dmytro Melnychuk
quelle
2
Ich sehe keine Erwärmung der JVM vor diesen "Benchmarks", daher würde ich keine dieser Daten ernst nehmen. Lesen Sie mehr
Felix S
3

HashSet: Eigentlich ungeordnet. Wenn Sie den Parameter übergeben, bedeutet dies

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

Ausgabe: Kann 2,1,3nicht vorhersehbar sein. nächstes Mal eine andere Bestellung.

LinkedHashSet() die FIFO-Ordnung erzeugen.

Justin
quelle
3

HashSet Sie halten nicht die Reihenfolge der Einfügungen Artikel
LinkedHashSet halten die Reihenfolge der Einfügungen Artikel

Beispiel

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 Ausgabe

1
ab
2

LinkedHashSet Ausgabe

2
1
ab
Phan Van Linh
quelle
2

HashSet:

Die unterstrichene Datenstruktur ist Hashtable. Doppelte Objekte sind nicht zulässig. Die Einfügereihenfolge wird nicht beibehalten und basiert auf dem Hash-Code von Objekten. Das Einfügen von Null ist möglich (nur einmal). Es implementiert die Schnittstelle Serializable, Clonable, aber nicht RandomAccess. HashSet ist die beste Wahl, wenn es sich bei der häufigen Operation um eine Suchoperation handelt.

In HashSet sind Duplikate nicht zulässig. Wenn Benutzer versuchen, Duplikate einzufügen, wenn keine Kompilierungs- oder Laufzeitausnahmen auftreten. Die Methode add gibt einfach false zurück.

Konstruktoren:

HashSet h = neues HashSet (); Erstellt ein leeres HashSet-Objekt mit der Standard-Anfangskapazität 16 und einem Standard-Füllverhältnis (Lastfaktor) von 0,75.

HashSet h = neues HashSet (int initialCapacity); Erstellt ein leeres HashSet-Objekt mit der angegebenen initialCapacity und der Standardfüllrate ist 0,75.

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

HashSet h = neues HashSet (Sammlung c); Erstellt ein äquivalentes HashSet-Objekt für die angegebene Sammlung. Dieser Konstruktor ist für die Konvertierung zwischen Sammlungsobjekten vorgesehen.

LinkedHashSet:

Es ist eine untergeordnete Klasse von HashSet. Es ist genau das gleiche wie HashSet einschließlich (Konstruktoren und Methoden), mit Ausnahme der folgenden Unterschiede.

Unterschiede HashSet:

  1. Die unterstrichene Datenstruktur ist Hashtable.
  2. Die Einfügereihenfolge bleibt nicht erhalten.
  3. Version 1.2 eingeführt.

LinkedHashSet:

  1. Die unterstrichene Datenstruktur ist eine Kombination aus LinkedList und Hashtable.
  2. Die Einfügereihenfolge bleibt erhalten.
  3. Eingeführt in Version 1.4.
Umapathi
quelle
1

Wenn Sie sich die Konstruktoren ansehen, die von der LinkedHashSetKlasse aufgerufen werden, werden Sie feststellen, dass sie intern LinkedHashMapzu Sicherungszwecken verwendet werden.

Riff
quelle
0

Alle Methoden und Konstruktoren sind gleich, aber nur ein Unterschied besteht darin, dass LinkedHashset die Einfügereihenfolge beibehält, jedoch keine Duplikate zulässt.

Hashset behält keine Einfügereihenfolge bei. Es ist eine Kombination aus List und Set simple :)

Anand Mohan
quelle