¿Cuál es la complejidad de tiempo de HashMap.containsKey() en java?

Necesito saber: ¿Cuál es la complejidad temporal de HashMap.containsKey() en java?¿Cuál es la complejidad de tiempo de HashMap.containsKey() en java?

Fuente

2012-01-19 Hossein

@OlegSklyar Esta pregunta me ha ayudado porque tenía que poner en práctica un HashMap yo mismo. – trinity420

@ trinity420 ¿Esto justifica no leer la documentación de la API cuando tienes una pregunta sobre la API? –

Desde el API doc ofHashMap:

Esta aplicación proporciona un rendimiento constante en el tiempo para los operaciones básicas (obtener y poner), suponiendo que la función hash dispersa los elementos correctamente entre los depósitos.

Desde containsKey() es sólo un get() que tira a la basura el valor recuperado, es O (1) (suponiendo que la función hash funciona correctamente, de nuevo).

Fuente

2012-01-19 08:54:01

esto es lo que pensé antes. Pero no es correcto Echa un vistazo a la respuesta de Jigar Joshi. Su respuesta es correcta para 'Hashtable' que no permite valores nulos. – AlexR

@AlexR: Creo que estás malinterpretando por completo el código en la respuesta de Jigar. No tiene absolutamente nada que ver con valores nulos, y el bucle for solo recorre la lista de entradas enlazadas en un único contenedor, que es O (1) si, como dije dos veces en mi respuesta, la función hash hace su trabajo. –

Si consigo elegir las claves que ya están en el mapa, es O (n). –

Es O(1) en general, sin embargo, en el peor caso es O(n)

public boolean containsKey(Object key) { 
    352   return getEntry(key) != null; 
    353  } 
    354 
    355  /** 
    356  * Returns the entry associated with the specified key in the 
    357  * HashMap. Returns null if the HashMap contains no mapping 
    358  * for the key. 
    359  */ 
    360  final Entry<K,V> getEntry(Object key) { 
    361   int hash = (key == null) ? 0 : hash(key.hashCode()); 
    362   for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
    363    e != null; 
    364    e = e.next) { 
    365    Object k; 
    366    if (e.hash == hash && 
    367     ((k = e.key) == key || (key != null && key.equals(k)))) 
    368     return e; 
    369   } 
    370   return null; 
    371  }

Fuente

2012-01-19 08:53:18

Eso sería 'Ω (1)' y 'O (n)' luego. – Viruzzo

Ver Answer by mishadoff para una explicación del peor caso. – cellepo

Generalmente O (1), pero si estamos usando una mala función hashCode, necesitamos agregar varios elementos a un cubo para que pueda ser O (n) en el peor de los casos.

Fuente

2012-01-19 08:54:38 mishadoff

La complejidad del tiempo de containsKey ha cambiado en JDK 1.8-, como otros han dicho que es O(1) en casos ideales. Sin embargo, en caso de colisiones en el que el keys son Comparable, contenedores de almacenamiento de elementos chocan no son lineales más después de que superen un umbral llamado TREEIFY_THRESHOLD, que es igual a 8,

/** 
* The bin count threshold for using a tree rather than list for a 
* bin. Bins are converted to trees when adding an element to a 
* bin with at least this many nodes. The value must be greater 
* than 2 and should be at least 8 to mesh with assumptions in 
* tree removal about conversion back to plain bins upon 
* shrinkage. 
*/ 
static final int TREEIFY_THRESHOLD = 8;

En otras palabras, se utilizará TreeNodes (similar a los de TreeMap) para almacenar contenedores (es decir, una estructura de árbol rojo-negro) y esto nos deja con una complejidad O(lgn) en caso de colisiones.

Lo mismo se aplica para get(key) en donde ambos métodos llaman getNode internamente

Nota: n aquí es el tamaño de la bin y no HashMap

Fuente

2015-12-31 11:41:28

¿Cuál es la complejidad de tiempo de HashMap.containsKey() en java?

Respuesta

Cuestiones relacionadas