metodos - imprimir arraylist java

ArrayList: ¿cómo aumenta el tamaño?

Question

Tengo una pregunta básica sobre Java ArrayList .

Cuando ArrayList se declara e inicializa utilizando el constructor predeterminado, se crea espacio de memoria para 10 elementos. Ahora, cuando agrego un 11º elemento, ¿qué ocurre? ¿Se creará un nuevo espacio de memoria con 20 (o más) elementos de capacidad (esto requiere copiar elementos desde la ubicación de la 1ª memoria a la nueva ubicación) O algo más?

Revisé here . Pero no encontré una respuesta.

Por favor comparte el conocimiento. Gracias.

Answer 1

Contexto java 8

Doy mi respuesta aquí en el contexto de la implementación Oracle java 8, ya que después de leer todas las respuestas, encontré que gmgmiller me dio una respuesta en el contexto de java 6, y otra respuesta en el contexto de java 7. Pero cómo java 8 implementa el aumento de tamaño no se ha dado.

En java 8, el comportamiento de aumento de tamaño es el mismo que el de java 6, consulte el método de grow de ArrayList:

   private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

el código clave es esta línea:

int newCapacity = oldCapacity + (oldCapacity >> 1);

Entonces, claramente, el factor de crecimiento también es 1.5, lo mismo que java 6.

Answer 2

Cuando ArrayList se declara e inicializa utilizando el constructor predeterminado, se crea espacio de memoria para 10 elementos.

NO. Cuando ArrayList se inicializa, la asignación de memoria se realiza para una matriz vacía. La asignación de memoria para la capacidad predeterminada (10) se realiza solo al agregar el primer elemento a ArrayList.

 /**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 */
private transient Object[] elementData;

PD: No tengo suficiente reputación para comentar sobre una pregunta, así que lo estoy poniendo como una respuesta ya que nadie señaló esta suposición incorrecta antes.

Answer 3

ArrayList aumenta el tamaño del factor de carga en los siguientes casos:

• Capacidad inicial: 10
• Factor de carga: 1 (es decir, cuando la lista está llena)
• Tasa de crecimiento: tamaño_actual + tamaño_actual / 2

Contexto: JDK 7

Al agregar un elemento a ArrayList , las siguientes llamadas public ensureCapacityInternal y las otras llamadas a métodos privados suceden internamente para aumentar el tamaño. Esto es lo que aumenta dinámicamente el tamaño de ArrayList . Mientras veo el código, puedes entender la lógica nombrando convenciones, por esta razón no agrego una descripción explícita

public boolean add(E paramE) {
        ensureCapacityInternal(this.size + 1);
        this.elementData[(this.size++)] = paramE;
        return true;
    }

private void ensureCapacityInternal(int paramInt) {
        if (this.elementData == EMPTY_ELEMENTDATA)
            paramInt = Math.max(10, paramInt);
        ensureExplicitCapacity(paramInt);
    }
private void ensureExplicitCapacity(int paramInt) {
        this.modCount += 1;
        if (paramInt - this.elementData.length <= 0)
            return;
        grow(paramInt);
    }

private void grow(int paramInt) {
    int i = this.elementData.length;
    int j = i + (i >> 1);
    if (j - paramInt < 0)
        j = paramInt;
    if (j - 2147483639 > 0)
        j = hugeCapacity(paramInt);
    this.elementData = Arrays.copyOf(this.elementData, j);
}

Answer 4

Cuando tratamos de agregar un objeto a la lista de arrays,

Java comprueba que haya suficiente capacidad en la matriz existente para contener el nuevo objeto. De lo contrario, se crea una nueva matriz de mayor tamaño , la matriz anterior se copia a la nueva matriz usando Arrays.copyOf y la nueva matriz se asigna a la matriz existente.

Mire el siguiente código (tomado de Java ArrayList Code en GrepCode.com).

Editar:

public ArrayList () Construye una lista vacía con una capacidad inicial de diez.

public ArrayList (int initialCapacity) podemos especificar la capacidad inicial.

public ArrayList (Collection c) Construye una lista que contiene los elementos de la colección especificada, en el orden en que son devueltos por el iterador de la colección.

Ahora, cuando usamos ArrayList () constructore, obtenemos ArrayList con Size = 10 Al agregar el undécimo elemento en la lista, se crea un nuevo Arraylist dentro del método ensureCapacity ().

Usando la siguiente fórmula:

  int newCapacity= (oldCapacity * 3)/2 +1;

Answer 5

Dependerá de la implementación, pero del código fuente de Sun Java 6:

int newCapacity = (oldCapacity * 3)/2 + 1;

Eso está en el método de ensureCapacity . Otras implementaciones de JDK pueden variar.

Answer 6

El tamaño de ArrayList aumenta siempre con n+n/2+1 .

Answer 7

El tamaño predeterminado de la lista de arrays es 10. Cuando agregamos la 11ª ... la lista de arrays aumenta el tamaño (n * 2). Los valores almacenados en el arraylist antiguo se copian en el nuevo arraylist cuyo tamaño es 20.

Answer 8

En Jdk 1.6: Nueva capacidad = (Capacidad actual * 3/2) + 1;

En Jdk 1.7:

int j = i + (i >> 1); esto es lo mismo que Nueva capacidad = (Capacidad actual * 1/2) + Capacidad actual;

ej .: el tamaño aumentará como: 10 -> 15 -> 22 -> 33

Answer 9

JDK6 de Sun:

Creo que crece a 15 elementos. Sin codificarlo, pero mirando el código grow () en el jdk.

int newCapacity then = 10 + (10 >> 1) = 15.

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Desde Javadoc, dice que esto es de Java 2 en adelante, por lo que es una apuesta segura en Sun JDK.

EDITAR : para aquellos que no obtuvieron cuál es la conexión entre multiplicar el factor 1.5 e int newCapacity = oldCapacity + (oldCapacity >> 1);

>> es el operador de desplazamiento a la derecha que reduce un número a su mitad. Así,
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;

Answer 10

La capacidad predeterminada de ArrayList es 10. Una vez que la capacidad alcanza su capacidad máxima, el tamaño de ArrayList será 16, una vez que la capacidad alcance su capacidad máxima de 16, el tamaño de ArrayList será 25 y seguirá aumentando según el tamaño de datos. ...

¿Cómo? Aquí está la respuesta y la fórmula

New capacity = (Current Capacity * 3/2) + 1

Entonces, si la capacidad predeterminada es 10, entonces

Current Capacity = 10
New capacity = (10 * 3/2) + 1
Output is 16

Answer 11

Lo que sucede es que se crea una nueva matriz con n * 2 espacios, luego se copian todos los elementos en la matriz anterior y se inserta el nuevo elemento en el primer espacio libre. Con todo, esto da como resultado O (N) agregar tiempo para ArrayList.

Si está utilizando Eclipse, instale Jad y Jadclipse para descompilar los Jadclipse almacenados en la biblioteca. Hice esto para leer el código fuente original.

Answer 12

Por lo general, la memoria para los contenedores de tipo ArrayList aumenta al duplicarla. Por lo tanto, si inicialmente tenía espacio para 10 elementos y agregó 10, el undécimo elemento se agregará a una nueva matriz (interna) de 20 elementos. La razón de esto es que el costo incremental de agregar elementos se reduce desde O (n ^ 2) si la matriz se ha incrementado en incrementos de tamaño fijo a un agradable O (n) al duplicar el tamaño cada vez que la matriz interna está llena.

Answer 13

Se crea una nueva matriz y se copia el contenido de la anterior. Eso es todo lo que sabes en el nivel de API. Citando de los documentos (mi énfasis):

Cada instancia de ArrayList tiene una capacidad. La capacidad es el tamaño de la matriz utilizada para almacenar los elementos en la lista. Siempre es al menos tan grande como el tamaño de la lista. A medida que se agregan elementos a ArrayList, su capacidad crece automáticamente. Los detalles de la política de crecimiento no se especifican más allá del hecho de que agregar un elemento tiene un costo de tiempo amortizado constante.

En términos de cómo sucede realmente con una implementación específica de ArrayList (como la de Sun), en su caso puede ver los detalles sangrientos en la fuente. Pero, por supuesto, confiar en los detalles de una implementación específica no suele ser una buena idea ...

Answer 14

cuando una ArrayList se declara e inicializa utilizando el constructor predeterminado, se creará un espacio de memoria para 10 elementos. ahora, cuando agrego el 11 ° elemento, lo que sucede es

ArrayList crea un nuevo objeto con el siguiente tamaño

es decir, OldCapacity * 3/2 + 1 = 10 * 3/2 + 1 = 16

Answer 15

static int getCapacity(ArrayList<?> list) throws Exception {
            Field dataField = ArrayList.class.getDeclaredField("elementData");
            dataField.setAccessible(true);
            return ((Object[]) dataField.get(list)).length;
    }

utilice el método anterior para verificar el tamaño cuando se está modificando el arraylist.