Ricerca mappa Efficienza di TestForNull

Question

Referencing a previous answer to a question on SO, esiste un metodo chiamato TestForNull. Questo era il mio codice originale prima che mi è stato detto che potrei renderlo più efficiente:

mio codice originale:

for (int i = 0; i < temp.length; i++) { 
      if (map.containsKey(temp[i])) 
       map.put(temp[i], map.get(temp[i]) + 1); 
      else 
       map.put(temp[i], 1); 

In questo frammento di codice, che sto facendo tre look-up per la mappa. Mi è stato detto che questo potrebbe essere realizzato in una sola occhiata, così ho finito per cercare una risposta su SO e trovato la risposta legata, e modificato il mio codice a guardare come:

mio codice modificato:

for (int i = 0; i < temp.length; i++) { 
      Integer value = map.get(temp[i]); 
      if (value != null) 
       map.put(temp[i], value + 1); 
      else 
       map.put(temp[i], 1); 
     } 

Anche se sembra meglio, sembra due lookup per me e non per uno. Mi chiedevo se ci fosse un'implementazione di questa che ne utilizza solo una e se può essere fatta senza l'uso di librerie di terze parti. Se aiuta, sto usando una HashMap per il mio programma.

Answer 1

Java 8 ha aggiunto un certo numero di default metodi all'interfaccia Map che potrebbe aiutare, tra merge:

map.merge(temp[i], 1, v -> v + 1); 

E compute:

map.compute(temp[i], (k, v) -> v == null ? 1 : v + 1); 

HashMap's implementations of these methods sono opportunamente ottimizzate efficacemente eseguire solo un ricerca chiave singola. (Curiosamente, lo stesso non si può dire per TreeMap.)

Answer 2

@John La risposta di Kugelman è la migliore (purché sia ​​possibile utilizzare java 8).

Il primo esempio è un caso peggiore di 3 chiamate mappa (nel caso di un valore già presente):

1. containsKey
2. ottenere
3. messo

Il secondo esempio ha sempre esattamente 2 chiamate (e un controllo Null):

1. ottenere
2. messo

Così si sono fondamentalmente negoziazione containsKey per un controllo nullo.

In un HashMap, queste operazioni sono approssimativamente costanti, presupponendo una buona distribuzione del codice hash (e che la distribuzione funzioni correttamente con le dimensioni dello HashMap). Altre implementazioni Map (come TreeMap) hanno il tempo di esecuzione del log (n). Anche nel caso di HashMap, un controllo Null sarà più veloce di containsKey, rendendo la seconda opzione il vincitore. Tuttavia, è improbabile che si verifichi una differenza misurabile a meno che non si disponga di codici hash scarsamente distribuiti (o questa è l'unica cosa che l'applicazione sta facendo) o di controlli uguali con scarse prestazioni.