Różnica między HashSet i HashMap?

168

Poza tym, że HashSet nie zezwala na zduplikowane wartości, jaka jest różnica między HashMapi HashSet?

Mam na myśli mądre wdrożenie? Jest to trochę niejasne, ponieważ obie używają tablic mieszających do przechowywania wartości.

SpikETidE
źródło
HashSet jest zaimplementowany przy użyciu HashMap
therealprashant
Myślę, że wiedza o tym, dlaczego HashSet różni się od ArrayList, pomoże ci zrozumieć odpowiedź na powyższe pytanie: stackoverflow.com/questions/18706870/ ...
djangofan

Odpowiedzi:

150

Są to zupełnie inne konstrukcje. A HashMapjest implementacją Map. Mapa odwzorowuje klucze do wartości. Wyszukiwanie klucza odbywa się za pomocą skrótu.

Z drugiej strony, a HashSetjest implementacją Set. Zestaw został zaprojektowany, aby dopasować model matematyczny zestawu. Jak zauważyłeś, A HashSetużywa a HashMapdo poparcia swojej implementacji. Jednak implementuje zupełnie inny interfejs.

Jeśli szukasz tego, co będzie najlepsze Collectiondo twoich celów, ten samouczek jest dobrym punktem wyjścia. Jeśli naprawdę chcesz wiedzieć, co się dzieje, jest też książka o tym .

justkt
źródło
To stwierdzenie jest nieco uproszczone. Pod okładkami dzieje się więcej, "" Zwraca wartość skrótu dla określonego obiektu. Oprócz własnego hashCode obiektu ta metoda stosuje „dodatkową funkcję skrótu”, która chroni przed funkcjami skrótu o niskiej jakości. Jest to krytyczne, ponieważ HashMap używa tablic mieszających o potędze dwóch długości. ” Weblogs.java.net/blog/2005/06/18/hashmap-implementation - jednak jeśli spojrzysz na dokument, zobaczysz, że ten skrót dystrybuuje rzeczy ponad „zasobniki”, więc w końcu uważam, że dwie rzeczy mogą zostać zmapowane w tym samym
zasobniku
1
Odpowiadając na drugie pytanie - nie. Mapa jest, jeśli chcesz (klucz -> wartość) zgodnie z doskonałą odpowiedzią @Bruno Rothgiesser. Zestaw jest dla elementów, które nie są zduplikowane. Jeśli chcesz mieć duplikaty, a nie klucz-> wartość, sprawdzę implementację java.util.List. Zapoznaj się z samouczkiem dotyczącym kolekcji, aby uzyskać ostateczny przewodnik: java.sun.com/docs/books/tutorial/collections/index.html
justkt
@justk: tak, możesz dostać dwa klucze w jednym wiadrze, a następnie używa się equals (), aby je rozróżnić. Dlatego ważne jest, aby hashCode () i equals () były zgodne.
Michael Borgwardt
6
@SpikETidE: ani HashMap, ani HashSet nie zezwalają na duplikaty. O to chodzi.
Michael Borgwardt
23
@SpikETidE: zestaw nie ma par klucz / wartość, tylko elementy. HashSet jest implementowany przez posiadanie HashMap z elementami set jako kluczami i ignorowaną wartością.
Michael Borgwardt
300

HashSet to zestaw , np. {1,2,3,4,5}

HashMap to mapa klucz -> wartość (klucz do wartości), np. {A -> 1, b -> 2, c -> 2, d -> 1}

Zauważ, że w powyższym przykładzie w HashMap nie może być zduplikowanych kluczy, ale mogą one mieć zduplikowane wartości.

W HashSet nie może być żadnych zduplikowanych elementów.

Rosół
źródło
Ale (najbardziej interesującym) powodem zamieszania jest to, że nawet w HashSet potrzebujesz „klucza”, aby uzyskać dostęp do elementów. Tj. Obiekty, nawet w matematyce, mają nazwy (lub adresy), jeśli mają być dostępne lub odniesienia. Zatem w tym prawdziwym sensie HashSet jest szczególnie prostą HashMapą, z kluczem zawierającym nazwy (lub adresy) jego elementów.
Andrew Marshall,
65

HashSet

  1. Klasa HashSet implementuje interfejs Set
  2. W HashSet przechowujemy obiekty (elementy lub wartości) np. Jeśli mamy HashSet elementów string, to może on przedstawiać zestaw elementów HashSet: {„Hello”, „Hi”, „Bye”, „Run”}
  3. HashSet nie zezwala na zduplikowane elementy, co oznacza, że ​​nie można przechowywać zduplikowanych wartości w HashSet.
  4. HashSet zezwala na posiadanie pojedynczej wartości null.
  5. HashSet nie jest zsynchronizowany, co oznacza, że ​​nie nadają się do operacji bezpiecznych wątkowo, dopóki nie zostaną zsynchronizowane jawnie. [Podobieństwo]

                          add      contains next     notes
    HashSet               O(1)     O(1)     O(h/n)   h is the table 

HashMap

  1. Klasa HashMap implementuje interfejs Map
  2. HashMap służy do przechowywania par klucz-wartość. Krótko mówiąc, zachowuje mapowanie klucza i wartości (klasa HashMap jest z grubsza równoważna z Hashtable, z wyjątkiem tego, że jest niezsynchronizowana i dopuszcza wartości null). np. {1 -> „Cześć”, 2 -> „Cześć”, 3 -> „Do widzenia”, 4 -> „Biegnij”}
  3. HashMap nie zezwala na zduplikowane klucze, ale pozwala na zduplikowane wartości.
  4. HashMap dopuszcza pojedynczy klucz null i dowolną liczbę wartości null.
  5. HashMap nie jest synchronizowany, co oznacza, że ​​nie nadają się do operacji bezpiecznych wątkowo, dopóki nie zostaną zsynchronizowane jawnie. [Podobieństwo]

                           get      containsKey next     Notes
     HashMap               O(1)     O(1)        O(h/n)   h is the table 

Zapoznaj się z tym artykułem, aby znaleźć więcej informacji.

Avanish Kumar
źródło
36

Szkoda, że ​​obie nazwy zaczynają się od Hash . To najmniej ważna część z nich. Ważne części pojawiają się po skrócie - zestaw i mapa , jak zauważyli inni. Tym, czym są, są odpowiednio Zestaw - nieuporządkowana kolekcja - i Mapa - kolekcja z dostępem z kluczem. Tak się składa, że ​​są implementowane za pomocą skrótów - stąd pochodzą nazwy - ale ich esencja jest ukryta za tą częścią ich nazw.

Nie dajcie się zmylić ich imionami; są to bardzo różne rzeczy.

Carl Manaster
źródło
@HiteshSahu Oba są zaimplementowane za pomocą tabel skrótów ( en.wikipedia.org/wiki/Hash_table ). Jest to dobra struktura danych do reprezentowania zestawu, wydajna we właściwy sposób i, w zasadzie, klucze HashMap są implementowane jako HashSet. Więc ktokolwiek je nazwał, zadał sobie trud, aby je wdrożyć i skupił się na implementacji, a nie na celu (przypuszczenie).
Carl Manaster
1
Dobrze wyjaśnione. Dziękuję Ci.
user3932000
5

Te Hashsetnarzędzia z wewnętrznym HashMap. Jeśli widzisz implementację wewnętrzną, wartości wstawione w HashSet są przechowywane jako klucze w HashMap, a wartość jest obiektem Dummy klasy Object.
Różnica między HashMap a HashSet to: -

  1. HashMap zawiera pary klucz-wartość, a do każdej wartości można uzyskać dostęp za pomocą klucza, w którym HashSet musi być za każdym razem iterowany, ponieważ nie ma metody get.
  2. HashMapimplementuje interfejs Map i zezwala na jedną wartość null jako klucz i wiele wartości null jako wartości. gdzie HashSetimplementuje interfejs Set, dopuszcza tylko jedną wartość null i brak zduplikowanych wartości. (Pamiętaj, że jeden pusty klucz jest dozwolony w kluczu HashMap, stąd jedna wartość null w HashSet ponieważ HashSet implementuje wewnętrznie HashMap).
  3. HashSeti HashMapnie zachowuje kolejności wstawiania podczas iteracji.
Abhay S
źródło
3

HashSet pozwala nam na przechowywanie obiektów w zestawie, gdzie jak HashMap pozwala na przechowywanie obiektów na podstawie klucza i wartości. Każdy obiekt lub obiekt przechowywany będzie miał klucz.

Spidfire
źródło
2

Jak sugerują nazwy, HashMap jest mapą asocjacyjną (mapowaniem z klucza do wartości), a HashSet to tylko zestaw .

leonbloy
źródło
2
@SpikETidE To jest szczegół na temat implementacji unikalności, ale znaczenie HashSet polega na zaimplementowaniu zestawu.
Michael Borgwardt
1
więc .. wszystko sprowadza się do „jeśli nie chcesz duplikatów, użyj hashSet ... Jeśli nie przejmujesz się duplikatami, użyj HashMap” ....?
SpikETidE
3
Java nie implementuje określonej klasy dla „kolekcji z potencjalnie zduplikowanymi elementami” („worek”), możesz użyć do tego List (chociaż List dodaje pewną semantyczną do bag: order; ale możesz to zignorować).
leonbloy
2

Różnice między HashSet i HashMap w Javie

1) Pierwsza i najbardziej znacząca różnica między HashMap i HashSet polega na tym, że HashMap jest implementacją interfejsu Map, podczas gdy HashSet jest implementacją interfejsu Set, co oznacza, że ​​HashMap jest strukturą danych opartą na kluczowej wartości, a HashSet gwarantuje wyjątkowość, nie zezwalając na duplikaty. reality HashSet to wrapper wokół HashMap w Javie, jeśli spojrzysz na kod metody add (E e) HashSet.java, zobaczysz następujący kod:

public boolean add(E e) 
{
    return map.put(e, PRESENT)==null;
}

gdzie umieszczenie obiektu na mapie jako klucza i wartości jest ostatecznym obiektem OBECNY, który jest fikcyjny.

2) Druga różnica między HashMap i HashSet polega na tym, że używamy metody add () do umieszczania elementów w Set, ale używamy metody put () do wstawiania klucza i wartości do HashMap w Javie.

3) HashSet zezwala tylko na jeden klucz pusty, ale HashMap może zezwalać na jeden klucz pusty + wiele wartości null.

To wszystko na różnicy między HashSet i HashMap w Javie. Podsumowując, HashSet i HashMap to dwa różne typy kolekcji, jedna to Set, a druga to Map.

Vibha Sanskrityayan
źródło
2

Różnice między HashSet i HashMap w Javie

HashSet wewnętrznie używa HashMap do przechowywania obiektów. Gdy metoda add (String) nazywa ją wywołuje metodę HahsMap put (klucz, wartość), gdzie klucz = obiekt ciągu i wartość = nowy obiekt (Dummy). Więc nie zachowuje duplikatów, ponieważ klucze są niczym innym jak wartością Obiekt.

Obiekty, które są przechowywane jako klucz w Hashset / HashMap, powinny przesłonić hashcode i equals contract.

Klucze używane do uzyskiwania dostępu / przechowywania obiektów wartości w HashMap powinny być zadeklarowane jako końcowe, ponieważ po zmodyfikowaniu obiektu wartości nie można zlokalizować i zwraca wartość null.

user3539704
źródło
1

A HashMappolega na dodawaniu, pobieraniu, usuwaniu ... obiektów indeksowanych przez niestandardowy klucz dowolnego typu.
A HashSetpolega na dodawaniu elementów, usuwaniu elementów i sprawdzaniu, czy elementy są obecne, porównując ich skróty.

Zatem HashMap zawiera elementy, a HashSet zapamiętuje ich skróty.

Martijn Courteaux
źródło
1
Porównując ich skróty i wywołując ich equals()metody.
Markiz Lorne
1

Różnice: w odniesieniu do hierarchii: HashSet implementuje Set. HashMap implementuje Map i przechowuje mapowanie kluczy i wartości.

Zastosowanie HashSet i HashMap w odniesieniu do bazy danych pomoże ci zrozumieć znaczenie każdego z nich.
HashSet: jest zwykle używany do przechowywania unikatowych obiektów kolekcji. Np .: Może być użyty jako klasa implementacji do przechowywania relacji wiele do jednego pomiędzy
klasą Przedmiot a Klasą Oferta, gdzie (Przedmiot ma wiele ofert) HashMap: służy do mapowania klucza do wartości. Wartość może być zerowa lub dowolny obiekt / lista obiektu (który sam w sobie jest obiektem).

koło pasowe bez tarcia
źródło
0

HashSet jest realizowany w kategoriach HashMap . Jest to mapowanie między kluczem a OBECNYM obiektem.

Matthew Flaschen
źródło
5
Co to jest „OBECNY obiekt”?
Markiz Lorne
0

HashSet używa HashMap wewnętrznie do przechowywania swoich wpisów. Każdy wpis w wewnętrznej HashMap jest kluczowany przez pojedynczy obiekt, więc wszystkie wpisy są mieszane w tym samym zasobniku. Nie pamiętam, czego używa wewnętrzna HashMap do przechowywania swoich wartości, ale tak naprawdę nie ma to znaczenia, ponieważ ten wewnętrzny kontener nigdy nie będzie zawierał zduplikowanych wartości.

EDYCJA : Aby odnieść się do komentarza Matthew, ma rację; Miałem to od tyłu. Wewnętrzna mapa HashMap jest kluczowana za pomocą obiektów, które tworzą elementy Set . Wartości HashMap to obiekt, który jest po prostu przechowywany w zasobnikach HashMap.

Andy Gherna
źródło
To nie tak. Elementy zestawu są bezpośrednio używane jako klucze HashMap.
Matthew Flaschen
0

HashMapjest Mapimplementacją umożliwiającą zduplikowane wartości, ale nie zduplikowane klucze. . Do dodania obiektu wymagana jest para klucz / wartość. Dozwolone są klucze o wartości Null i wartości Null. na przykład:

{The-> 3, world-> 5, is-> 2, nice-> 4}

HashSetjest Setimplementacją, która nie pozwala na duplikaty. Jeśli próbowałeś dodać zduplikowany obiekt, wywołanie public boolean add(Object o)metody, to zestaw pozostaje niezmieniony i wraca false. na przykład:

[Świat jest fajny]

Minnie
źródło
-1

właściwie odpowiedziałeś na swoje własne pytanie - hashset nie zezwala na zduplikowane wartości. byłoby trywialne zbudowanie hashsetu przy użyciu bazowej mapy hash (i po prostu sprawdzenie, czy wartość już istnieje). Sądzę, że różne implementacje java albo to robią, albo implementują jakiś niestandardowy kod, aby robić to bardziej wydajnie.

chris
źródło
1
@oedo - java.util.HashSetmówi, że jest wspierany przez plik java.util.HashMap.
justkt
2
Nie zezwalanie na duplikaty nie stanowi różnicy między nimi.
Markiz Lorne
-1

Zasadniczo w HashMap użytkownik musi podać zarówno klucz, jak i wartość, podczas gdy w HashSet podajesz tylko wartość, klucz jest uzyskiwany automatycznie z wartości przy użyciu funkcji skrótu. Więc po posiadaniu zarówno klucza, jak i wartości, HashSet może być wewnętrznie przechowywany jako HashMap.

Munish Goyal
źródło
Klucz jest wartością w HashSet.
Markiz Lorne
-1

HashSet i HashMap obie pary sklepów, różnica polega na tym, że w HashMap możesz określić klucz, podczas gdy w HashSet klucz pochodzi z kodu skrótu obiektu

prateeksarda
źródło
Gdyby to było prawdą, HashSet nie mógł przechowywać wielu obiektów z tym samym hashCode i tak jest.
Markiz Lorne
-1

HashMapszezwalaj na jeden klucz pusty i wartości null. Nie są zsynchronizowane, co zwiększa wydajność. Jeśli jest to wymagane, możesz je zsynchronizować za pomocąCollections.SynchronizedMap()

Hashtables nie zezwalaj na klucze puste i są zsynchronizowane.

Appesh
źródło
Nie pytał o Hashtables. Nie odpowiada na pytanie.
Markiz Lorne
-2

HashMap to implementacja interfejsu Map. HashSet jest implementacją interfejsu Set

HashMap Przechowuje dane w postaci pary klucz-wartość HashSet Store tylko obiekty

Metoda Put służy do dodawania elementu na mapie Metoda Add służy do dodawania elementu Set

W mapie skrótów wartość hashcode jest obliczana za pomocą obiektu kluczowego W tym przypadku obiekt członkowski służy do obliczania wartości kodu skrótu, która może być taka sama dla dwóch obiektów, więc metoda equal () jest używana do sprawdzania równości, jeśli zwraca false, co oznacza, że ​​dwa obiekty są różne.

HashMap jest szybszy niż hashset, ponieważ unikalny klucz jest używany do uzyskiwania dostępu do obiektu HashSet jest wolniejszy niż Hashmap

Hengameh
źródło
1
Mają zasadniczo identyczną wydajność, a sformułowanie „ponieważ używany jest unikalny klucz” jest niepoprawne.
Markiz Lorne