Shulou(Shulou.com)06/03 Report--

This article focuses on "how to understand the ArrayList source code", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand the ArrayList source code.

The ArrayList class diagram is as follows:

The underlying layer of ArrayList is implemented by arrays, which are characterized by fixed size, while ArrayList implements dynamic expansion.

Some of the ArrayList variables are as follows, which will be used in the following analysis.

/ * * default capacity * / private static final int DEFAULT_CAPACITY = 10; / * empty object array * / private static final Object [] EMPTY_ELEMENTDATA = {}; / * empty array created by no parameter constructor * / private static final Object [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; / * cache variable of the array where the data is stored * / transient Object [] elementData / * number of elements * / private int size

One initialize ArrayList

Initializing ArrayList typically uses the following two constructors

1.1 No-parameter constructor

If you do not specify a size when initializing the ArrayList, an empty array is created.

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

1.2 Constructor that specifies the size of the array

Create an array of estimated size. After specifying the size, you only specify the size of the initial value of the array, which does not affect the subsequent expansion. The advantage of specifying is that it can save memory and time overhead.

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

Second, add elements and expand capacity dynamically

ArrayList.add (E e) source code:

Public boolean add (E) {ensureCapacityInternal (size + 1); / / Increments modCounting! ElementData [size++] = e; return true;}

ElementData [size++] = e in add () is easy to understand, that is, insert the element into the size position, and then size++, let's focus on the ensureCapacityInternal (size+ 1) method.

Private void ensureCapacityInternal (int minCapacity) {if (elementData = = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max (DEFAULT_CAPACITY, minCapacity);} ensureExplicitCapacity (minCapacity);}

The ensureCapacityInternal () method determines whether the cache variable elementData is empty, that is, whether the element is added for the first time. If the element is added for the first time, the initialization size is set to the default capacity of 10, otherwise it is the passed parameter. The purpose of this method is to obtain the capacity of the initialization array. Call the ensureExplicitCapacity (minCapacity) method after getting the initialization capacity

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

The ensureExplicitCapacity (minCapacity) method is used to determine whether capacity expansion is needed. If the element is added for the first time, the minCapacity is 10 and the capacity is 0, then the capacity needs to be expanded. Call the grow (minCapacity) method.

/ / the maximum capacity of the array private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8; private void grow (int minCapacity) {/ / overflow-conscious code int oldCapacity = elementData.length; / / the expansion size is 1.5 times the length of the original array int newCapacity = oldCapacity + (oldCapacity > > 1); / / if the expansion capacity is smaller than the length that needs to be expanded, the capacity if (newCapacity-minCapacity) is used

0) newCapacity = hugeCapacity (minCapacity); / / minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf (elementData, newCapacity);}

The grow (minCapacity) method expands the array to 1.5 times the size of the original array. If the calculated expansion capacity is less than the required capacity, the expansion size is the required capacity. If the expansion capacity is larger than the maximum capacity of the array, call the hugeCapacity (minCapacity) method to expand the array to the maximum length of the integer, and then point the elemetData array to the new expanded memory space and copy the elements to the new space.

When the required set capacity is particularly large, 1.5 times the capacity will consume a lot of space, so it is recommended to estimate a capacity size during initialization.

Three delete elements

ArrayList provides two ways to delete elements, which can be deleted by index and element. The two deletions are more or less the same. after deleting the element, move the subsequent element forward at once.

ArrayList.remove (int index) source code:

Public E remove (int index) {rangeCheck (index); modCount++; E oldValue = elementData (index); int numMoved = size-index-1; if (numMoved > 0) System.arraycopy (elementData, index+1, elementData, index, numMoved); elementData [--size] = null; / / clear to let GC do its work return oldValue;}

When deleting an element, it first determines whether the index is larger than the size of the ArrayList, if the index range is correct, assigns the next element of the index position to the index position, sets the size of the ArrayList to-1, and finally returns the removed element. The operation diagram is as follows, if I want to remove the element with index 1:

At this point, I believe you have a deeper understanding of "how to understand the ArrayList source code", might as well come to the actual operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.