Sprawdzanie istnienia klucza w HashMap

309

Czy sprawdzanie istnienia klucza w HashMap jest zawsze konieczne?

Mam HashMap z powiedzmy 1000 wpisów i szukam poprawy wydajności. Jeśli dostęp do HashMap jest uzyskiwany bardzo często, sprawdzanie istnienia klucza przy każdym dostępie spowoduje duże obciążenie. Zamiast tego, jeśli klucz nie jest obecny i stąd występuje wyjątek, mogę go złapać. (kiedy wiem, że to się zdarza rzadko). Spowoduje to zmniejszenie dostępu do HashMap o połowę.

To może nie być dobra praktyka programowania, ale pomoże mi zmniejszyć liczbę dostępów. A może coś tu brakuje?

[ Aktualizacja ] Nie mam wartości zerowych w HashMap.

atena
źródło
8
„stąd i wyjątek występuje” - jaki wyjątek? To nie będzie z java.util.HashMap ...
serg10

Odpowiedzi:

513

Czy kiedykolwiek przechowujesz wartość zerową? Jeśli nie, możesz po prostu:

Foo value = map.get(key);
if (value != null) {
    ...
} else {
    // No such key
}

W przeciwnym razie mogłyby po prostu sprawdzić na istnienie, jeśli uzyska wartość NULL zwracane:

Foo value = map.get(key);
if (value != null) {
    ...
} else {
    // Key might be present...
    if (map.containsKey(key)) {
       // Okay, there's a key but the value is null
    } else {
       // Definitely no such key
    }
}
Jon Skeet
źródło
1
@ Samuel: Tylko gdy możliwa jest wartość null. Jeśli zdecydowanie nie masz wartości zerowych na mapie, po prostu getjest w porządku i unikasz wykonywania dwóch przeglądów, gdy potrzebujesz także wartości.
Jon Skeet,
Chociaż jest to prawdopodobnie bardziej zrozumiałe jako przykład, możesz również napisać if(value!=null || map.containsKey(key))dla drugiej części. Przynajmniej jeśli chcesz zrobić to samo w obu przypadkach - bez powtarzającego się kodu. Będzie działać z powodu zwarcia .
Cullub,
66

Nic nie zyskasz, sprawdzając, czy klucz istnieje. To jest kod HashMap:

@Override
public boolean containsKey(Object key) {
    Entry<K, V> m = getEntry(key);
    return m != null;
}

@Override
public V get(Object key) {
    Entry<K, V> m = getEntry(key);
    if (m != null) {
        return m.value;
    }
    return null;
}

Wystarczy sprawdzić, czy zwracana wartość dla get()jest inna niż null.

To jest kod źródłowy HashMap.


Zasoby :

Colin Hebert
źródło
2
Po co pokazywać jedną konkretną implementację tych metod?
jarnbjo
2
Aby wyjaśnić, że w większości przypadków sprawdzenie, czy klucz istnieje, zajmie mniej więcej tyle samo czasu, co uzyskanie wartości. Więc nie zoptymalizuje niczego, aby sprawdzić, czy klucz rzeczywiście istnieje przed uzyskaniem wartości. Wiem, że to uogólnienie, ale może pomóc zrozumieć.
Colin Hebert
Dobrym linkiem jest grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… (OpenJDK jest bardzo silnie pochodną kodu Sun) i wygląda na to, że się mylę. Porównywałem wersję dla Java5 z Java6; działają one inaczej w tym obszarze (ale oba są poprawne, podobnie jak fragmenty, które opublikowałeś).
Donal Fellows,
2
Jak wskazano w przyjętej odpowiedzi, ten snawer jest po prostu błędny. Oczywiście, że coś zyskujesz, sprawdzając, czy klucz istnieje, porównując wartości - możesz odróżnić nieistniejące klucze od kluczy, które istnieją, ale są zamapowane na wartość null.
Johannes H.
43

Lepszym sposobem jest użycie containsKeymetody HashMap. Jutro ktoś doda null do mapy. Należy odróżnić obecność klucza od klucza o wartości zerowej.

Dead Programmer
źródło
Tak. Lub podklasę HashMap, aby zapobiec nullcałkowitemu przechowywaniu .
RobAu
1
1+ dla typów prymitywnych, ponieważ niepotrzebne
przekazywanie
Bardziej płynne jest pisanie .containsKey () niż sprawdzanie wartości null. Powinniśmy bardziej martwić się o łatwość czytania, która oszczędza czas programistów, niż o drobną optymalizację w większości przypadków. Przynajmniej nie optymalizuj, zanim stanie się to konieczne.
maks.
23

Czy masz na myśli, że masz kod podobny do tego?

if(map.containsKey(key)) doSomethingWith(map.get(key))

wszędzie wokoło ? Następnie powinieneś po prostu sprawdzić, czy map.get(key)zwrócił wartość null i to wszystko. Nawiasem mówiąc, HashMap nie zgłasza wyjątków dla brakujących kluczy, zamiast tego zwraca null. Jedynym przypadkiem, w którym containsKeyjest to potrzebne, jest przechowywanie wartości zerowych w celu odróżnienia wartości zerowej od wartości brakującej, ale zwykle uważa się to za złą praktykę.

jkff
źródło
8

Po prostu użyj containsKey()dla jasności. Jest szybki i utrzymuje kod w czystości i czytelności. Chodzi o HashMapto, że wyszukiwanie klucza jest szybkie, po prostu upewnij się, że hashCode()i equals()są poprawnie zaimplementowane.

Mikko Wilkman
źródło
4
if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))
Erlan
źródło
3

Możesz także użyć tej computeIfAbsent()metody wHashMap klasie.

W poniższym przykładzie mapprzechowuje listę transakcji (liczb całkowitych), które są stosowane do klucza (nazwa konta bankowego). Aby dodać 2 transakcje 100i 200do checking_accountmożna napisać:

HashMap<String, ArrayList<Integer>> map = new HashMap<>();
map.computeIfAbsent("checking_account", key -> new ArrayList<>())
   .add(100)
   .add(200);

W ten sposób nie musisz sprawdzać, czy klucz checking_accountistnieje, czy nie.

  • Jeśli nie istnieje, zostanie utworzony i zwrócony przez wyrażenie lambda.
  • Jeśli istnieje, wartość klucza zostanie zwrócona przez computeIfAbsent().

Naprawdę elegancki! 👍

nazmul idris
źródło
0

Zwykle używam tego idiomu

Object value = map.get(key);
if (value == null) {
    value = createValue(key);
    map.put(key, value);
}

Oznacza to, że uderzyłeś w mapę tylko dwa razy, jeśli brakuje klucza

Jon Freedman
źródło
0
  1. Jeśli należysz do klasy kluczy, upewnij się, że zaimplementowano metody hashCode () i equals ().
  2. Zasadniczo dostęp do HashMap powinien wynosić O (1), ale przy niewłaściwej implementacji metody hashCode staje się O (n), ponieważ wartość z tym samym kluczem skrótu zostanie zapisana jako lista połączona.
Boris
źródło
0

Odpowiedź Jona Skeeta dobrze odnosi się do dwóch scenariuszy (mapa z nullwartością, a nie nullwartością) w efektywny sposób.

Jeśli chodzi o wpisy liczbowe i problem z wydajnością, chciałbym coś dodać.

Mam HashMap z, powiedzmy, 1000 pozycji i szukam poprawy wydajności. Jeśli dostęp do HashMap jest uzyskiwany bardzo często, sprawdzanie istnienia klucza przy każdym dostępie spowoduje duże obciążenie.

Mapa z 1000 wpisów nie jest wielką mapą.
Jak również mapa z 5.000 lub 10.000 wpisów.
Mapsą zaprojektowane do szybkiego wyszukiwania przy takich wymiarach.

Teraz zakłada się, że hashCode()z klawiszy mapy zapewnia dobrą dystrybucję.

Jeśli możesz użyć Integerjako typu klucza, zrób to.
Ta hashCode()metoda jest bardzo wydajna, ponieważ kolizje nie są możliwe dla unikalnych intwartości:

public final class Integer extends Number implements Comparable<Integer> {
    ...
    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }

    public static int hashCode(int value) {
        return value;
    }
    ...
}

Jeśli dla klucza musisz użyć innego wbudowanego typu, jak Stringna przykład często używany Map, możesz mieć pewne kolizje, ale od 1 tysiąca do kilku tysięcy obiektów w Map, powinieneś mieć ich bardzo mało jako String.hashCode()metodę zapewnia dobrą dystrybucję.

Jeśli używasz niestandardowego typu, zastąp hashCode()i equals()poprawnie, i upewnij się, że ogólnie hashCode()zapewnia to sprawiedliwą dystrybucję.
Możesz odnieść się do punktu 9, Java Effectivedotyczy go.
Oto post, który szczegółowo opisuje sposób.

davidxxx
źródło