HashSet vs LinkedHashSet

153

Jaka jest różnica między nimi? wiem to

LinkedHashSet to uporządkowana wersja HashSet, która utrzymuje podwójnie połączoną listę wszystkich elementów. Użyj tej klasy zamiast HashSet, jeśli zależy Ci na kolejności iteracji. Podczas iteracji przez HashSet kolejność jest nieprzewidywalna, podczas gdy LinkedHashSet umożliwia iterację elementów w kolejności, w jakiej zostały wstawione.

Ale w kodzie źródłowym LinkedHashSet są tylko wywołujące konstruktory HashSet. Więc gdzie jest podwójnie połączona lista i zamówienie reklamowe?

Shikarn-O
źródło
2
użyj opcji Intellij (Ctrl + B), aby znaleźć odpowiedź. :)
Delta
oczywiście potrzebujesz załączonego kodu źródłowego. :)
Delta

Odpowiedzi:

65

Odpowiedź tkwi w których konstruktorzy z LinkedHashSetzastosowania do skonstruowania klasy podstawowej:

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

I (jeden przykład) HashSetkonstruktora, który przyjmuje argument logiczny, jest opisany i wygląda następująco:

/**
 * 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
źródło
2
Klasa nadrzędna, która ma funkcjonalność wyraźnie dla klasy podrzędnej, ignorowany argument do rozróżnienia
Traubenfuchs
5
Niezupełnie czysty projekt przy użyciu fikcyjnego parametru do ujednoznacznienia konstruktora.
Eric J.
8
Jest to dość czysty projekt, ponieważ interfejs API jest czysty (ten konstruktor HashSet jest prywatnym pakietem). Szczegóły implementacji nie mają znaczenia dla użytkowników klasy. Utrzymanie tego kodu może być trudniejsze, ale w przypadku klas java.util nawet bardzo małe ulepszenia wydajności mogą to uzasadniać.
lbalazscs
25

LinkedHashSetKonstruktory wywołują następujący konstruktor klasy bazowej:

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

Jak widać, wewnętrzna mapa to plik LinkedHashMap. Jeśli zajrzysz do środka LinkedHashMap, odkryjesz następujące pole:

private transient Entry<K, V> header;

To jest odnośna lista.

NPE
źródło
24

HashSet jest nieuporządkowany i nieposortowany .
LinkedHashSet to zamówiona wersja HashSet.

Jedyna różnica między HashSet i LinkedHashSet jest taka, że:
LinkedHashSet utrzymuje kolejność .

Kiedy iterujemy przez HashSet , kolejność jest nieprzewidywalna, podczas gdy jest przewidywalna w przypadku LinkedHashSet .

Powód, dla którego LinkedHashSet utrzymuje kolejność wstawiania, jest następujący:
Podstawową strukturą danych jest lista podwójnie połączona .

Hema Ganapathy
źródło
9

Należy spojrzeć na źródła HashSetkonstruktora wywołuje ... jest specjalny konstruktor, który sprawia, że podkład zamiast po prostu .MapLinkedHashMapHashMap

ColinD
źródło
Dzięki, w HashSet jest konstruktor do tworzenia LinkedHashMap, który nazywa się w LinkedHashSet, a cała logika jest w LinkedHashMap
Shikarn-O
5

Proponuję używać przez LinkedHashSetwiększość czasu, ponieważ ogólnie ma lepszą wydajność ):

  1. Przewidywalna kolejność iteracji LinkedHashSet (Oracle)
  2. LinkedHashSet jest droższy w przypadku wstawiania niż HashSet;
  3. Ogólnie wydajność jest nieco lepsza niż HashMap, ponieważ przez większość czasu używamy struktur Set do iteracji.

Testy wydajności:

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

Możesz zobaczyć źródłową stronę testową tutaj: Przykład końcowego testu wydajności

Dmytro Melnychuk
źródło
2
Nie widzę żadnego rozgrzania JVM przed tymi „testami porównawczymi”, więc nie traktowałbym poważnie żadnych z tych danych. Czytaj więcej
Felix S
3

HashSet: właściwie Unordered. jeśli przekazanie parametru oznacza

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

Out Put: może być 2,1,3nieprzewidywalne. następnym razem kolejne zamówienie.

LinkedHashSet() które produkują Zamówienie FIFO.

Justin
źródło
3

HashSet nie utrzymuj kolejności obsługi elementu
LinkedHashSet reklamowego kolejność elementów reklamowych

Przykład

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 wynik

1
ab
2

LinkedHashSet wynik

2
1
ab
Phan Van Linh
źródło
2

HashSet:

Podkreślona struktura danych jest Hashtable. Duplikaty obiektów nie są dozwolone. Kolejność wstawiania nie jest zachowywana i jest oparta na kodzie skrótu obiektów. Możliwe jest wstawienie zerowe (tylko raz). Implementuje interfejs Serializable, Clonable, ale nie RandomAccess. HashSet najlepiej wybrać, jeśli częstą operacją jest operacja wyszukiwania.

W HashSet duplikaty są niedozwolone. Jeśli użytkownicy próbują wstawić duplikaty, gdy nie otrzymamy żadnych wyjątków kompilacji ani czasu wykonania. metoda add zwraca po prostu fałsz.

Konstruktorzy:

HashSet h = new HashSet (); tworzy pusty obiekt HashSet z domyślną pojemnością początkową 16 i domyślnym współczynnikiem wypełnienia (współczynnik obciążenia) 0,75.

HashSet h = new HashSet (int initialCapacity); tworzy pusty obiekt HashSet z określoną wartością initialCapacity i domyślną dawką wypełnienia 0,75.

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

HashSet h = new HashSet (kolekcja c); tworzy równoważny obiekt HashSet dla danej kolekcji. Ten konstruktor służy do konwersji między obiektami kolekcji.

LinkedHashSet:

Jest to klasa potomna HashSet. jest dokładnie taki sam jak HashSet, w tym (konstruktory i metody), z wyjątkiem następujących różnic.

Różnice HashSet:

  1. Podkreślona struktura danych jest Hashtable.
  2. Zamówienie reklamowe nie jest zachowywane.
  3. wprowadzono wersję 1.2.

LinkedHashSet:

  1. Podkreślona struktura danych to połączenie LinkedList i Hashtable.
  2. Zamówienie reklamowe jest zachowane.
  3. Wprowadzony w wersji 1.4.
Umapathi
źródło
1

Jeśli spojrzysz na konstruktory wywołane z LinkedHashSetklasy, zobaczysz, że wewnętrznie jest LinkedHashMapto używany jako kopia zapasowa.

rafa
źródło
0

Wszystkie metody i konstruktory są takie same, ale tylko jedna różnica polega na tym, że LinkedHashset zachowuje kolejność reklam, ale nie zezwala na duplikaty.

Hashset nie będzie obsługiwać żadnych zamówień reklamowych. Jest to proste połączenie List i Set :)

Anand Mohan
źródło