Verifica esistenza chiave in HashMap

Question

Il controllo dell'esistenza della chiave in HashMap è sempre necessario?

Ho una HashMap con diciamo un 1000 voci e sto cercando di migliorare l'efficienza. Se l'accesso a HashMap viene eseguito molto frequentemente, la ricerca dell'esistenza della chiave ad ogni accesso determinerà un notevole sovraccarico. Invece se la chiave non è presente e quindi si verifica un'eccezione, posso rilevare l'eccezione. (quando so che questo accadrà raramente). Ciò ridurrà la metà degli accessi a HashMap.

Questa potrebbe non essere una buona pratica di programmazione, ma mi aiuterà a ridurre il numero di accessi. O mi sto perdendo qualcosa qui?

[Aggiornamento] Non ho valori Null in HashMap.

Answer 1

Avete mai archiviato un valore nullo? In caso contrario, si può solo fare:

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

In caso contrario, si potrebbe basta controllare per l'esistenza, se si ottiene un valore nullo restituito:

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

Answer 2

io di solito uso l'idioma

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

Questo significa che si preme due volte la mappa solo se manca la chiave

Answer 3

Vuoi dire che hai il codice come

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

tutto il luogo? Quindi dovresti semplicemente verificare se map.get(key) ha restituito null e il gioco è fatto. A proposito, HashMap non lancia eccezioni per le chiavi mancanti, restituisce invece null. L'unico caso in cui è necessario containsKey è quando si memorizzano valori nulli, per distinguere tra un valore nullo e un valore mancante, ma di solito è considerato una cattiva pratica.

Answer 4

Non otterrai nulla controllando che la chiave esista. Questo è il codice di 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; 
} 

Basta controllare se il valore restituito per get() è diverso da null.

Questo è il codice sorgente HashMap.

---

Risorse:

• HashMap source code Bad uno
• HashMap source code Good one

Answer 5

1. Se la classe chiave è la vostra di assicurarsi che il hashCode() e equals () metodi implementato.
2. Fondamentalmente l'accesso a HashMap deve essere O (1) ma con un'implementazione del metodo hashCode errato diventa O (n), poiché il valore con la stessa chiave hash verrà memorizzato come Elenco collegato.

Answer 6

Il modo migliore è utilizzare il metodo containsKey di HashMap. Domani soembody aggiungerà null alla mappa, dovresti distinguere tra la chiave lì e la chiave ha valore nullo.

Answer 7

Basta usare containsKey() per chiarezza. È veloce e mantiene il codice pulito e leggibile. L'intero punto di HashMap s è che la ricerca della chiave è veloce, basta assicurarsi che lo hashCode() e lo equals() siano implementati correttamente.

Answer 8

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

Answer 9

The Jon Skeet answer indirizzi bene i due scenari (mappa con null valore e non null valore) in modo efficiente.

Circa le voci di numero e il problema di efficienza, vorrei aggiungere qualcosa.

Ho una HashMap con diciamo 1.000 voci e sto cercando di migliorare l'efficienza. Se si accede a HashMap molto frequentemente, il controllo per l'esistenza della chiave ad ogni accesso comporterà un grande overhead .

Una mappa con 1.000 voci non è una mappa enorme.
Così come una mappa con 5.000 o 10.000 voci.
Map sono progettati per effettuare il recupero rapido con tali dimensioni.

Ora, si presume che hashCode() delle chiavi della mappa fornisca una buona distribuzione.

Se è possibile utilizzare un Integer come tipo di chiave, farlo.
Il suo metodo hashCode() è molto efficiente dal momento che le collisioni non sono possibili per unici int valori:

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

Se per la chiave, è necessario utilizzare un altro tipo built-in come String per esempio che viene spesso utilizzato in Map , potresti avere delle collisioni ma da 1mila a qualche migliaio di oggetti nel numero Map, dovresti averne pochissime in quanto il metodo String.hashCode() fornisce una buona distribuzione.

Se si utilizza un tipo personalizzato, ignorare hashCode() e equals() correttamente e assicurarsi generale che hashCode() fornisce una distribuzione equa.
È possibile fare riferimento all'articolo 9 di Java Effective.
Ecco uno post che descrive la via.