Java ArrayList expansion problems detailed examples

This paper mainly studies the Java ArrayList expansion problems in detail, the specific introduction is as follows.

The first thing we need to know is that ArrayList is actually an array of type Object, and the size of ArrayList is actually the size of this array of type Object.

transient Object[] elementData; 

1. Capacity allocation of ArrayList at creation time

There are three scenarios for creating an ArrayList

1. Default size creation (default is 0)

ArrayList al = new ArrayList();

After creation, al has a capacity of 0. You can see this from the following code.

transient Object[] elementData; 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2, Specify size creation

ArrayList al = new ArrayList(5);

Create an ArrayList object (size 5), which is an array of Object (length 5).

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 the creation of a collection of elements

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

The ES36en object is created and initialized with 1 ES37en as [1,2,3,4,5]. We create an Object array of length 5. The contents of the array are [1,2,3,4,5]. You can see this 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. Capacity expansion of ArrayList when inserting elements

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:

Create (ArrayList = 5) create (ArrayList = 5) create (ArrayList = 5) create (ArrayList = 5) -- The initial capacity is 5

2, Add collection {6, 7, 8, 9, 10} to ArrayList object. At this point, we need to expand the ArrayList object capacity.

View the source code:

public Boolean addAll(Collection<? extends E> c) {
	//  Get the insert array 
	Object[] a = c.toArray();
	//  Gets the inserted content length 
	int numNew = a.length;
	ensureCapacityInternal(size + numNew);
	// Increments modCount
	System.arraycopy(a, 0, elementData, size, numNew);
	size += numNew;
	return numNew != 0;
}
private void ensureCapacityInternal(int minCapacity) {
	// if ArrayList The contents are empty 
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	//  Into the 1 Step to calculate the expanded size minCapacity
	if (minCapacity - elementData.length > 0)
	    grow(minCapacity);
}
private void grow(int minCapacity) {
	// ArrayList Original size of 
	int oldCapacity = elementData.length;
	//  Calculates the expanded size based on the original size, which is the size of the element 1.5 times 
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	// The expanded length is the same as the previous calculation minCapacity Compare, take the larger one as the expanded length 
	if (newCapacity - minCapacity < 0)
	    newCapacity = minCapacity;
	//  If the expanded length is greater than the maximum length 
	if (newCapacity - MAX_ARRAY_SIZE > 0)
	    newCapacity = hugeCapacity(minCapacity);
	//  expand 
	elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
	// minCapacity Less than 0 , indicating overflow, otherwise the maximum integer is taken as the final expansion length 
	if (minCapacity < 0) // overflow
	throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ?
	    Integer.MAX_VALUE :
	    MAX_ARRAY_SIZE;
}

The above process can be summarized as follows:

ArrayList + size of set to be inserted numNew = minimum length of minCapacity

2, If the original size of ArrayList is 0, that is, ArrayList is empty, then the expanded minimum length of ArrayList = Math.max(10, minCapacity), that is, the expanded minimum length of minCapacity is not just the original length of size plus the inserted length of numNew.

3. The minimum extended length minCapacity obtained above is not the final expanded length, and it needs to be calculated in one step further.

(1) The original size of ArrayList is oldCapacity
newCapacity = oldCapacity*1.5; 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.

conclusion

The above is all the content of this article on ArrayList expansion problems in detail, I hope to help you. Interested friends can continue to refer to the site of other related topics, if there are shortcomings, welcome to leave a message to point out. Thank you for your support!