Detailed explanation of Java ArrayList expansion problem example

This article mainly studies related contents of Java ArrayList expansion problem examples, as follows.

First of all, we need to know that the essence of ArrayList is actually an Object-type array. The expansion problem of ArrayList is actually the expansion problem of this Object-type array.

 transient Object[] elementData;

1. When creating, the capacity allocation of ArrayList

There are three situations for creating an ArrayList

1. Default size creation (default is 0)

 ArrayList al = new ArrayList();

After creation is completed, the capacity of al is 0. You can know from the following code.

 transient Object[] elementData; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

2. Create a specified size

 ArrayList al = new ArrayList(5);

Creating an ArrayList object with a capacity of 5 is actually an Object array with a length of 5. You can know from the following code.

 transient Object[] elementData; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}

3. Specify element collection creation

 ArrayList al = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));

The ArrayList object is created above and initialized using a List as [1,2,3,4,5]. In fact, it creates an Object array of length 5, and the content of the array is [1, 2, 3, 4, 5]. You can know from the following code.

 private int size;transient Object[] elementData; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}

2. When inserting elements, the capacity of ArrayList is expanded

 ArrayList<Integer> collection = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));Integer[] moreInts = { 6, 7, 8, 9, 10 };collection.addAll(Arrays.asList(moreInts));

The above process is as follows:

1. Create an ArrayList with size 5, with content [1, 2, 3, 4, 5]. - The initial capacity is 5

2. Add set { 6, 7, 8, 9, 10} to this ArrayList object. ―--At this time, the capacity of this ArrayList object needs to be expanded.

View source code:

 public Boolean addAll(Collection<? extends E> c) {// Get the insert array Object[] a = c.toArray();// Get the insert content length int numNew = a.length;ensureCapacityInternal(size + numNew);// Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}private void ensureCapacityInternal(int minCapacity) {//If the content in ArrayList is empty if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;// Further calculate the expanded size minCapacityif (minCapacity - elementData.length > 0) grow(minCapacity);}private void grow(int minCapacity) {// The original size of ArrayList int oldCapacity = elementData.length;// Calculate the expanded size based on the original size, and the expanded size is 1.5 times the size of the element int newCapacity = oldCapacity + (oldCapacity >> 1);//Compare with the previously calculated expansion length minCapacity, take the larger one as the expansion length if (newCapacity - minCapacity < 0) newCapacity = minCapacity;// If the expansion length is greater than the maximum length if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);// Expansion elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {// minCapacity is less than 0, indicating overflow, otherwise the maximum integer is used as the final expansion length if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

The above process can be summarized as follows:

1. The original size of ArrayList + the size of the collection to be inserted numNew = Get the minimum length of the expanded ArrayList minCapacity

2. If the original size of ArrayList is 0, that is, ArrayList is empty, the minimum length of ArrayList after expansion minCapacity=Math.max(10, minCapacity), that is, the minimum length of expansion minCapacity is not just the original length size plus the length numNew of the insertion set.

3. The expanded minimum length minCapacity obtained above is not the final expanded length, and further calculation is needed.

(1) Get the original size of ArrayList oldCapacity
(2) Obtain the new expanded size: newCapacity = oldCapacity*1.5;
(3) Compare the expanded minimum length minCapacity calculated above with the expanded size newCapacity obtained here, and take the larger one as the final expanded size.

Summarize

The above is all the detailed explanation of the ArrayList expansion problem example in this article, I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!