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

This article focuses on "how to solve the ArrayList collection container problem", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to solve the ArrayList collection container problem.

ArrayList step on the pit

First of all, let's take a look at what's wrong with this code?

In fact, in most cases, this is nothing more than writing data to the ArrayList in a loop.

But in special cases, such as when the data returned by getData () here is very large, there will be a problem with the subsequent temp.add (str).

For example, when we find that the data returned here can sometimes be as high as 2000W in the review code, the problem of ArrayList writing is highlighted.

Pit filling guide

Everyone knows that ArrayList is implemented by arrays, and the length of the data is limited; you need to expand the array at the right time.

Here, take insertion into the tail as an example, add (E e).

ArrayList temp = new ArrayList (2); temp.add ("1"); temp.add ("2"); temp.add ("3")

When we initialize an ArrayList of length 2 and write three pieces of data into it, the ArrayList has to be expanded, that is, a copy of the previous data is copied into a new array of length 3.

It is 3 because the new length = the original length * 1.5

We can know from the source code that the default length of ArrayList is 10.

Image

But you don't actually create an array of DEFAULT_CAPACITY = 10 at initialization.

Instead, the capacity will be expanded to 10 when you add * * data inside.

Now that you know that the default length is 10, it means that once you write to the ninth element, it will be expanded to 10: 1. 5 = 15.

This step is for array replication, that is, to open up a new memory space to store the 15 arrays.

Once we write frequently and in a large number, it will lead to a lot of array replication, which is extremely inefficient.

But we can avoid this problem in advance if we know in advance how many pieces of data might be written.

For example, when we write 1000W pieces of data into it, there is a huge performance gap between the given array length at initialization and the default length of 10.

I verified it with the JMH benchmark as follows:

From the results, you can see that the preset length is much more efficient than using the default (Score here refers to the time taken to complete the execution of the function).

So here is a strong recommendation: when a large amount of data is written to ArrayList, be sure to initialize the specified length.

Another is to be careful to use add (int index, E element) to write data to the specified location.

From the source code, we can see that each write will move the data after the index back, in fact, the essence is to copy the array.

However, instead of writing data to the end of the array, it replicates the array every time, which is extremely inefficient.

LinkedList

When it comes to ArrayList, you have to talk about LinkedList, the twin brothers; although they are all containers for List, the essential implementation is completely different.

LinkedList is made up of linked lists, and each node has a head and tail that refer to the front and back nodes, respectively; so it is also a two-way linked list.

So in theory, its write is very efficient, there will be no extremely inefficient array replication in ArrayList, and you just need to move the pointer each time.

If you are lazy here, you will not draw pictures, and you will make up for it on your own.

Comparative test

It has been rumored that:

LinkedList is more efficient than ArrayList in writing, so it is very suitable for LinkedList when writing is greater than reading.

The test here is to see if the conclusion is consistent; similarly, 1000W data are written to LinkedList, and the ArrayList efficiency of initializing the array length is significantly higher than that of LinkedList.

But the premise here is to preset the array length of ArrayList in advance to avoid array expansion, so that the writing efficiency of ArrayList is very high, while LinkedList does not need to copy memory, but it needs to create objects, transform pointers and other operations.

Needless to say about the query, ArrayList can support subscript random access, which is very efficient.

LinkedList does not support subscript access because the underlying layer is not an array. Instead, it needs to determine whether to traverse from the beginning or from the end according to the location of the query index.

But either way, you have to move the pointer to traverse one by one, especially when the index is close to the middle.

At this point, I believe you have a deeper understanding of "how to solve the ArrayList collection container problem". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.