java - diferencia - arraylist vs linkedlist

Tamaño máximo de HashSet, Vector, LinkedList

Question

¿Cuál es el tamaño máximo de HashSet , Vector , LinkedList ? Sé que ArrayList puede almacenar más de 3277000 números.

Sin embargo, el tamaño de la lista depende del tamaño de la memoria (pila). Si alcanza el máximo, el JDK arroja un OutOfMemoryError .

Pero no conozco el límite para la cantidad de elementos en HashSet , Vector y LinkedList .

Answer 1

Como se indica en otras respuestas, una matriz no puede alcanzar 2 ^ 31 entradas. Otros tipos de datos están limitados por esto o es probable que denuncien erróneamente su tamaño (). Sin embargo, estos límites teóricos no se pueden alcanzar en algunos sistemas:

En un sistema de 32 bits, el número de bytes disponibles nunca excede 2 ^ 32 exactamente. Y eso es asumiendo que no tienes un sistema operativo que ocupe memoria. Un puntero de 32 bits tiene 4 bytes. Todo lo que no dependa de las matrices debe incluir al menos un puntero por entrada: esto significa que el número máximo de entradas es 2 ^ 32/4 o 2 ^ 30 para las cosas que no utilizan matrices.

Una matriz simple puede alcanzar su límite teórico, pero solo una matriz de bytes, una matriz corta de longitud 2 ^ 31-1 usaría aproximadamente 2 ^ 32 + 38 bytes.

Algunas máquinas virtuales Java han introducido un nuevo modelo de memoria que utiliza punteros comprimidos. Al ajustar la alineación del puntero, se puede hacer referencia a un poco más de 2 ^ 32 bytes con punteros de 32 bytes. Alrededor de cuatro veces más. Esto es suficiente para causar que un tamaño de LinkedList () se vuelva negativo, pero no lo suficiente como para permitir que se ajuste a cero.

Un sistema de sesenta y cuatro bits tiene punteros de sesenta y cuatro bits, lo que hace que todos los punteros sean dos veces más grandes, lo que hace que las listas que no sean de matriz sean más voluminosas. Esto también significa que la capacidad máxima admitida salta exactamente a 2 ^ 64 bytes. Esto es suficiente para que una matriz 2D alcance su máximo teórico. byte [0x7fffffff] [0x7fffffff] usa memoria aproximadamente igual a 40 + 40 * (2 ^ 31-1) + (2 ^ 31-1) (2 ^ 31-1) = 40 + 40 (2 ^ 31-1) + (2 ^ 62-2 ^ 32 + 1)

Answer 2

Depende mucho de los detalles de implementación.

Un HashSet usa una matriz como una tienda subyacente que, de forma predeterminada, intenta crecer cuando la colección está llena en un 75%. Esto significa que fallará si intenta agregar más de 750,000,000 de entradas. (No puede hacer crecer la matriz de 2 ^ 30 a 2 ^ 31 entradas)

Aumentar el factor de carga aumenta el tamaño máximo de la colección. por ejemplo, un factor de carga de 10 permite 10 mil millones de elementos. (Vale la pena señalar que HashSet es relativamente ineficiente más allá de los 100 millones de elementos, ya que la distribución del código hash de 32 bits comienza a verse menos aleatoria, y el número de colisiones aumenta)

Un Vector duplica su capacidad y comienza en 10. Esto significa que no crecerá por encima de aproximadamente 1.340 millones. Cambiando el tamaño inicial a 2 ^ n-1 le da un poco más de espacio para la cabeza.

Por cierto: utilice ArrayList en lugar de Vector si puede.

Una LinkedList no tiene límite inherente y puede crecer más allá de 2.1 mil millones. En este punto, size () podría devolver Integer.MAX_VALUE, pero algunas funciones, como toArray, fallarán, ya que no pueden poner todos los objetos en una matriz, sino que le proporcionarán el primer Integer.MAX_VALUE en lugar de arrojar una excepción.

Como señala @Joachim Sauer, el OpenJDK actual podría devolver un resultado incorrecto para tamaños superiores a Integer.MAX_VALUE. por ejemplo, podría ser un número negativo.

Answer 3

El tamaño máximo depende de la configuración de memoria de la JVM y, por supuesto, de la memoria del sistema disponible. El tamaño específico del consumo de memoria por entrada de lista también difiere entre las plataformas, por lo que la forma más fácil podría ser ejecutar pruebas simples.

Answer 4

En todos los casos, es probable que esté limitado por el tamaño del almacenamiento dinámico de JVM en lugar de por cualquier otra cosa. Eventualmente, siempre llegarás a las matrices, por lo que dudo mucho que cualquiera de ellas administre más de 2 ³¹ - 1 elementos, pero de todos modos es muy probable que se te acabe el montón.

Answer 5

No hay un tamaño máximo especificado de estas estructuras.

El límite de tamaño práctico real probablemente esté en algún lugar de la región de Integer.MAX_VALUE (es decir, 2147483647, aproximadamente 2 mil millones de elementos), ya que ese es el tamaño máximo de una matriz en Java.

• Un HashSet utiliza un HashMap internamente, por lo que tiene el mismo tamaño máximo que ese
  • Un HashMap utiliza una matriz que siempre tiene un tamaño que es una potencia de dos, por lo que puede tener como máximo 2 ³⁰ = 1073741824 elementos grandes (ya que la siguiente potencia de dos es mayor que Integer.MAX_VALUE ).
  • Normalmente, el número de elementos es como máximo el número de cubos multiplicado por el factor de carga (0,75 por defecto). Sin embargo , cuando HashMap deje de cambiar el tamaño, le permitirá agregar elementos, explotando el hecho de que cada segmento se administra a través de una lista vinculada. Por lo tanto, el único límite para los elementos en un HashMap / HashSet es la memoria.
• Un Vector utiliza una matriz interna que tiene un tamaño máximo de Integer.MAX_VALUE exactamente, por lo que no puede admitir más que muchos elementos
• Una LinkedList no utiliza una matriz como almacenamiento subyacente, por lo que no limita el tamaño. Utiliza una estructura clásica de lista doblemente vinculada sin límite inherente, por lo que su tamaño solo está limitado por la memoria disponible. Tenga en cuenta que LinkedList informará el tamaño incorrectamente si es más grande que Integer.MAX_VALUE , porque utiliza un campo int para almacenar el tamaño y el tipo de devolución de size() es int .

Tenga en cuenta que, si bien la API de recopilación define cómo debe comportarse una Collection con más de elementos Integer.MAX_VALUE . Lo más importante es que indica esta la documentación del size() :

Si esta colección contiene más de elementos Integer.MAX_VALUE , devuelve Integer.MAX_VALUE .

Tenga en cuenta que aunque HashMap , HashSet y LinkedList parecen admitir más que los elementos Integer.MAX_VALUE , ninguno de ellos implementa el método size() de esta forma (es decir, simplemente dejan que el campo de size interno se desborde).

Esto me lleva a creer que otras operaciones tampoco están bien definidas en esta condición.

Por lo tanto, diría que es seguro usar esas colecciones de propósito general con elementos Integer.MAX_VLAUE . Si sabe que necesitará almacenar más que eso, entonces debe cambiar a implementaciones de colecciones dedicadas que realmente lo respalden.