Hola usuario de nuestra web, hemos encontrado la respuesta a tu pregunta, continúa leyendo y la verás a continuación.
Solución:
Creo que estás haciendo la pregunta equivocada. La complejidad espacial de una estructura de datos indica cuánto espacio ocupa en relación con la cantidad de elementos que contiene. Por ejemplo, una complejidad espacial de O(1) significaría que la estructura de datos siempre consume espacio constante sin importar cuántos elementos coloque allí. O(n) significaría que el consumo de espacio crece linealmente con la cantidad de elementos en él.
Una tabla hash normalmente tiene una complejidad de espacio de O(n).
Entonces, para responder a su pregunta: depende de la cantidad de elementos que almacene actualmente y, en el mundo real, también de la implementación real.
Un límite inferior para el consumo de memoria de su tabla hash es: (Número de valores para almacenar) * (Tamaño de un valor). Entonces, si desea almacenar 1 millón de valores en la tabla hash y cada uno ocupa 4 bytes, consumirá al menos 4 millones de bytes (aproximadamente 4 MB). Por lo general, las implementaciones del mundo real usan un poco más de memoria para la infraestructura, pero de nuevo: esto depende en gran medida de la implementación real y no hay forma de saberlo con seguridad más que medirlo.
Las tablas hash no coinciden con los valores y las ranuras de la función hash. La función hash se calcula módulo el tamaño de un vector de referencia que es mucho más pequeño que el rango de la función hash. Debido a que este valor es fijo, no se considera en el cálculo de la complejidad del espacio.
En consecuencia, la complejidad espacial de cada tabla hash razonable es En).
En general, esto funciona bastante bien. Mientras que la key el espacio puede ser grande, el número de valores a almacenar suele ser bastante fácil de predecir. Ciertamente, la cantidad de memoria que es funcionalmente aceptable para la sobrecarga de la estructura de datos suele ser obvia.
Esta es la razón por la cual las tablas hash son tan omnipresentes. Suelen proporcionar la mejor estructura de datos para una tarea dada, mezclando una sobrecarga de memoria estrictamente limitada con mejor que el registro.2norte complejidad del tiempo. Me encantan los árboles binarios, pero no suelen vencer a las tablas hash.
Supongamos que tenemos una tabla hash ingenua donde el número de cubos es igual al doble del tamaño de los elementos. Eso es O(2n) el número de elementos que es O(n).
Cuando la cantidad de elementos supera la mitad de la cantidad de cubos disponibles, debe crear una nueva array de cubos, duplique el tamaño y vuelva a colocar todos los elementos en sus nuevas ubicaciones en el nuevo array de baldes
386 public V put(K key, V value)
387 if (key == null)
388 return putForNullKey(value);
389 int hash = hash(key.hashCode());
390 int i = indexFor(hash, table.length);
391 for (Entry e = table[i]; e != null; e = e.next) key.equals(k)))
394 V oldValue = e.value;
395 e.value = value;
396 e.recordAccess(this);
397 return oldValue;
398
399
401 modCount++;
402 addEntry(hash, key, value, i);
403 return null;
404
768 void addEntry(int hash, K key, V value, int bucketIndex)
769 Entry e = table[bucketIndex];
770 table[bucketIndex] = new Entry(hash, key, value, e);
771 if (size++ >= threshold)
772 resize(2 * table.length);
773
471 void resize(int newCapacity)
472 Entry[] oldTable = table;
473 int oldCapacity = oldTable.length;
474 if (oldCapacity == MAXIMUM_CAPACITY)
475 threshold = Integer.MAX_VALUE;
476 return;
477
479 Entry[] newTable = new Entry[newCapacity];
480 transfer(newTable);
481 table = newTable;
482 threshold = (int)(newCapacity * loadFactor);
483
488 void transfer(Entry[] newTable)
489 Entry[] src = table;
490 int newCapacity = newTable.length;
491 for (int j = 0; j < src.length; j++)
492 Entry e = src[j];
493 if (e != null)
494 src[j] = null;
495 do
496 Entry next = e.next;
497 int i = indexFor(e.hash, newCapacity);
498 e.next = newTable[i];
499 newTable[i] = e;
500 e = next;
501 while (e != null);
502
503
504
Referencias:
HashMap.put
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.put%28java.lang.Object%2Cjava.lang. Objeto%29
Grepcode está caído, puede echar un vistazo al repositorio de openjdk aquí como una mejor referencia: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/ HashMap.java
No se te olvide comunicar este post si te fue útil.