Sprawdzanie istnienia klucza w HashMap

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.

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
    }
}

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 :

• Kod źródłowy HashMap Zły
• Kod źródłowy HashMap Dobry

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.

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ę.

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.

if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))

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! 👍

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

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.

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.