Example Analysis of ArrayList capacity and expansion Mode in Java

Editor to share with you the Java ArrayList capacity and expansion of the example analysis, I believe that most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article, let's go to know it!

Check the source code of JDK1.8 ArrayList 1. The default initial capacity is 10 / * Default initial capacity. * / private static final int DEFAULT_CAPACITY = 10 * * 2, the maximum capacity is Integer.MAX_VALUE-8 * * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit * / private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8

Reason: before referring to others, it remains to be verified:

The array object has an additional metadata that represents the size of the array

The array length size is of type int, with a total of 32 bits and one symbol bit, so the maximum length is Integer.MAX_VALUE= 2 ^ 31 = 2147483648.

8bytes is used to store size

3. Expansion method:

(1) first pass in a desired minimum capacity minCapacity

(2) the new capacity newCapacity = oldCapacity + (oldCapacity > > 1), that is, the new capacity is equal to 1.5 times the original capacity.

(3) if minCapacity > newCapacity, newCapacity = minCapacity

(4) if newCapacity > maximum capacity MAX_ARRAY_SIZE, newCapacity = hugeCapacity (minCapacity)

(5) copy the original data with new capacity

/ * * 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);} private static int hugeCapacity (int minCapacity) {if (minCapacity)

< 0) // overflow throw new OutOfMemoryError(); return (minCapacity >

MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE;} Java ArrayList () capacity expansion principle

ArrayList () is usually used directly. Today, let's take a look at the expansion principle of ArrayList ().

First, take a look at the properties and construction methods of ArrayList, which is more important.

Take a look at the attributes first.

/ / ArrayList default capacity size private static final int DEFAULT_CAPACITY = 10 size / a shared empty array, using private static final Object [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} when empty instances are used; / / a shared empty array, using private static final Object [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} when using empty instances of default size / * Array buffers storing ArrayList elements focus 1: the capacity of ArrayList is the length of array buffers 2: it can also be seen from this element that the underlying layer of ArrayList () is an Object [] add first element, any empty ArrayList with elementData = = DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY*/transient Object [] elementData / / the size of ArrayList. The bottom layer of list.size () that we usually use is the maximum private static final int MAX_ARRAY_SIZE of recorded sizeprivate int size;// ArrayList = Integer.MAX_VALUE-8.

Then look at the constructor, with a parametric constructor.

/ * Constructor with parameters, for example: initialize a container of 20 type Integer ArrayListArrayList list = new ArrayList (20); * / public ArrayList (int initialCapacity) {/ * initialization capacity > 0, elementData initialization to the array initialization capacity of size = 0, elementData = EMPTY_ELEMENTDATA (empty array) initialization capacity

< 0, 直接抛出异常 */ if (initialCapacity >

0) {this.elementData = new Object [initialCapacity];} else if (initialCapacity = = 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException ("Illegal Capacity:" + initialCapacity);}}

Constructor with parameter Collection

/ * convert a collection whose parameter is Collection to ArrayList*/public ArrayList (Collection