Complessità del tempo dei metodi HashMap

Question

Poiché sto lavorando sulla complessità del tempo, ho cercato nella libreria di Oracle oracle per la complessità temporale di alcuni metodi standard utilizzati su elenchi, mappe e classi. (Più precisamente, ArrayList, HashSet e HashMap)

Ora, se si guarda al HashMap javadoc page, hanno veramente solo parlano dei metodi get() e put().

i metodi che ho ancora bisogno di sapere sono:

remove(Object o) 
size() 
values() 

penso che remove() sarà la stessa complessità get(), O(1), assumendo che non hanno un HashMap gigante con uguali codici hash, ecc ecc ..

Per size() mi piacerebbe anche assumere O(1), dal momento che un HashSet, che ha anche alcun ordine, ha un metodo size() complessità O(1).

Quello non ho idea di è values() - non sono sicuro se questo metodo sarà solo in qualche modo "copia" la HashMap, dando una complessità temporale di O(1), o se dovrà iterare il HashMap, rendendo la complessità pari alla quantità di elementi memorizzati in HashMap.

Grazie.

Answer 1

La fonte è spesso utile: http://kickjava.com/src/java/util/HashMap.java.htm

• remove: O (1)
• size: O (1)
• values: O (n) (su attraversamento attraverso iteratore)

Answer 2

Puoi sempre dare un'occhiata al codice sorgente e controllarlo da solo.
Ad ogni modo ... Una volta ho controllato il codice sorgente e quello che ricordo è che esiste una variabile denominata size che tiene sempre il numero di articoli nello HashMap quindi size() è O(1).

Answer 3

Il codice per rimuovere (come in rt.jar per HashMap) è:

/** 
* Removes and returns the entry associated with the specified key 
* in the HashMap. Returns null if the HashMap contains no mapping 
* for this key. 
*/ 
final Entry<K,V> removeEntryForKey(Object key) { 
    int hash = (key == null) ? 0 : hash(key.hashCode()); 
    int i = indexFor(hash, table.length); 
    Entry<K,V> prev = table[i]; 
    Entry<K,V> e = prev; 

    while (e != null) { 
     Entry<K,V> next = e.next; 
     Object k; 
     if (e.hash == hash && 
      ((k = e.key) == key || (key != null && key.equals(k)))) { 
      modCount++; 
      size--; 
      if (prev == e) 
       table[i] = next; 
      else 
       prev.next = next; 
      e.recordRemoval(this); 
      return e; 
     } 
     prev = e; 
     e = next; 
    } 

    return e; 
} 

Chiaramente, il caso peggiore è O (n).

Answer 4

Ricerca: O (1 + k/n)
Inserire: O (1)
Delete: O (1 + k/n) dove k è il no. di elementi di collisione aggiunti allo stesso LinkedList (k elementi avevano stessa hashCode)

inserimento è O (1), perché si aggiunge l'elemento a destra alla testa di LinkedList.

Le complessità del tempo ammortizzato sono vicine a O (1) data una buona funzione hash. Se sei troppo preoccupato per il tempo di ricerca, prova a risolvere le collisioni usando un BinarySearchTree invece dell'implementazione predefinita di java ie LinkedList