webentwicklung-frage-antwort-db.com.de

Schlüsselüberprüfung in HashMap

Ist die Überprüfung der Existenz von Schlüsseln in HashMap immer erforderlich?

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

Dies ist möglicherweise keine gute Programmierpraxis, aber es hilft mir, die Anzahl der Zugriffe zu reduzieren. Oder fehlt mir hier etwas?

[ Update ] Ich habe keine Nullwerte in der HashMap.

javahashmap
270
athena

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 prüfen Sie (könnten auf Existenz prüfen, wenn Sie einen Nullwert zurückgeben:

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
    }
}
466
Jon Skeet

Sie erhalten nichts, wenn Sie prüfen, ob der Schlüssel existiert. 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;
}

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

Dies ist der HashMap-Quellcode.

Ressourcen:

63
Colin Hebert

Besser ist es, diehälfteKey-Methode von HashMap zu verwenden. Morgen fügt die Person null zur Karte hinzu. Sie sollten zwischen dem Schlüssel dort und dem Schlüssel mit dem Wert null unterscheiden.

38
Dead Programmer

Meinen Sie, dass Sie Code wie haben

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

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

22
jkff

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

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

Die Antwort von Jon Skeet adressiert die beiden Szenarien (Karte mit null-Wert und nicht null-Wert) auf effiziente Weise.

Über die Nummerneingaben und die Effizienzfrage möchte ich noch etwas hinzufügen.

Ich habe eine HashMap mit etwa 1.000 Einträgen und bin dabei, .__ zu verbessern. Die Effizienz. Wenn auf die HashMap sehr häufig zugegriffen wird, dann Die Überprüfung der Schlüsselexistenz bei jedem Zugriff führt zu einem großen Overhead.

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

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

Wenn Sie eine Integer als Schlüsseltyp verwenden können, tun Sie es.
Die Methode hashCode() ist sehr effizient, da für eindeutige int-Werte keine Kollisionen 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 als String verwenden müssen, der beispielsweise häufig in Map verwendet wird, haben Sie zwar einige Kollisionen, aber in der Map von eintausend bis zu einigen tausend Objekten, sollten Sie nur wenige davon haben da die String.hashCode()-Methode eine gute Verteilung bietet.

Wenn Sie einen benutzerdefinierten Typ verwenden, überschreiben Sie hashCode() und equals() korrekt und stellen Sie sicher, dass hashCode() eine faire Verteilung bietet.
Sie können sich auf den Punkt 9 von Java Effective beziehen.
Hier ist ein Beitrag der den Weg beschreibt.

0
davidxxx

Ich benutze normalerweise die Redewendung

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

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

0
Jon Freedman
  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 mit falscher Implementierung der hashCode-Methode wird O (n), da Werte mit demselben Hash-Schlüssel als verknüpfte Liste gespeichert werden.
0
Boris

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

Im folgenden Beispiel speichert map eine Liste von Transaktionen (Ganzzahlen), die auf den Schlüssel angewendet werden (der Name des Bankkontos). Um 2 Transaktionen von 100 und 200 zu checking_account hinzuzufügen, können Sie 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 prüfen, ob der Schlüssel checking_account vorhanden ist oder nicht.

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

Wirklich elegant! ????

0
nazmul idris