Czy używanie java Map.containsKey () jest nadmiarowe podczas korzystania z map.get ()

93

Zastanawiałem się od jakiegoś czasu, czy w ramach najlepszej praktyki można powstrzymać się od używania containsKey()metody na java.util.Mapi zamiast tego sprawdzić wynik z get().

Moje uzasadnienie jest takie, że dwukrotne sprawdzanie wartości wydaje się zbędne - najpierw dla, containsKey()a potem ponownie dla get().

Z drugiej strony może się zdarzyć, że większość standardowych implementacji Mappamięci podręcznej ostatnie wyszukiwanie lub kompilator może w inny sposób pozbyć się nadmiarowości, a dla czytelności kodu preferowane jest zachowanie containsKey()części.

Byłbym bardzo wdzięczny za twoje komentarze.

Erik Madsen
źródło

Odpowiedzi:

112

Niektóre implementacje Map mogą mieć wartości null, np. HashMap, w tym przypadku, jeśli get(key)zwraca null, nie gwarantuje, że nie ma wpisu w mapie skojarzonej z tym kluczem.

Więc jeśli chcesz wiedzieć, czy mapa zawiera kluczowe zastosowanie Map.containsKey. Jeśli potrzebujesz po prostu wartości zamapowanej na klucz Map.get(key). Jeśli ta mapa zezwala na wartości null, to zwracana wartość null niekoniecznie oznacza, że ​​mapa nie zawiera żadnego mapowania dla klucza; W takim przypadku Map.containsKeyjest bezużyteczna i wpłynie na wydajność. Ponadto w przypadku jednoczesnego dostępu do mapy (np. ConcurrentHashMap), Po przetestowaniu Map.containsKey(key)jest szansa, że ​​wpis zostanie usunięty przez inny wątek przed wywołaniem Map.get(key).

Evgeniy Dorofeev
źródło
8
Nawet jeśli wartość jest ustawiona na null, czy chcesz traktować ją inaczej niż klucz / wartość, która nie jest ustawiona? Jeśli nie musisz specjalnie traktować tego inaczej, możesz po prostu użyćget()
Peter Lawrey
1
Jeśli Maptak private, Twoja klasa może być w stanie zagwarantować, że a nullnigdy nie zostanie wstawiony na mapę. W takim przypadku możesz użyć, get()a następnie sprawdzić wartość null zamiast containsKey(). W niektórych przypadkach może to być jaśniejsze i być może trochę bardziej wydajne.
Raedwald
44

Myślę, że pisanie jest dość standardowe:

Object value = map.get(key);
if (value != null) {
    //do something with value
}

zamiast

if (map.containsKey(key)) {
    Object value = map.get(key);
    //do something with value
}

Nie jest mniej czytelny i nieco wydajniejszy, więc nie widzę powodów, żeby tego nie robić. Oczywiście, jeśli twoja mapa może zawierać wartość null, obie opcje nie mają tej samej semantyki .

asylias
źródło
8

Jak wskazali asyliowie, jest to pytanie semantyczne. Generalnie Map.get (x) == null jest tym, czego potrzebujesz, ale są przypadki, w których ważne jest, aby użyć containsKey.

Jednym z takich przypadków jest pamięć podręczna. Kiedyś pracowałem nad problemem z wydajnością w aplikacji internetowej, która często wykonywała zapytania w swojej bazie danych, szukając jednostek, które nie istnieją. Kiedy przestudiowałem kod pamięci podręcznej dla tego komponentu, zdałem sobie sprawę, że odpytuje bazę danych, jeśli cache.get (klucz) == null. Jeśli baza danych zwróci wartość null (nie znaleziono jednostki), będziemy buforować ten klucz -> mapowanie null.

Przełączenie na includeKey rozwiązało problem, ponieważ mapowanie na wartość null w rzeczywistości coś oznaczało. Mapowanie klucza na null miało inne znaczenie semantyczne niż klucz nieistniejący.

Brandon
źródło
Ciekawy. Dlaczego po prostu nie dodałeś sprawdzenia zerowego przed buforowaniem wartości?
Saket
To niczego by nie zmieniło. Chodzi o to, że mapowanie klucza na null oznacza "już to zrobiliśmy. Jest w pamięci podręcznej. Wartość jest zerowa". Versus nie zawiera w ogóle danego klucza, co oznacza „Nie wiem, nie w pamięci podręcznej, być może będziemy musieli sprawdzić bazę danych”.
Brandon
5
  • containsKeypo którym następuje a getjest zbędne tylko wtedy, gdy wiemy, apriori, że wartości null nigdy nie będą dozwolone. Jeśli wartości null nie są prawidłowe, wywołanie containsKeyma nietrywialny spadek wydajności i jest tylko narzutem, jak pokazano w poniższym benchmarku.

  • OptionalIdiomy Java 8 - Optional.ofNullable(map.get(key)).ifPresentlub Optional.ofNullable(map.get(key)).ifPresent- wiążą się z nietrywialnym narzutem w porównaniu z zwykłymi sprawdzeniami zerowymi.

  • A HashMapużywa O(1)stałego wyszukiwania w tabeli, podczas gdy a TreeMapużywa O(log(n))wyszukiwania. containsKeyNastępnie getidiomu jest znacznie wolniejsze, gdy wywoływany na zasadzie TreeMap.

Benchmarki

Zobacz https://github.com/vkarun/enum-reverse-lookup-table-jmh

// t1
static Type lookupTreeMapNotContainsKeyThrowGet(int t) {
  if (!lookupT.containsKey(t))
    throw new IllegalStateException("Unknown Multihash type: " + t);
  return lookupT.get(t);
}
// t2
static Type lookupTreeMapGetThrowIfNull(int t) {
  Type type = lookupT.get(t);
  if (type == null)
    throw new IllegalStateException("Unknown Multihash type: " + t);
  return type;
}
// t3
static Type lookupTreeMapGetOptionalOrElseThrow(int t) {
  return Optional.ofNullable(lookupT.get(t)).orElseThrow(() -> new 
      IllegalStateException("Unknown Multihash type: " + t));
}
// h1
static Type lookupHashMapNotContainsKeyThrowGet(int t) {
  if (!lookupH.containsKey(t))
    throw new IllegalStateException("Unknown Multihash type: " + t);
  return lookupH.get(t);
}
// h2
static Type lookupHashMapGetThrowIfNull(int t) {
  Type type = lookupH.get(t);
  if (type == null)
    throw new IllegalStateException("Unknown Multihash type: " + t);
  return type;
}
// h3
static Type lookupHashMapGetOptionalOrElseThrow(int t) {
  return Optional.ofNullable(lookupH.get(t)).orElseThrow(() -> new 
    IllegalStateException("Unknown Multihash type: " + t));
}
Benchmark (iteracje) (lookupApproach) Mode Cnt Score Error Units

MultihashTypeLookupBenchmark.testLookup 1000 t1 avgt 9 33,438 ± 4,514 us / op
MultihashTypeLookupBenchmark.testLookup 1000 t2 średnio 9 26,986 ± 0,405 us / op
MultihashTypeLookupBenchmark.testLookup 1000 t3 avgt 9 39,259 ± 1,306 us / op
MultihashTypeLookupBenchmark.testLookup 1000 h1 średnio 9 18,954 ± 0,414 us / op
MultihashTypeLookupBenchmark.testLookup 1000 h2 średnio 9 15,486 ± 0,395 us / op
MultihashTypeLookupBenchmark.testLookup 1000 h3 średnio 9 16,780 ± 0,719 us / op

Odwołanie do źródła TreeMap

https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TreeMap.java

Odniesienie do źródła HashMap

https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/HashMap.java

Venkat Karun Venugopalan
źródło
3

Możemy sprawić, że odpowiedź @assylias będzie bardziej czytelna dzięki Java8 Optional,

Optional.ofNullable(map.get(key)).ifPresent(value -> {
     //do something with value
};)
Radża
źródło
2

W Javie, jeśli sprawdzisz implementację

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

oba używają getNode do pobrania dopasowania, gdzie główna praca jest wykonywana.

redundancja jest kontekstowa, na przykład, jeśli masz słownik przechowywany na mapie skrótów. Gdy chcesz odzyskać znaczenie słowa

robić...

if(dictionary.containsKey(word)) {
   return dictionary.get(word);
}

jest zbędny.

ale jeśli chcesz sprawdzić, czy słowo jest prawidłowe lub nie na podstawie słownika. robić...

 return dictionary.get(word) != null;

nad...

 return dictionary.containsKey(word);

jest zbędny.

Jeśli zaznaczysz implementację HashSet , która używa HashMap wewnętrznie, użyj metody „ zawieraKlucz ” w metodzie „zawiera”.

    public boolean contains(Object o) {
        return map.containsKey(o);
    }
asela38
źródło