[introduction to Java] day21 Java container class (IV) ArrayList source code analysis

Today we will introduce ArrayList, the most commonly used implementation class in the list interface. The source code analysis of this article is based on jdk8. If there is any inconsistency, you can switch to jdk8 before operation.

The content of this article mainly includes these parts:

　　1. Introduction to source code structure

　　2. Source code display

　　3. Key points

　　4. Description of advantages and disadvantages

1、 Introduction to source code structure

Compared with the previous interface source code, the source code of ArrayList is not the same. More than 1000 lines of code are really laborious if you look directly, but if you look carefully, you will find that the general structure is as follows:

There are four internal classes:

Arraylistsplitter: ArrayList separable iterator, a separable iterator based on dichotomy, is an iterator designed to traverse elements in parallel, jdk1 The data structures in the collection framework in 8 implement splitter by default.

ITR: iterator that implements iterator interface and optimizes ArrayList.

Listitr: an iterator that implements the listiterator interface to optimize ArrayList.

Sublist: implements the sublist of abstractlist and randomaccess interfaces.

These four internal classes account for nearly half of the space, which shows their importance. The first three of these four classes are related to iterators, and the last is a sublist class designed to deal with local lists.

2、 Source code presentation:

The following is the source code of the lame translation explanation version:

Seriously, I've tried my best.

3、 Key points

This part is mainly explained according to the above source code. If there is something unclear, you can return to the above source code for viewing.

　　1. In fact, ArrayList only internally maintains an array, which simplifies the operation by exposing a convenient interface.

　　2. In ArrayList, size and capacity are two different things. Size represents the number of elements actually stored in the list, which is generally less than the length of the internal array, while capacity represents the capacity, that is, the length of the internal array.

　　3. In ArrayList, the default size is 10. When you use new arraylist(); The array will not be allocated space of size 10 immediately, but will not be allocated until the first element is inserted. This is to save memory space.

　　4. Due to the above purpose, in order to distinguish between the default list and the empty list, two empty array constants, empty, are set_ Elementdata and defaultprotocol_ EMPTY_ Elementdata, so that different processing can be performed during capacity expansion.

　　5. When maintaining internal arrays, arrays. Is used Copyof() method and system Arraycopy() method.

　　6. Modcount is used in many places. This variable actually inherits from the parent class abstractlist, It is used to identify the number of times the size of the array inside the list has been modified (such as add, trimtosize and other operations may be triggered). The replacement of the element will not change its value. The "fail fast" of the iterator The mechanism is closely related to this modcount variable. In general, expectedmodcount = modcount will be assigned once before the operation; After the operations are executed, perform another detection. If they are still equal, the structure has not changed, otherwise an exception will be thrown, which is why the operation iterator will throw an exception after the ArrayList was modified in the previous article.

　　7. During capacity expansion, the default capacity expansion factor is 1.5. Each time capacity expansion is required, 1.5 times the original array size will be compared with the actual array space, and the maximum value will be taken as the array size. Then create a new array and copy all the elements in the original array to the new array. Therefore, capacity expansion is actually the most time-consuming operation, which requires not only reallocation of space, but also re assignment.

　　8. Because the methods of ArrayList operate on the same internal array, and all methods are not locked and have no synchronization mechanism, it is thread unsafe.

　　9. ArrayList can store null values, which can be seen in the source code. Null values are processed during comparison.

4、 Description of advantages and disadvantages

Because the list is actually an internal maintenance and management array, it has the advantages of array. Of course, the disadvantages of arrays also exist.

Array is to store elements in memory continuously. Since each element occupies the same memory, you can quickly access any element in the array through subscript. However, if you want to add an element to the array, you need to move a large number of elements, empty the space of an element in memory, and then put the element to be added in it. Similarly, if you want to delete an element, you also need to move a large number of elements to fill out the moved elements.

However, when maintaining this internal array, the list still takes some care. For example, the concept of capacity is used to reduce the number of array structure changes, so the structure will not change every time the add operation is performed. Selecting the expansion factor of 1.5 instead of 2 is also to save space as much as possible on the premise of meeting the requirements. However, if you know the approximate number of elements in advance, you'd better set the capacity of the list in the constructor first, so as to save a lot of overhead during expansion.

Hoo. This article has been prepared for two days. I hope it can help you. If there is anything missing or not clear enough, you are welcome to point out. If you have wrong knowledge points, please don't be stingy and welcome correction.

For the sake of my hard work, let's give a little praise. You are also welcome to pay attention to my blog, which will be updated continuously in the future.