Czy dodanie zduplikowanej wartości do HashSet / HashMap zastępuje poprzednią wartość

137

Proszę wziąć pod uwagę poniższy fragment kodu:

HashSet hs = new HashSet();
hs.add("hi"); -- (1)
hs.add("hi"); -- (2)

hs.size()da 1, ponieważ HashSetnie zezwala na duplikaty, więc tylko jeden element zostanie zapisany.

Chcę wiedzieć, czy dodajemy zduplikowany element, czy zastępuje on poprzedni element, czy po prostu go nie dodaje?

Co się stanie HashMapz tym samym przypadkiem?

Anand
źródło

Odpowiedzi:

247

W przypadku HashMapzastępuje starą wartość nową.

W przypadku HashSet, element nie jest wstawiany.

Keppil
źródło
1
Nie wiesz, czego mi brakuje, ale kod źródłowy wydaje się wskazywać inaczej? Widzę, że nie sprawdzają podkładu, HashMapaby sprawdzić, czy keyjuż istnieje przed wywołaniem putpodkładu map?
mystarrocks
10
@mystarrocks: klucz jest elementem operacji Seti nigdy nie jest zastępowany przez put()operację.
Keppil
1
Ach, teraz rozumiem. Zrozumiałem, że klucz jest elementem elementu the Set, ale właśnie zdałem sobie sprawę, że put()nadpisuje tylko wartość, a nie klucz. W tym przypadku jest to ta sama wartość umieszczona ponownie obok klucza, co może, ale nie musi, być lepsze niż sprawdzenie, czy klucz istnieje i wstawienie. Tak czy inaczej, rozumiem, jak to działa.
mystarrocks
Ciekawe, dlaczego HashMap i HashSet decydują się na to?
Helin Wang,
@HelinWang: Myślę, że nie było to zaplanowane, myślę, że to po prostu efekt HashSetwdrożenia w formie pliku HashMap. Trudno to jednak wiedzieć, chyba że jesteś jednym z twórców klas.
Keppil,
47

Pierwszą rzeczą, którą musisz wiedzieć, jest to, że HashSetdziała jak a Set, co oznacza, że ​​dodajesz swój obiekt bezpośrednio do HashSeti nie może zawierać duplikatów. Po prostu dodajesz swoją wartość bezpośrednio HashSet.

Jednak HashMapjest to Maptyp. Oznacza to, że za każdym razem, gdy dodajesz wpis, dodajesz parę klucz-wartość.

W HashMapmożesz mieć zduplikowane wartości, ale nie zduplikowane klucze. W HashMapnowym wpisie zastąpi stary. Najnowszy wpis będzie w HashMap.

Zrozumienie powiązania między HashMap i HashSet:

Pamiętaj, HashMapnie możesz mieć zduplikowanych kluczy. Za sceną HashSetużywa HashMap.

Kiedy próbujesz dodać dowolny obiekt do HashSet, ten wpis jest w rzeczywistości przechowywany jako klucz w HashMap- tym samym, HashMapktóry jest używany za sceną HashSet. Ponieważ ten HashMapelement bazowy wymaga pary klucz-wartość, generowana jest dla nas wartość fikcyjna.

Teraz, gdy spróbujesz wstawić inny zduplikowany obiekt do tego samego HashSet, ponownie spróbuje wstawić go jako klucz do HashMapleżącego poniżej. Jednak HashMapnie obsługuje duplikatów. Dlatego HashSetnadal będzie skutkować posiadaniem tylko jednej wartości tego typu. Na marginesie, dla każdego zduplikowanego klucza, ponieważ wartość wygenerowana dla naszego wpisu w HashSet jest jakąś losową / fikcyjną wartością, klucz nie jest w ogóle zastępowany. zostanie zignorowane, ponieważ usunięcie klucza i dodanie z powrotem tego samego klucza (fikcyjna wartość jest taka sama) nie miałoby żadnego sensu.

Podsumowanie:

HashMapumożliwia duplikowanie values, ale nie keys. HashSetnie może zawierać duplikatów.

Aby pobawić się, czy dodanie obiektu zakończyło się pomyślnie, czy nie, możesz sprawdzić booleanwartość zwracaną podczas wywołania .add() i zobaczyć, czy zwraca truelub false. Jeśli zwrócił true, został włożony.

Jimmy
źródło
HashMap allows duplicate valuesHashMap zastępuje starą wartość nową.
Alex78191
20

W docs są całkiem jasno: HashSet.add nie wymienić:

Dodaje określony element do tego zestawu, jeśli nie jest jeszcze obecny. Bardziej formalnie, dodaje określony element e do tego zestawu, jeśli ten zestaw nie zawiera elementu e2 takiego, że (e == null? E2 == null: e.equals (e2)). Jeśli ten zestaw już zawiera element, wywołanie pozostawia zestaw bez zmian i zwraca false.

Ale będzie wymienić:HashMap.put

Jeśli mapa zawierała wcześniej mapowanie klucza, stara wartość jest zastępowana.

pb2q
źródło
4

W przypadku HashSet NIE zastępuje go.

Z dokumentów:

http://docs.oracle.com/javase/6/docs/api/java/util/HashSet.html#add(E )

"Dodaje określony element do tego zestawu, jeśli jeszcze go nie ma. Bardziej formalnie dodaje określony element e do tego zestawu, jeśli ten zestaw nie zawiera elementu e2 takiego, że (e == null? E2 == null: e.equals ( e2)). Jeśli ten zestaw już zawiera element, wywołanie pozostawia zestaw bez zmian i zwraca fałsz. "

Bob Provencher
źródło
1

Popraw mnie, jeśli się mylę, ale to, do czego zmierzasz, to to, że w przypadku łańcuchów „Hi” == „Hi” nie zawsze wychodzi jako prawdą (ponieważ niekoniecznie są one tym samym obiektem).

Powodem, dla którego otrzymujesz odpowiedź 1, jest jednak to, że maszyna JVM ponownie użyje obiektów łańcuchowych, jeśli to możliwe. W tym przypadku maszyna JVM ponownie wykorzystuje obiekt łańcuchowy, nadpisując w ten sposób element w Hashmap / Hashset.

Ale nie masz gwarancji takiego zachowania (ponieważ może to być inny obiekt ciągu o tej samej wartości „Hi”). Zachowanie, które widzisz, jest spowodowane optymalizacją maszyny JVM.

Nick Rippe
źródło
0

Musisz najpierw sprawdzić metodę put w mapie Hash, ponieważ HashSet jest kopiowany przez HashMap

  1. Gdy dodasz zduplikowaną wartość, wypowiedz ciąg „One” w HashSet,
  2. Wpis („jeden”, OBECNY) zostanie wstawiony do Hashmap (dla wszystkich wartości dodanych do zestawu, wartość będzie „OBECNA”, co jeśli jest typu Object)
  3. Hashmap dodaje wpis do Map i zwraca wartość, która w tym przypadku jest „PRESENT” lub null, jeśli Entry tam nie ma.
  4. Metoda add Hashset zwraca następnie wartość true, jeśli wartość zwrócona z Hashmap jest równa null, w przeciwnym razie false, co oznacza, że ​​wpis już istnieje ...
shiv
źródło
0

Mówiąc inaczej: kiedy wstawisz parę klucz-wartość do HashMap, gdzie klucz już istnieje (w pewnym sensie hashvalue () daje tę samą wartość und equal () jest prawdziwe, ale te dwa obiekty mogą nadal różnić się na kilka sposobów ), klucz nie zostanie zastąpiony, ale wartość zostanie nadpisana. Klucz jest po prostu używany do pobrania hashvalue () i znalezienia z nią wartości w tabeli. Ponieważ HashSet używa kluczy HashMap i ustawia dowolne wartości, które tak naprawdę nie mają znaczenia (dla użytkownika), w rezultacie elementy zestawu również nie są zastępowane.

Marco Rothley
źródło
0

HashMapw zasadzie zawiera, Entryktóre następnie zawiera Key(Object)i. Value(Object)Wewnętrznie HashSetHashMapi HashMapzastępują wartości, jak niektórzy z was już wskazali, ale czy to naprawdę zastępuje klucze ??? Nie .. i na tym polega sztuczka. HashMapzachowuje swoją wartość jako klucz w źródle, HashMapa wartość jest tylko fikcyjnym obiektem, więc jeśli spróbujesz ponownie wstawić tę samą wartość w HashMap (klucz w podstawowej mapie) .Zastępuje po prostu wartość fikcyjną, a nie klucz (wartość dla HashSet).

Spójrz na poniższy kod dla klasy HashSet:

public boolean  [More ...] add(E e) {

   return map.put(e, PRESENT)==null;
}

Tutaj e jest wartością dla HashSet, ale klucz dla podstawowej mapy. A klucz nigdy nie jest zastępowany. Mam nadzieję, że uda mi się usunąć zamieszanie.

Kunal Kumar
źródło