Co się stanie, gdy duplikat klucza zostanie umieszczony w HashMap?

276

Jeśli mijam te same kluczowe wielokrotnie do HashMap„s putmetody, co dzieje się z pierwotnej wartości? A jeśli nawet wartość się powtarza? Nie znalazłem żadnej dokumentacji na ten temat.

Przypadek 1: Nadpisane wartości klucza

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","not one");
mymap.put("1","surely not one");
System.out.println(mymap.get("1"));

Dostajemy surely not one.

Przypadek 2: Zduplikowana wartość

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","not one");
mymap.put("1","surely not one");
// The following line was added:
mymap.put("1","one");
System.out.println(mymap.get("1"));

Dostajemy one.

Ale co dzieje się z innymi wartościami? Uczyłem studenta podstaw i zostałem o to poproszony. Czy jest Mapjak wiadro, do którego odwołuje się ostatnia wartość (ale w pamięci)?

boodieye
źródło
7
BTW, jest to doskonała okazja, aby pochwalić się wieloma hashapami, które są częścią klas kolekcji w Dżakarcie ( commons.apache.org/collections ). Pozwoli ci to powiązać dowolną liczbę wartości z tym samym kluczem na te czasy, kiedy będziesz tego potrzebować.
John Munsch,
możliwy duplikat HashMap z wieloma wartościami pod tym samym kluczem
Muhammed Refaat

Odpowiedzi:

303

Z definicji putpolecenie zastępuje poprzednią wartość powiązaną z danym kluczem na mapie (koncepcyjnie jak operacja indeksowania tablic dla typów pierwotnych).

Mapa po prostu upuszcza swoje odniesienie do wartości. Jeśli nic innego nie zawiera odwołania do obiektu, obiekt ten kwalifikuje się do odśmiecania. Ponadto Java zwraca dowolną poprzednią wartość związaną z danym kluczem (lub nulljeśli nie występuje), dzięki czemu możesz określić, co tam było i zachować referencję, jeśli to konieczne.

Więcej informacji tutaj: HashMap Doc

jheddings
źródło
Dzięki za to. Czytanie w dokumentacji Java nie jest wyraźnie wspomniane. Zgaduję, że autor dokumentu założył, że jest to milczące założenie wszystkich implementacji mapy skrótu.
Andrew S,
77

Odpowiedź możesz znaleźć w javadoc mapy # put (K, V) (która faktycznie coś zwraca):

public V put(K key,
             V value)

Kojarzy określoną wartość z określonym kluczem na tej mapie (operacja opcjonalna). Jeśli mapa zawierała wcześniej mapowanie tego klucza, stara wartość jest zastępowana określoną wartością. ( mMówi się, że mapa zawiera mapowanie klucza kwtedy i tylko wtedy m.containsKey(k), gdy powróci true.)

Parametry:
key - klucz, z którym ma być powiązana określona wartość.
value- wartość, która ma być powiązana z określonym kluczem.

Zwraca:
poprzednia wartość związana z określonym kluczem lub nulljeśli nie było mapowania key. ( nullZwrot może również wskazywać, że mapa poprzednio powiązana nullz określonym key, jeśli implementacja obsługuje nullwartości.)

Jeśli więc nie przypiszesz zwracanej wartości podczas wywoływania mymap.put("1", "a string"), staje się ona po prostu bez odniesienia, a zatem kwalifikuje się do odśmiecania.

Pascal Thivent
źródło
3
Zwrócona wartość jest poprzednia wartość (lub null) jak udokumentowano tylko powyżej w javadoc tak, tak, to jest to, co mam na myśli. Czy to naprawdę może być źle interpretowane?
Pascal Thivent
To jest bardzo pomocne.
roottraveller,
18

Poprzednia wartość klucza jest usuwana i zastępowana nową.

Jeśli chcesz zachować wszystkie wartości podane w kluczu, możesz rozważyć wdrożenie czegoś takiego:

import org.apache.commons.collections.MultiHashMap;
import java.util.Set;
import java.util.Map;
import java.util.Iterator;
import java.util.List;
public class MultiMapExample {

   public static void main(String[] args) {
      MultiHashMap mp=new MultiHashMap();
      mp.put("a", 10);
      mp.put("a", 11);
      mp.put("a", 12);
      mp.put("b", 13);
      mp.put("c", 14);
      mp.put("e", 15);
      List list = null;

      Set set = mp.entrySet();
      Iterator i = set.iterator();
      while(i.hasNext()) {
         Map.Entry me = (Map.Entry)i.next();
         list=(List)mp.get(me.getKey());

         for(int j=0;j<list.size();j++)
         {
          System.out.println(me.getKey()+": value :"+list.get(j));
         }
      }
   }
}
kamlesh0606
źródło
1
To rozwiązanie jest osłabione. MultiHashMap jest częścią apache.commons.collections, a nie java.
wikimix
17

jest to funkcja Klucz / Wartość i nie można mieć duplikatu klucza dla kilku wartości, ponieważ gdy chcesz uzyskać rzeczywistą wartość, która z wartości należy do wpisanego klucza
w twoim przykładzie, gdy chcesz uzyskać wartość „1”, która to jest to ?!
to powody, dla których warto mieć unikalny klucz dla każdej wartości, ale możesz spróbować sztuczki według standardowej biblioteki Java:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class DuplicateMap<K, V> {

    private Map<K, ArrayList<V>> m = new HashMap<>();

    public void put(K k, V v) {
        if (m.containsKey(k)) {
            m.get(k).add(v);
        } else {
            ArrayList<V> arr = new ArrayList<>();
            arr.add(v);
            m.put(k, arr);
        }
    }

     public ArrayList<V> get(K k) {
        return m.get(k);
    }

    public V get(K k, int index) {
        return m.get(k).size()-1 < index ? null : m.get(k).get(index);
    }
}


i możesz użyć tego w ten sposób:

    public static void main(String[] args) {
    DuplicateMap<String,String> dm=new DuplicateMap<>();
    dm.put("1", "one");
    dm.put("1", "not one");
    dm.put("1", "surely not one");
    System.out.println(dm.get("1"));
    System.out.println(dm.get("1",1));
    System.out.println(dm.get("1", 5));
}

a wynikiem wydruków są:

[one, not one, surely not one]
not one
null
java acm
źródło
Świetna odpowiedź! dobra robota. Dosłownie ratujesz moje życie programistyczne :).
Subin Babu,
Dziękuję również ode mnie! Musiałem dodać metodę „usuń”, aby wykonać tę samą funkcjonalność co normalna mapa, ale działało świetnie!
JGlass,
1
@JGlass, witaj, stary, ale to nie jest rozwiązanie techniczne, to jest to, co możesz zrobić za pomocą standardowej biblioteki Java, w technicznym problemie musisz uważać na swój problem, jeśli chcesz mieć takie zachowanie, jestem pewien, że to nie jest rozwiązanie, ponieważ koncepcji klucza / wartości i należy pomyśleć o problemie i znaleźć logiczny sposób rozwiązania. w każdym razie moje dane to po prostu świetny sposób na zrobienie tego z Javą, a w produkcji problemy i droga rozwiązania są bardzo różne od dobrej zabawy! ale możesz go użyć, gdy zachowanie klucza / wartości nie jest twoim problemem i znalezienie takiej struktury danych.
java acm
13

Kojarzy określoną wartość z określonym kluczem na tej mapie. Jeśli mapa poprzednio zawierała mapowanie klucza, stara wartość zostanie zastąpiona.

Diego Alejandro
źródło
12

To zastępuje istniejącą wartość na mapie dla odpowiedniego klucza. A jeśli nie istnieje żaden klucz o tej samej nazwie, tworzy klucz o podanej wartości. na przykład:

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","two");

Klucz wyjściowy = „1”, wartość = „dwa”

Tak więc poprzednia wartość zostaje zastąpiona.

Bishal Jaiswal
źródło
4

Na twoje pytanie, czy mapa była jak wiadro: nie.

To jest jak lista z name=valueparami, podczas namegdy nie musi to być ciąg znaków (może jednak).

Aby uzyskać element, przekazujesz klucz do metody get (), która w zamian daje ci przypisany obiekt.

A mapa hash oznacza, że ​​jeśli próbujesz odzyskać swój obiekt za pomocą metody get-, nie porówna on rzeczywistego obiektu z tym, który podałeś, ponieważ musiałby iterować swoją listę i porównywać () klucz podałeś bieżący element.

To byłoby nieefektywne. Zamiast tego, bez względu na to, z czego składa się twój obiekt, oblicza tak zwany kod skrótu z obu obiektów i porównuje je. Łatwiej jest porównać dwa ints zamiast dwóch całych (być może bardzo złożonych) obiektów. Możesz sobie wyobrazić hashcode jako podsumowanie o określonej długości (int), dlatego nie jest unikalny i ma kolizje. Zasady dotyczące kodu skrótu znajdują się w dokumentacji, do której wstawiłem łącze.

Jeśli chcesz dowiedzieć się więcej na ten temat, możesz zajrzeć do artykułów na javapractices.com i technofundo.com

pozdrowienia

Atokreacje
źródło
3

Zawsze używałem:

HashMap<String, ArrayList<String>> hashy = new HashMap<String, ArrayList<String>>();

gdybym chciał zastosować wiele rzeczy do jednego klucza identyfikującego.

public void MultiHash(){
    HashMap<String, ArrayList<String>> hashy = new HashMap<String, ArrayList<String>>();
    String key = "Your key";

    ArrayList<String> yourarraylist = hashy.get(key);

    for(String valuessaved2key : yourarraylist){
        System.out.println(valuessaved2key);
    }

}

zawsze możesz zrobić coś takiego i stworzyć sobie labirynt!

public void LOOK_AT_ALL_THESE_HASHMAPS(){
    HashMap<String, HashMap<String, HashMap<String, HashMap<String, String>>>> theultimatehashmap = new HashMap <String, HashMap<String, HashMap<String, HashMap<String, String>>>>();
    String ballsdeep_into_the_hashmap = theultimatehashmap.get("firststring").get("secondstring").get("thirdstring").get("forthstring");
}
sheepiiHD
źródło
2

Mapy z JDK nieprzeznaczone do przechowywania danych pod zduplikowanymi kluczami.

  • W najlepszym razie nowa wartość zastąpi poprzednie.

  • Gorszym scenariuszem jest wyjątek (np. Gdy próbujesz zebrać go jako strumień):

Brak duplikatów:

Stream.of("one").collect(Collectors.toMap(x -> x, x -> x))

Dobrze. Otrzymasz: 2 $ ==> {one = one}

Powielony strumień:

Stream.of("one", "not one", "surely not one").collect(Collectors.toMap(x -> 1, x -> x))

Wyjątek java.lang.IllegalStateException: Duplikat klucza 1 (próba scalenia wartości jedna, a nie jedna) | at Collectors.duplicateKeyException (Collectors.java:133) | w Collectors.lambda $ uniqKeysMapAccumulator $ 1 (Collectors.java:180) | na ReduceOps $ 3ReducingSink.accept (ReduceOps.java:169) | w Spliterators $ ArraySpliterator.forEachRemaining (Spliterators.java:948) | at AbstractPipeline.copyInto (AbstractPipeline.java:484) | at AbstractPipeline.wrapAndCopyInto (AbstractPipeline.java:474) | w ReduceOps $ ReduceOp.evaluateSequential (ReduceOps.java:913) | at AbstractPipeline.evaluate (AbstractPipeline.java:234) | at ReferencePipeline.collect (ReferencePipeline.java:578) | o (# 4: 1)

Aby poradzić sobie ze zduplikowanymi kluczami - użyj innego pakietu, np .: https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/Multimap.html

Istnieje wiele innych implementacji dotyczących zduplikowanych kluczy. Są one potrzebne w Internecie (np. Zduplikowane klucze cookie, nagłówki HTTP mogą mieć te same pola, ...)

Powodzenia! :)

Witold Kaczurba
źródło
czy operacja „zastępowania” jest kosztowna?
gaurav
Można to rozwiązać tylko przy użyciu JDK. Collectors.toMap()ma trzeci argument - funkcję scalania. Jeśli chcemy po prostu zastąpić ostatni duplikat elementu: Stream.of("one", "two", "one").collect(Collectors.toMap(x -> x, x -> x, (key1, key2) -> key2)). link
samodzielny
Także twój drugi przykład kodu jest niepoprawny. Te dane wejściowe: "one", "not one", "surely not one"nie spowodują żadnych powtarzających się błędów klucza z powodu różnych ciągów znaków.
samodzielny
Cześć samotnie. Przeczytaj uważnie funkcję mapowania (toMap).
Witold Kaczurba
Cześć @WitoldKaczurba. Skompiluj kod przed opublikowaniem.
samodzielny
1

BTW, jeśli chcesz trochę semantyki, takiej jak wstaw tylko, jeśli ten klucz nie istnieje. możesz używać concurrentHashMapz putIfAbsent()funkcją. Sprawdź to:

https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html#put(K,%20V)

concurrentHashMap jest bezpieczny dla wątków i ma wysoką wydajność, ponieważ wykorzystuje mechanizmblokowania pasków ” w celu zwiększenia przepustowości.

BufBills
źródło
1

Tak, oznacza to, że wszystkie 1 klucze z wartością są zastąpione ostatnią wartością dodaną, a tutaj dodajesz „na pewno nie jeden”, więc wyświetli się tylko „na pewno nie jeden”.

Nawet jeśli próbujesz wyświetlić za pomocą pętli, wyświetli również tylko jeden klucz i wartość, które mają ten sam klucz.

ajaynakrani
źródło
0
         HashMap<Emp, Emp> empHashMap = new HashMap<Emp, Emp>();

         empHashMap.put(new Emp(1), new Emp(1));
         empHashMap.put(new Emp(1), new Emp(1));
         empHashMap.put(new Emp(1), new Emp());
         empHashMap.put(new Emp(1), new Emp());
         System.out.println(empHashMap.size());
    }
}

class Emp{
    public Emp(){   
    }
    public Emp(int id){
        this.id = id;
    }
    public int id;
    @Override
    public boolean equals(Object obj) {
        return this.id == ((Emp)obj).id;
    }

    @Override
    public int hashCode() {
        return id;
    }
}


OUTPUT : is 1

Oznacza mapę skrótów nie zezwala na duplikaty, jeśli poprawnie zastąpiłeś metody equals i hashCode ().

HashSet używa również HashMap wewnętrznie, patrz dokument źródłowy

public class HashSet{
public HashSet() {
        map = new HashMap<>();
    }
}
SatyaS
źródło