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

This article mainly explains "the principle and usage of ArrayList". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "the principle and usage of ArrayList".

Preface

ArrayList, as the most commonly used class in the Java collection framework, is most suitable for storing collection data in general. Knowing why, in order to better understand and use ArrayList, this article will deeply understand ArrayList from the following aspects:

Why not use arrays, use ArrayList

Source Code Analysis of ArrayList characteristics

ArrayList after Java 8

Correct posture for ArrayList use

Why not use arrays, use ArrayList.

In Java language, due to the length limit of ordinary array, the length of array needs to be limited during initialization, so it is impossible to expand dynamically according to the number of elements. Moreover, the method of Java array for developers to call is limited, so there are only some simple operations such as fetching elements, getting array length and adding elements. The background introduces a powerful and rich Collection framework in Java 1.2, in which ArrayList is used as a list implementation that can dynamically expand the array to replace the use of Array in daily development. ArrayList implements the operation methods of all lists, which is convenient for developers to operate list collections. Here we first list the main features of ArrayList, which will be described one by one later:

Ordered storage element

Allow elements to repeat, allow null values to be stored

Support dynamic expansion

Non-thread safety

To better understand ArrayList, let's first take a look at the UML class diagram from ArrayList:

From the figure above, you can see that ArrayList inherits AbstractList and directly implements Cloneable, Serializable,RandomAccess type flag interface.

As an abstract implementation of the list, AbstractList gives the addition, deletion, modification and query of elements to specific subclasses to implement, and provides a default implementation on the iterative traversal of elements.

The implementation of the Cloneable interface indicates that ArrayList supports calling the clone method of Object to realize the copy of ArrayList.

The implementation of the Serializable interface shows that ArrayList also supports serialization and deserialization operations and has a fixed serialVersionUID attribute value.

The RandomAccess interface is implemented, which indicates that the elements in ArrayList can be accessed randomly and efficiently, and the elements can be obtained by numbering below. The list that implements the RandomAccess interface can directly use the normal for loop mode when traversing, and the execution efficiency is higher than the iterator mode.

ArrayList source code analysis

Entering the ArrayList source code, you can quickly see two important member variables of ArrayList: elementData and size, from the structure of the class.

ElementData is an Object array, and the elements stored are exactly the elements that need to be stored in ArrayList, that is, the ArrayList object maintains the object array Object []. The additions, deletions, modifications, queries and traversals provided outside are related to this array, so the elements added to ArrayList are stored in the array object elementData in an orderly manner.

The size field represents the number of elements currently added to ArrayList, and it is important to note that it must be less than or equal to the length of the array object elementData. Once size and elementData are of the same length and are still adding elements to the list, ArrayList performs a scaling operation to store the previous elements with a longer array object.

Since the underlying maintenance is an array of objects, the elements added to the ArrayList collection are naturally repeatable, allowed to be null, and have different index locations.

How to expand capacity

After understanding why ArrayList sequentially stores elements and elements can be repeated, let's take a look at how the underlying expansion is implemented as a dynamic array list.

First of all, you need to determine where the time for capacity expansion will be. As mentioned in the size field described above, when the length of size is the same as that of elementData, adding another element to the collection will cause insufficient capacity and need to be expanded. That is to say, the expansion of ArrayList occurs in the add method and certain conditions are met.

Now if we look at the code structure of the ArrayList class, we can see that there are four ways to add elements, divided into two categories: adding a single element and adding all elements in another collection.

Let's start with a simple analysis and see the add (E): boolean method implementation:

Public boolean add (E e) {ensureCapacityInternal (size+ 1); elementData [size++] = e; return true;}

As can be seen from the above, the third line of code simply adds a single element and increments size by 1. Then the implementation of capacity expansion is in the ensureCapacityInternal method, where the parameter is size+1, which is to determine the number of added elements before actually adding elements, that is, whether the minimum capacity required by the collection will exceed the length of the original array. Let's take a look at the ensureCapacityInternal method implementation

Private void ensureCapacityInternal (int minCapacity) {ensureExplicitCapacity (calculateCapacity (elementData,minCapacity));}

There are still two method calls inside. First, take a look at the relatively simple calculateCapacity method:

Private static int calculateCapacity (Object [] elementData, int minCapacity) {if (elementData = = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max (DEFAULT_CAPACITY, minCapacity);} return minCapacity;}

When elementData is equal to DEFAULTCAPACITY_EMPTY_ELEMENTDATA, that is, an empty array, it returns 10 corresponding to the default minimum capacity value DEFAULT_CAPACITY of elements that can be added, otherwise it is the minimum capacity value according to the passed size + 1. After execution, look at the ensureExplicitCapacity method:

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

You can see from the code that the expansion is implemented in the grow method and is performed only when the array length is less than the required minimum capacity: when the array storage element is full, the newly added element can no longer be stored.

Private void grow (int minCapacity) {int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity > > 1); if (newCapacity-minCapacity)

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

0) newCapacity = hugeCapacity (minCapacity); elementData = Arrays.copyOf (elementData, newCapacity);}

Further jumping to the implementation of the grow method, you can see that line 8 uses the utility class method java.util.Arrays#copyOf (T [], int) to copy the original array, store all internal elements in a new array of length newCapacity, and assign references to the new array to elementData. Now the object referenced inside the ArrayList is the new array with updated length, and the implementation effect is as follows:

Now let's take a look at how much the newCapacity representing the new capacity of the array is adjusted. First of all, newCapacity is calculated by oldCapacity + (oldCapacity > > 1). Using bit operation, the original capacity value oldCapacity is moved by one bit to the right to get half of its value (rounded down), and then the original capacity value is added, which is 1.5 times the original capacity value oldCapacity.

The right operator shifts the left Operand to the right, which is equivalent to dividing by 2, and rounds it down, for example, the expression (7 > > 1) = = 3 is true.

When the calculated newCapacity is still less than the incoming minimum capacity value, the current number of arrays is empty, and the default DEFAULT_CAPACITY is used as the capacity value allocation array.

It is important to note that there is also the judgment of the maximum number of arrays. The code corresponding to MAX_ARRAY_SIZE in the file is defined as follows:

Private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8

There is a maximum limit on the number of ArrayList storage elements. If the limit is exceeded, it will cause JVM to throw an OutOfMemoryError exception.

At this point, the expansion logic of the java.util.ArrayList#add (E) method is over. Similarly, in the implementation of other methods for adding elements, we can see the call to the ensureCapacityInternal method, which confirms the capacity before the actual operation of the underlying array, and dynamically expands the capacity if the capacity is not enough.

Serialization and deserialization of transient Object [] elementData

The elementData seen in the ArrayList source code has the keyword transient, and usually the transient keyword modifies the field to indicate that the field will not be serialized, but ArrayList implements the serialization interface and provides the implementation of serialization method writeObject and deserialization method readObject. How do you do this?

Let's first take a look at the ArrayList serialization code:

Private void writeObject (java.io.ObjectOutputStream s) throws java.io.IOException {int expectedModCount = modCount; s.defaultWriteObject (); s.writeInt (size); for (int I = 0; I

< size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); }} 第4行代码首先将当前对象的非 static 修饰，非 transient 修饰的字段写出到流中；第6行将写出元素的个数作为容量。 接下来就是通过循环将包含的所有元素写出到流，在这一步可以看出 ArrayList 在自己实现的序列化方法中没有将无存储数据的内存空间进行序列化，节省了空间和时间。 同样地，在反序列化中根据读进来的流数据中获取 size 属性，然后进行数组的扩容，最后将流数据中读到的所有元素数据存放到持有的对象数组中。 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; s.defaultReadObject(); s.readInt(); // ignored if (size >

0) {int capacity = calculateCapacity (elementData, size); SharedSecrets.getJavaOISAccess (). CheckArray (s, Object [] .class, capacity); ensureCapacityInternal (size); Object [] a = elementData; for (int I = 0; I < size; iTunes +) {a [I] = s.readObject ();}} about copying

For copies of list elements, ArrayList provides a custom clone implementation as follows:

Public Object clone () {try {ArrayList v = (ArrayList) super.clone (); v.elementData = Arrays.copyOf (elementData, size); v.modCount = 0; return v;} catch (CloneNotSupportedException e) {/ / this shouldn't happen, since we are Cloneable throw new InternalError (e);}}

It can be clearly seen from the above code that the copyOf operation performed is a shallow copy operation, and the elements of the original ArrayList object will not be copied to the new ArrayList object and then returned. Each location in their respective fields elementData will store references to the same element. Once which list modifies an element in the array, another list will also be affected.

ArrayList after JDK 1.8

After analyzing the features of ArrayList from a source point of view, let's take a look at any new changes in the ArrayList class since JDK 1.8.

New removeIf method

RemoveIf is an interface method added to the Collection interface, and ArrayList also has this method because the parent class implements the interface. The removeIf method is used to remove elements from the array for the specified condition.

Public boolean removeIf (Predicate

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.