ArrayList: how does size increase?

Question

I have a basic question about Java ArrayList .

When an ArrayList declared and initialized using the default constructor, a memory space of 10 elements is created. Now when I add the 11th element, what happens? Will a new memory space be created with a capacity of 20 (or more) elements (this requires copying elements from the 1st memory cell to a new location) OR something else?

I checked here . But I did not find the answer.

Please share your knowledge. Thank.

Answer 1

A new array is created and the contents of the old are copied. That’s all you know at the API level. Quote from the docs (my emphasis):

Each instance of ArrayList has a capacity. Capacity is the size of the array used to store items in a list. It is always no less than the size of the list. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not indicated beyond the fact that adding an item has a constant amortized cost of time.

In terms of how this actually happens with a specific ArrayList implementation (e.g. Sun), in their case you can see the gory details in the source. But, of course, relying on the details of a particular implementation is usually not a good idea ...

Answer 2

Sun JDK6:

I believe that it has grown to 15 elements. Not coding this, but looking at grow () code in 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); } 

From Javadoc, he says it is from Java 2 onwards, so this is a safe bet in the Sun JDK.

EDIT : for those who do not understand what is the relationship between the factor of 1.5 and int newCapacity = oldCapacity + (oldCapacity >> 1);

>> is the right shift operator, which reduces the number to half. So int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;

Answer 3

This will depend on the implementation, but on the source code of Sun Java 6:

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

This is in the ensureCapacity method. Other JDK implementations may vary.

Answer 4

When we try to add an object to an arraylist,

Java checks to ensure that the existing array is large enough to hold the new object. If not, a new larger array is created, the old array is copied to the new array using Arrays.copyOf , and the new array is assigned to the existing array.

Take a look at the code below (taken from the Java ArrayList code on GrepCode.com).

Edit:

public ArrayList () Creates an empty list with an initial capacity of ten.

public ArrayList (int initialCapacity) , we can specify the initial capacity.

public ArrayList (Collection c) Creates a list containing the elements of the specified collection, in the order in which they are returned by the collection iterator.

Now, when we use the ArrayList () constructor, we get an ArrayList with Size = 10. When you add the 11th element to the list, a new Arraylist is created inside the securityCapacity () method.

Using the following formula:

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

Answer 5

when an ArrayList is declared and the default constructor is initialized, a memory space for 10 elements. now when i add the 11th element what happens

ArrayList creates a new object with the following size

ie OldCapacity * 3/2 + 1 = 10 * 3/2 + 1 = 16

Answer 6

Prior to JDK 6, capacity increases with the formula newCapacity = (oldCapacity * 3/2) + 1 .

In JDK 7 and above, the formula changes to newCapacity = oldCapacity + (oldCapacity >> 1) .

Thus, if the initial capacity is 10 , then the new capacity will be 16 in JDK6 and 15 in above JDK6

Answer 7

As a rule, memory for containers of the ArrayList type is increased by doubling it. Thus, if at first you had a place for 10 items, and you added 10, the eleventh element will be added to the new (inner) array of 20 elements. The reason for this is that the added cost of adding elements decreases from O (n ^ 2) if the array was increased in fixed-size increments to good O (n) when doubling the size each time the inner array is full.

Answer 8

Java context 8

I give my answer here in the context of the implementation of Oracle java 8, since after reading all the answers I found that the answer in the context of java 6 was given by gmgmiller, and the other answer was given in the context of java 7. But how java 8 implements the increase in size was not given.

In java 8, the resize behavior is the same as java 6, see the grow ArrayList method:

  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); } 

key code is a line:

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

So the growth factor is also 1.5, just like java 6.

Answer 9

Let's look at this code (jdk1.8)

 @Test public void testArraySize() throws Exception { List<String> list = new ArrayList<>(); list.add("ds"); list.add("cx"); list.add("cx"); list.add("ww"); list.add("ds"); list.add("cx"); list.add("cx"); list.add("ww"); list.add("ds"); list.add("cx"); list.add("last"); } 

1) Put a breakpoint on the line when the "last" is inserted

2) Go to the ArrayList add method. You will see

 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; 

3) Go to the method ensure CapacityInternal, which calls this method ensureExplicitCapacity

four)

 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } return true; 

In our example, minCapacity is 11 11-10 > 0 , so you need a grow method

5)

 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); } 

Let's describe each step:

1) oldCapacity = 10, because we did not specify this parameter when initializing the ArrayList , so it will use the default capacity (10)

2) int newCapacity = oldCapacity + (oldCapacity >> 1); Here newCapacity is equal to oldCapacity plus oldCapacity with a right shift of one ( oldCapacity is 10 is a binary representation of 00001010 shifting one bit to the right, we get 00000101 , which is 5 in decimal, so newCapacity is 10 + 5 = 15 )

3)

 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 

For example, your initialization capacity is 1, when you add the second element to arrayList newCapacity will be 1(oldCapacity) + 0 (moved to right by one bit) = 1 In this case, newCapacity is less than minCapacity and elementData (the array object inside arrayList) cannot contain a new element, so newCapacity is equal to minCapacity

four)

 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); 

Check if the size of the array is MAX_ARRAY_SIZE (which is Integer.MAX - 8) Why is the maximum size of the ArrayList array Integer.MAX_VALUE - 8?

5) Finally, it copies the old values ​​to newArray of length 15

Answer 10

When an ArrayList is declared and initialized using the default constructor, a memory space of 10 elements is created.

NO. When an ArrayList is initialized, memory allocation is performed for an empty array. The memory allocation for the default capacity (10) is performed only after adding the first element to the 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; 

PS There is not enough reputation to comment on the question, so I put this as an answer, since no one had previously indicated this incorrect assumption.

Answer 11

Based on the JDK source code, I found the code below

 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); 

Answer 12

What happens to the new array created with spaces n * 2, then all the elements in the old array are copied and the new element is inserted into the first free space. In general, this causes O (N) to add time to the ArrayList.

If you use Eclipse, install Jad and Jadclipse to decompile the JARs stored in the library. I did this to read the source code.

Answer 13

ArrayList increases the load factor in the following cases:

• Starting Capacity: 10
• Load factor: 1 (i.e. when the list is full)
• Growth rate: current_size + current_size / 2

Context: JDK 7

When an element is added to an ArrayList following calls to public ensureCapacityInternal and other private method calls occur internally to increase the size. This is what dynamically increases the size of an ArrayList . when viewing code, you can understand the logic by assigning naming conventions, so I am not adding an explicit description

 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 14

The size of an ArrayList always increases from n+n/2+1 .

Answer 15

The default value for ArrayList is 10. As soon as the capacity reaches the maximum capacity, the size of the ArrayList array will be 16, as soon as the capacity reaches the maximum capacity of 16, the size of the ArrayList will be 25 and will increase depending on the size of the data .....

How? Here is the answer and the formula

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

So, if the default value is 10, then

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

Answer 16

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

use the above method to check the size when the array changes.

Answer 17

In JDK 1.6: New capacity = (Current capacity * 3/2) + 1;

In JDK 1.7:

int j = i + (i >> 1); it is the same as New capacity = (Current capacity * 1/2) + Current capacity;

example: the size will increase as: 10 -> 15 → 22 -> 33

Answer 18

The default size for arraylist is 10. When we add the 11th ... arraylist increases the size (n * 2). Values ​​stored in the old arraylist are copied to the new arraylist, whose size is 20.