Überprüfung der Schlüsselexistenz in HashMap

309

Ist eine Überprüfung der Schlüsselexistenz in HashMap immer erforderlich?

Ich habe eine HashMap mit beispielsweise 1000 Einträgen und möchte die Effizienz verbessern. Wenn sehr häufig auf die HashMap zugegriffen wird, führt die Überprüfung der Schlüsselexistenz bei jedem Zugriff zu einem hohen Overhead. Wenn der Schlüssel nicht vorhanden ist und daher eine Ausnahme auftritt, kann ich die Ausnahme abfangen. (wenn ich weiß, dass dies selten passieren wird). Dadurch wird der Zugriff auf die HashMap um die Hälfte reduziert.

Dies ist möglicherweise keine gute Programmierpraxis, hilft mir jedoch dabei, die Anzahl der Zugriffe zu verringern. Oder fehlt mir hier etwas?

[ Update ] Ich habe keine Nullwerte in der HashMap.

Athena
quelle
8
"daher und Ausnahme tritt auf" - welche Ausnahme? Dies wird nicht von java.util.HashMap sein ...
serg10

Antworten:

513

Speichern Sie jemals einen Nullwert? Wenn nicht, können Sie einfach Folgendes tun:

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

Andernfalls Sie könnten nur die Existenz , wenn Sie einen Nullwert zurück erhalten:

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
quelle
1
@Samuel: Nur wenn null ein möglicher Wert ist. Wenn Sie definitiv keine Nullwerte in der Karte haben, getist dies in Ordnung und vermeidet zwei Suchvorgänge, wenn Sie den Wert ebenfalls benötigen.
Jon Skeet
Obwohl dies als Beispiel wahrscheinlich klarer ist, könnten Sie auch if(value!=null || map.containsKey(key))für den zweiten Teil schreiben . Zumindest, wenn Sie dasselbe tun möchten - kein wiederholter Code. Es wird aufgrund eines Kurzschlusses funktionieren .
Cullub
66

Sie erhalten nichts, wenn Sie überprüfen, ob der Schlüssel vorhanden ist. Dies ist der Code von 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;
}

Überprüfen Sie einfach, ob sich der Rückgabewert für von get()unterscheidet null.

Dies ist der HashMap-Quellcode.


Ressourcen:

Colin Hebert
quelle
2
Was bringt es, eine bestimmte Implementierung dieser Methoden zu zeigen?
jarnbjo
2
Um dies zu erklären, dauert die Überprüfung, ob der Schlüssel vorhanden ist, in den meisten Fällen ungefähr dieselbe Zeit wie das Abrufen des Werts. Es wird also nichts optimiert, um zu überprüfen, ob der Schlüssel tatsächlich vorhanden ist, bevor der Wert abgerufen wird. Ich weiß, dass es eine Verallgemeinerung ist, aber es kann helfen, zu verstehen.
Colin Hebert
Ein guter Link ist grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… (OpenJDK ist sehr stark vom Sun-Code abgeleitet) und es scheint, dass ich falsch liege . Ich habe die Version für Java5 mit Java6 verglichen. Sie funktionieren in diesem Bereich unterschiedlich (aber beide sind korrekt, ebenso wie die von Ihnen geposteten Snippets).
Donal Fellows
2
Wie in der akzeptierten Antwort ausgeführt, ist dieser Snawer einfach falsch. Natürlich gewinnen Sie etwas, indem Sie die Schlüsselexistenz prüfen oder Werte vergleichen - Sie können nicht vorhandene Schlüssel von vorhandenen Schlüsseln unterscheiden, die jedoch als Wert auf Null abgebildet sind.
Johannes H.
43

Besser ist es zu benutzen containsKey Methode von zu verwenden HashMap. Morgen wird jemand der Karte null hinzufügen. Sie sollten zwischen Schlüsselpräsenz und Schlüssel mit dem Wert Null unterscheiden.

Toter Programmierer
quelle
Ja. Oder unterklassifizieren Sie die HashMap, um zu verhindern, dass nullalles zusammen gespeichert wird.
RobAu
1
1+ für primitive Typen als Wert unnötige Besetzung ist nicht erforderlich mit dieser Antwort
Prashant Bhanarkar
Es ist auch fließender, .containsKey () zu schreiben, als nach null zu suchen. Wir sollten uns mehr darum kümmern, einfach zu lesen zu sein, was Entwicklern Zeit spart, als in den meisten Fällen um kleinere Optimierungen. Zumindest nicht optimieren, bevor es notwendig wird.
Max
23

Meinst du, dass du Code wie hast?

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

überall ? Dann sollten Sie einfach prüfen, ob map.get(key)null zurückgegeben wurde und das wars. Übrigens löst HashMap keine Ausnahmen für fehlende Schlüssel aus, sondern gibt stattdessen null zurück. Der einzige Fall, in dem dies containsKeyerforderlich ist, ist das Speichern von Nullwerten, um zwischen einem Nullwert und einem fehlenden Wert zu unterscheiden. Dies wird jedoch normalerweise als schlechte Vorgehensweise angesehen.

jkff
quelle
8

Nur containsKey()zur Klarheit verwenden. Es ist schnell und hält den Code sauber und lesbar. Der springende Punkt bei HashMaps ist, dass die Schlüsselsuche schnell ist. Stellen Sie einfach sicher, dass die hashCode()und equals()ordnungsgemäß implementiert sind.

Mikko Wilkman
quelle
4
if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))
Erlan
quelle
3

Sie können die computeIfAbsent()Methode auch in der HashMapKlasse verwenden.

Im folgenden Beispiel wird mapeine Liste von Transaktionen (Ganzzahlen) gespeichert, die auf den Schlüssel (den Namen des Bankkontos) angewendet werden. Um 2 Transaktionen von 100und 200zu hinzufügen , können checking_accountSie schreiben:

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

Auf diese Weise müssen Sie nicht überprüfen, ob der Schlüssel checking_accountvorhanden ist oder nicht.

  • Wenn es nicht existiert, wird einer vom Lambda-Ausdruck erstellt und zurückgegeben.
  • Wenn es existiert, wird der Wert für den Schlüssel von zurückgegeben computeIfAbsent().

Wirklich elegant! 👍

Nazmul Idris
quelle
0

Normalerweise benutze ich die Redewendung

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

Dies bedeutet, dass Sie die Karte nur zweimal treffen, wenn der Schlüssel fehlt

Jon Freedman
quelle
0
  1. Wenn Sie eine Schlüsselklasse haben, stellen Sie sicher, dass die Methoden hashCode () und equals () implementiert sind.
  2. Grundsätzlich sollte der Zugriff auf HashMap O (1) sein, aber bei falscher Implementierung der HashCode-Methode wird er zu O (n), da der Wert mit demselben Hash-Schlüssel als verknüpfte Liste gespeichert wird.
Boris
quelle
0

Die Antwort von Jon Skeet spricht die beiden Szenarien (Karte mit nullWert und nicht nullWert) auf effiziente Weise gut an.

Über die Nummerneinträge und das Effizienzproblem möchte ich noch etwas hinzufügen.

Ich habe eine HashMap mit beispielsweise 1.000 Einträgen und möchte die Effizienz verbessern. Wenn sehr häufig auf die HashMap zugegriffen wird, führt die Überprüfung der Schlüsselexistenz bei jedem Zugriff zu einem hohen Overhead.

Eine Karte mit 1.000 Einträgen ist keine riesige Karte.
Sowie eine Karte mit 5.000 oder 10.000 Einträgen.
Mapsind so konzipiert, dass sie mit solchen Abmessungen schnell abgerufen werden können.

Nun wird davon ausgegangen, dass hashCode()der Kartenschlüssel eine gute Verteilung bietet.

Wenn Sie einen IntegerSchlüsseltyp als verwenden können, tun Sie dies.
Die hashCode()Methode ist sehr effizient, da die Kollisionen für eindeutige intWerte nicht möglich sind:

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

Wenn Sie für den Schlüssel einen anderen integrierten Typ verwenden müssen, wie Stringer beispielsweise häufig verwendet wird Map, können einige Kollisionen auftreten, aber von 1 Tausend bis zu einigen Tausend Objekten in der Mapsollten Sie nur sehr wenige davon als String.hashCode()Methode verwenden bietet eine gute Verteilung.

Wenn Sie einen benutzerdefinierten Typ verwenden, überschreiben hashCode()und equals()korrigieren Sie ihn und stellen Sie insgesamt sicher, dass hashCode()eine faire Verteilung gewährleistet ist .
Sie können sich auf Punkt 9 Java Effectivebeziehen.
Hier ist ein Beitrag , der den Weg beschreibt.

davidxxx
quelle