Java improvement Part 10 in-depth analysis of ArrayList

In the previous chapter, we introduced the class diagram of the collection. In this section, we will learn the most commonly used subclass ArrayList class in the collection interface, This chapter is divided into the following parts to explain (explain the JDK1.6 source code used in this chapter for analysis, because I think that although JDK1.8 has been partially changed, it still changes. I still use the introduction of JDK1.6 for optimization, so I learned 1.6 and understood 1.8).

1、 Common features of ArrayList

Before analyzing the source code of ArrayList, let's take a look at the common functions of ArrayList:

As can be seen from the above, in addition to inheriting the methods in the parent collection interface, the ArrayList interface also implements the extended index related methods in the list interface, which all stem from its underlying array structure.

2、 Important properties of ArrayList

The above section lists some common function methods in ArrayList, and how to use these methods. Next, we will analyze the source code. Before analyzing, we can think for ourselves. We know that ArrayList is a dynamically extended collection, The reason why the dynamic expansion is stronger than the array is that the length of the array is fixed and cannot be extended. This is the biggest defect of the array, so there is a set. Then ArrayList, its bottom layer must also adopt the array structure, because it is called ArrayList. One of its important properties must be the definition of an array. As follows:

ArrayList is a collection implemented in the form of an array. The functions of its elements are:

private transient Object[] elementData; // ArrayList is an implementation based on array, and elementdata is the underlying array

private int size; // The number of elements in the ArrayList. Note here that the size increases or decreases automatically according to the number of calls to the add and remove methods. Therefore, when a null is added into the ArrayList, the size will also increase by 1

3、 Analysis of construction method of ArrayList

After analyzing the above attributes, let's look at the construction method of ArrayList:

You can see that ArrayList provides three construction methods. Their respective meanings have been annotated on the code. Then think about the meaning of the construction method of specifying the capacity. Since the default is 10, why provide a construction method that can specify the capacity? Think about it, and we'll talk about it.

4、 Analysis of common methods of ArrayList

1. Add add element

There are four methods added. Let's analyze their function source code:

2. Remove delete

analysis:

The addition and deletion methods are explained here. The code is very simple. There are two main areas that need special attention: 1 Array expansion, 2 Array copy, these two operations are extremely inefficient. In the worst case (adding to the first position of the list, deleting the last element of the list or deleting the element of the first index position of the list), the time complexity can reach o (n).

Remember the pit above (why do you provide a construction method that can specify the capacity)? Is it a little clear here? Let's explain briefly: if the initial test capacity of the array is too small, assume the default size of 10, and when we use the main operation of ArrayList, we add elements, constantly increase, constantly increase, and the above consequences will occur? That is, the array capacity is not stable The array needs constant capacity expansion. The process of capacity expansion is array copy system In the process of arraycopy, each expansion will open up a new memory space and data replication and movement, which is bound to have an impact on performance. In this write based scenario (write will expand capacity, delete will not shrink capacity), setting a large capacity in advance can reduce the number of capacity expansion and improve performance.

Array expansion is accompanied by opening up a new memory space to create a new array and then copy the data. Array replication does not need to open up a new memory space, but just copy the data.

As mentioned above, adding elements may expand the capacity, but deleting elements will not shrink the capacity. What happens if you use the list in the deleted scenario and keep deleting and rarely add? Or after a large expansion of the array, we only use a few spaces later. Will the above situation occur? Of course, it's a waste of space. Lala, what should I do?

3. Update set

4. Find

Since ArrayList is implemented using arrays, updating and searching are directly based on subscript operations, which becomes very simple.

5. Whether it includes

Contains mainly checks indexof, that is, the index position of the element in the list, that is, the array subscript. Then, check whether the indexof and lastIndexOf codes are familiar. Yes, like the code of public Boolean move (object o), they are element null judgment and circular comparison.

6. Capacity judgment

Note: what does modcount do, how to operate this variable everywhere, and traversal? Why not? Because the iterator traversal is relatively complex, and the iterator is an important one of the classic GOF design patterns, the iterator will be analyzed separately later.

5、 Advantages and disadvantages of transient analysis and ArrayList

1. Advantages and disadvantages of ArrayList

1. The bottom layer of ArrayList is implemented in array, which is a random access mode. In addition, it implements the randomaccess interface, so it is very fast to find, that is, get

2. ArrayList is very convenient to add an element in sequence, just adding an element to the array

However, the disadvantages of ArrayList are also obvious:

1. Deleting elements involves one element copy. If there are many elements to be copied, it will cost more performance

2. When inserting elements, it involves one element copy. If there are many elements to be copied, it will cost more performance

Therefore, ArrayList is more suitable for scenes with sequential addition and random access.

2. Difference between ArrayList and vector

ArrayList is thread unsafe, which is obvious because all methods in ArrayList are not synchronized, and thread safety problems will occur under concurrency. So what if we want to use ArrayList and make it thread safe? One way is to use collections The synchronizedlist method turns your ArrayList into a thread safe list, such as:

Another method is vector, which is the thread safe version of ArrayList. 90% of its implementation is exactly the same as ArrayList. The difference is:

1. Vector is thread safe and ArrayList is thread unsafe

2. Vector can specify the growth factor. If the growth factor is specified, the new array size will be added to the original array size each time during capacity expansion; If the growth factor is not specified, the original array size is given

3. Why is elementdata of ArrayList modified with transient?

Why is elementdata decorated with transient? Let's take a look at the definition of ArrayList:

Seeing that ArrayList implements the serializable interface means that ArrayList can be serialized. Modifying elementdata with transient means that I don't want the elementdata array to be serialized. Why? Because when serializing ArrayList, the elementdata in ArrayList may not be full. For example, elementdata has a size of 10, but I only use three of them. Is it necessary to serialize the whole elementdata? Obviously, this is not necessary, so the writeobject method is overridden in ArrayList:

Call this method every time you serialize. First call the defaultwriteobject() method to serialize the non transient elements in the ArrayList. Elementdata does not serialize it, and then traverse elementdata to serialize only those elements. This is as follows:

1. Speed up serialization

2. Reduces the file size after serialization

6、 Write a myarraylist yourself

Note: others about jdk1 The difference between 6 and 1.7 and 1.8 can be seen:

JDK1. 8、JDK1. 7、JDK1. 6. Look here