This is the 19th day of my participation in the More text Challenge. For details, see more text Challenge

Author: JavaGieGie

Wechat official account: Java Development zero to one

preface

Gie guess that all Java friends have used, if there are friends who have not used, please leave a message at the end of the article, you can stay for me after school, I will give you a tutorial. This article is the first in a series on collection classes, starting with a relatively simple and familiar ArrayList. Collections are a very important and fundamental part of Java, because the only thing that is essential to any data is how it is stored, and the purpose of collections is to organize and store data in a certain way.

The body of the

Dog Leftover: Flower Gie, the new series has started, and I’m a little excited!

After all, liver at the same time several series, is also a bit to die, you see my this increasingly bright head, ah, what also do not say.

Dog left son:…. After the province of shampoo you, hold back nonsense, tell me about learning collection I want to pay attention to which points!

(Touching the smooth top of the head, thoughtful) As for the collection, I think the following four points should be focused on:

  • Whether empty is allowed
  • Whether to allow duplicate data
  • Ordered or not, ordered means that the order in which the data is read is consistent with the order in which the data is stored
  • Thread Safe or not

Can you tell me how to use ArrayList?

First take a look at his new element method add(), which is very simple. It looks like this:

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
Copy the code

Dog leftover son: look at be quite simple, that say next add how to realize at bottom!

. Suddenly? Straight to the heart. All right, here we go

Look at the source code for the add method:

The ensureCapacity method in line 2 is used for scaling, so I’ll leave that alone. When the add method is called, the bottom layer is simply adding data somewhere in elementData, which looks like this:

It is important to note that elementData should store references to elements in the heap, not the actual elements. Gie is used to draw this diagram for the sake of understanding, as long as you know this problem.

How does ensureCapacity work?

Yo hoo, dog son today when the interviewer, also know to cross-examine. When we construct an ArrayList, the default underlying array size is 10:

Since the size is fixed, what if the underlying array is not big enough? ArrayList is a dynamic array, which means that the size of the underlying array is not fixed, but is determined by the size of the added elements. If it is not enough, it is dynamically expanded. The code for this expansion is in ensureCapacity:

 private void grow(int minCapacity) {
     //1. Obtain the array length
     int oldCapacity = elementData.length;
     
     //oldCapacity >> 1 is the same as dividing by 2
     //2. New array capacity = original array capacity * 1.5.
     int newCapacity = oldCapacity + (oldCapacity >> 1);
     
     //3. If the capacity of the new array is less than minCapacity, the capacity of the new array is the capacity of the passed parameter.
     if (newCapacity - minCapacity < 0)
         newCapacity = minCapacity;
     
     //4. Determine whether the new array capacity newCapacity is greater than the maximum number of elements that the array can hold MAX_ARRAY_SIZE
     if (newCapacity - MAX_ARRAY_SIZE > 0)
         / / 5.
         newCapacity = hugeCapacity(minCapacity);
     
     //6. Put the array before expansion into the new array after expansion
     elementData = Arrays.copyOf(elementData, newCapacity);
 }
Copy the code

Step 5: hugeCapacity(minCapacity) determine if minCapacity is greater than MAX_ARRAY_SIZE. If minCapacity is greater than MAX_ARRAY_SIZE, If newCapacity is equal to Integer.MAX_VALUE, otherwise newCapacity is equal to MAX_ARRAY_SIZE

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}
Copy the code

Dog leftover son: feel very simple expand way, that why want to use this kind of way expand?

Big guys of order, I can answer out how expand of not enough strong yao, still ask why, you are 100 thousand why.

The dog is left son: answer right salary add 500

Oh, well, that should be easy.

We can think:

1, if the one-time expansion is too large, will inevitably cause a waste of memory space

2. If the one-time expansion is not enough, then the next expansion operation will inevitably come quickly, which will reduce the operation efficiency of the program. We should know that expansion is still a performance consuming operation

So how much to expand is a trade-off between time and space made by JDK developers, and a reasonable value is provided. The last one we call is the copyOf method of Arrays, which copies the contents of the element groups into the new array:

It looks like this on a graph:

Dog leftover son: with the picture is great, give you a yao yao da, in addition to the order to add elements, there must be in accordance with the subscript inserted

ArrayList inserts also call the add method, such as:

List<String> list = new ArrayList<>();
list.add("111");
list.add("222");
list.add("333");
list.add("444");
list.add("555");
list.add("666");
list.add("777");
list.add("888");
list.add(2."000");
System.out.println(list);
Copy the code

One thing to be sure about is that the add method on line 10 means to insert data at any subscript, such as line 10, which is to insert data 000 at index 2 (note that ArrayList subscript starts at 0, i.e., list.get(0) is 111). Take a look at the run results to prove the point:

[111, 222, 000, 333, 444, 555, 666, 777, 888]
Copy the code

Again, let’s look at what we do when we insert it:

You can see that when you insert, you first use the ensureCapacity method to determine whether to expand the size of the specified location, then use the System.arrayCopy method to copy all the elements from the specified location, move backward one place, and then set the element at the specified location to the element you want to insert. An insert operation is completed. Graphically, the process looks like this:

Dog leftover son: yo ~ good, that say again delete element!

ArrayList can be deleted in the following two ways:

  • Delete by subscript, i.e. List.remove (1)

  • Remove (“111”). If there are more than one equivalent element 111, only the first matching element will be removed

From the code, the two delete methods are implemented in the same way in ArrayList. They both call the following code:

There are only two things that are being done in a nutshell:

  1. Move all elements after the specified element forward by one position using the System. Arraycopy method

  2. The element in the last position is specified as NULL so that gc can reclaim it

For example, now we operate on this code:

List<String> list = new ArrayList<>();
list.add("111");
list.add("222");
list.add("333");
list.add("444");
list.add("555");
list.add("666");
list.add("777");
list.add("888");
list.remove("3333");
Copy the code

Represented by a graph, it is:

Dog leftover son: then you summarize the characteristics of ArrayList bai!

ArrayList is a collection that is implemented as an array. Let’s take a look at the basic elements of an ArrayList.

Yuan, As with
private transient Object[] elementData; ArrayList is an implementation based on arrays, and elementData is the underlying array
private int size; The number of elements in an ArrayList increases or decreases according to the number of calls to add or remove, so add a null to the ArrayList increases the size by 1

ArrayList properties:

Belong to sex conclusion
ArrayL WHETHER an IST can be empty allow
ArrayList Specifies whether to allow duplicate data allow
Whether the ArrayList is ordered The orderly
ArrayList is thread safe Non-thread safe

Dog leftover son: said so much, that ArrayList has what advantages and disadvantages ah

Nothing is perfect, and we need to use ArrayList appropriately for our scenarios. The advantages of ArrayList are as follows:

  1. ArrayList is implemented as an array, a RandomAccess mode, and it implements the RandomAccess interface, so the lookup, or get, is very fast
  2. ArrayList is very handy when you add an element in order, you just add an element to the array

But the downside of ArrayLists is obvious:

  1. Deleting an element involves a single element copy, which can be performance intensive if there are many elements to copy

  2. Inserting an element involves a single copy of the element, which can be performance intensive if there are many elements to copy

So, to summarize, ArrayList is a good fit for sequential add, random access scenarios.

Expand the part

Here is a question that has puzzled me for a long time: why is ArrayList elementData transient modified?

This is almost beyond my knowledge, but I’m glad Gie read the secret book last night.

Let’s look at the definition of ArrayList:

ArrayList implements the Serializable interface, which means that ArrayList can be serialized, and using transient to decorate elementData means THAT I don’t want the elementData array to be serialized.

This ten thousand grass mud horse pentium, can’t panic? Because elementData is not necessarily full when I serialize the ArrayList, say, elementData has a size of 10, but I only use three of them, is it necessary to serialize the entire elementData? This is obviously not necessary, so ArrayList overrides the writeObject method:

Each time you call this method for serialization, you first call the defaultWriteObject() method to serialize the non-transient elements in the ArrayList, elementData does not serialize it, and then iterate through elementData, serializing only those elements that are present. This will have two advantages:

  1. Speed up serialization

  2. Reduced the serialized file size

conclusion

So you know how important arrayLists are, so I’m not going to go into this. When we read the source code, in fact, there are a lot of can be worth our reference, such as elementData transient to modify, learning need to think more, the learned technology and ideas to apply to their own actual development, learning for use, in order to continue to be powerful.

Pay attention to avoid getting lost

That’s all for this episode. If you have any mistakes, please leave a comment. Thank you very much. I’m GieGie Flower, feel free to leave a comment if you have any questions, and we’ll see you next time at 🦮.

+++

The article continues to be updated, can be wechat search Java development zero to one first time to read, and can obtain interview materials learning videos, interested partners welcome attention, study together, ha 🐮🥃.

Original is not easy, how can you bear white whore. if you think this article is a little useful to you, thank you for the old iron for this article point a like, comment or forward, because this will be my power to output more quality articles, thank you!