Complejidad del tiempo de los métodos de HashMap

Question

Como estoy trabajando en la complejidad del tiempo, he estado buscando en la biblioteca de la clase Oracle de Oracle la complejidad temporal de algunos métodos estándar utilizados en las listas, los mapas y las clases. (Más específicamente, ArrayList, HashSet y HashMap)

Ahora, cuando se mira en el HashMap javadoc page, en realidad sólo hablan de los métodos get() y put().

los métodos que todavía necesita saber son:

remove(Object o) 
size() 
values() 

creo que remove() será la misma complejidad que get(), O(1), suponiendo que no tienen un HashMap gigante con iguales hashcodes, etc etc. ..

Para size() también me asumir O(1), ya que un HashSet, que también tiene ningún orden, tiene un método size() con la complejidad O(1).

El que no tengo ni idea de es values() - No estoy seguro de si este método se acaba de alguna manera "ejemplar" el HashMap, dando un tiempo de complejidad O(1), o si tendrá que repetir el HashMap, haciendo la complejidad es igual a la cantidad de elementos almacenados en HashMap.

Gracias.

Answer 1

la fuente es a menudo útil: http://kickjava.com/src/java/util/HashMap.java.htm

• remove: O (1)
• size: O (1)
• values: O (n) (en el recorrido a través de iterador)

Answer 2

Siempre puede echar un vistazo al código fuente y comprobarlo usted mismo.
De todos modos ... Una vez revisé el código fuente y lo que recuerdo es que hay una variable llamada size que siempre contiene el número de elementos en el HashMap así que size() es O(1).

Answer 3

El código para eliminar (como en rt.jar para HashMap) es:

/** 
* 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; 
} 

Claramente, el peor de los casos es O (n).

Answer 4

Buscar: O (1 + k/n)
Insertar: O (1)
Eliminar: O (1 + k/n) donde k es el no. de los elementos de colisión añadidos a la misma lista LinkedList (los elementos k tenían el mismo hashCode)

La inserción es O (1) porque agrega el elemento justo al principio de LinkedList.

Las complejidades de tiempo amortiguado son cerca de O (1) dado un buen hashFunction. Si está demasiado preocupado por el tiempo de búsqueda, intente resolver las colisiones utilizando un BinarySearchTree en lugar de la implementación predeterminada de java ie LinkedList