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

This article starts with ArrayList

The reference code is jdk1 6_ 45 jdk1. 7_ 80 jdk1. 8_ 111 source code, comparative reading, found modified problems and improvement points.

public class ArrayList
extends AbstractList

implements List

,RandomAccess,Cloneable,java. io. Serializable

1、 Basic properties

1. The underlying layer uses the native array implementation to implement the randomaccess interface, which can be accessed randomly. Random access refers to the subscript index operation, and the time complexity of index (I) is O (1).

The operations of size, isempty, get, set, iterator and listiterator are completed in O (1), and the add (E) operation is completed in O (1) on average, that is, adding n elements takes O (n) time (this is collection.add, which is added at the end. Note the distinction between list. Add (index, e)). Other operations are basically completed in O (n). Compared with the LinkedList implementation, the constant factor of the time complexity of each method of O (n) is smaller.

2. Because the capacity of the underlying array elementdata cannot be changed, when the capacity is insufficient, you need to replace elementdata with a larger array. This process is called capacity expansion. The actual number of elements, size, will never exceed the capacity of the underlying array elementdata Length, because the expansion requires more memory and a copy of the original array, the expansion is a time-consuming operation. Before adding a large number of elements, users should estimate an approximate number and manually call ensurecapacity for a capacity expansion operation to avoid frequent capacity expansion and performance impact caused by one addition.

3. ArrayList is unsynchronized. External synchronization is required when multithreading reads and writes concurrently. If external synchronization is not required, you can use collections The synchronizedlist method encapsulates an instance of ArrayList, or uses vector.

4. There are no restrictions on stored elements, and null elements are allowed.

5. The iterators returned by the iterator and listiterator methods of ArrayList fail quickly, that is, if they are structurally modified at any time after the iterator is created, the iterator will directly throw a concurrentmodificationexception in addition to the iterator's own remove or add methods, so as to achieve the purpose of fast failure, Try to avoid uncertain behavior.

The fast failure behavior of the iterator of ArrayList cannot be strictly guaranteed. When modifying concurrently, it will try but not 100% guarantee to throw a concurrentmodificationexception. Therefore, the correctness of the code that depends on this exception is not guaranteed, and the fast failure behavior of the iterator should only be used to detect bugs.

6. To implement the clone interface, you can call its clone method (although clone () is a method in object, it is protected. Clone () using a subclass must override this method in the subclass). Clone method copies an ArrayList. The underlying array elementdata is not shared, but the actual elements are still shared. However, clone is overwritten in ArrayList and does not belong to the method in list. Therefore, the common declaration form is list < string > STRs = new ArrayList < > (); The declared variables cannot directly use the clone method, and they are rarely used.

7. Implement the serializable interface, which can be serialized. ArrayList "implements" a custom serialization method, mainly to save space. For the large header of the occupied space - the element list, only the elements of the actual size are serialized, and the useless attributes for the new object - the modcount from the parent class abstractlist are not serialized. The actual size of ArrayList will not exceed the length of the underlying array. In most cases, it is smaller than the length of the underlying array. If default serialization is used, the entire underlying array will be serialized directly. After serialization, the byte stream will become larger and waste space.

2、 Construction method

1. Default construction method, arraylist()

About the default construction method, You may have seen this statement elsewhere: the size (capacity) of the underlying array elementdata of the ArrayList constructed by the parameterless constructor (the default constructor) is 10 by default. Here, I tell you that this is not necessarily true. This statement is true in version 1.6 (I didn't see the previous version). There is a problem with this sentence since 1.7. Below, I post three versions of code: JDK1.6, which is initialized to 10 capacities.

jdk1. 7, compared with version 1.6, introduces a new constant empty_ Elementdata, which is an empty array, so the capacity is 0.

jdk1. 8, compared with version 1.7, a new constant default capability is introduced_ EMPTY_ Elementdata, which is also an empty array, so the capacity is also 0. As for the difference between two empty arrays, see the following point.

As can be seen from the comparison: jdk1 The size of the underlying array elementdata of the ArrayList constructed by the parameterless construction method (default construction method) of 6 (capacity) is 10 by default. Starting from 1.7, the size of the underlying array elementdata of the ArrayList constructed by the parameterless construction method is 0 by default. The Java collection class basically has a change in jdk1.7: lazy initialization. Lazy initialization refers to the collection class constructed by the default construction method, which occupies as little memory space as possible (for ArrayList, the empty array is used to occupy as little space as possible, and null is not used to avoid null judgment). The real initialization is only carried out when the operation including adding semantics is carried out for the first time.

ArrayList starting from 1.7 is an instance constructed by the default construction method. The underlying array is an empty array with a capacity of 0. It will not really assign a non empty value to the underlying array until the first add / addall operation. If the element added by add / addall is less than 10, expand the elementdata array to 10 element sizes, Otherwise, use a size that is just right (for example, if you add 6 addall for the first time, the capacity will be expanded to 10, and if you add more than 10 for the first time, for example, 24, the capacity will be expanded to 24, which is just right); in version 1.8, the behavior of the default constructed instance has not changed, but the name of the array used has changed.

By the way, JDK: can you make complaints about the default construction method? The behavior of the default construction method has changed. You still use the annotation before!!!

2. Construction method with initial capacity, public ArrayList (int initialCapacity)

678 the actual behavior of this construction method in the three versions is basically the same: if initialCapacity > = 0, assign the underlying array elementdata to an array with the size of initialCapacity, and all elements of the array are null by default. 1.8 is slightly optimized. It is also assigned to an empty array, but the constant object is reused. Let's write a simple example to see a subtle difference.

jdk1. New ArrayList in 6 () followed by new ArrayList (10) as like as two peas, new ArrayList () and new ArrayList < > (0), although the underlying content and capacity are the same after creation, the actual behavior is slightly different, that is, the two have different strategies during the first automatic capacity expansion. However, this has little impact and basically does not affect the use. The use of two empty arrays in 1.8, as mentioned in the note, is to optimize (avoid creating useless empty arrays) while retaining the difference between their initial expansion strategies. If only one empty array is used, it can no longer be optimized and the cell type can be maintained.

3. Collection copy construction method, public ArrayList (collection C)

The relationship between the three versions of 678 is the same as point 2.

For the comments in the middle line, you can see this blog post