🎓 Do your best and obey the destiny. The blogger is studying for a master’s degree in Southeast University. He loves fitness and basketball, and is willing to share what he sees and gains related to technology. He pays close attention to the public account @flying Veal, and gets the update of the article as soon as possible
🎁 This article has been included in the “CS-Wiki” Gitee official recommended project, has accumulated 1.5K + STAR, is committed to creating a perfect back-end knowledge system, in the road of technology to avoid detours, welcome friends to come to exchange and study
🍉 If you have no outstanding projects, you can refer to a project I wrote “Open source community system Echo” Gitee official recommended project, so far has accumulated 500+ star, SpringBoot + MyBatis + Redis + Kafka + Elasticsearch + Spring Security +… And provide detailed development documents and supporting tutorials. Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo
Recently in preparation for the summer internship, so the surface of the brush is more, a few days ago saw a ashore the face of the friend to write, he said when he was in reviews knowledge (usually use mind mapping PIC), will write questions in the form of knowledge, rather than declarative sentence, so that you see in this sentence, to active thinking, rather than memorizing. I’ve been doing it for a few days and I’ve found that’s true. Here’s Amway for you guys. In addition, this article will guide the whole paper in the form of questions and answers.
1. ArrayList? What is it? Have a purpose?
As we all know, the Java Collection framework has two main interfaces: Collection and Map, among which the three children of Collection are List, Set and Queue. ArrayList implements the List interface, which is essentially an ArrayList, but as a Java collection framework, it can only store object reference types, which means that when we need to load basic data types such as ints and floats, we must convert them to the corresponding wrapper classes.
The underlying implementation of ArrayList is an Object array:
Since it is based on arrays, arrays in memory space is continuously allocated, it is inevitable that the query speed is very fast, but of course, it also can not escape the inefficient add and delete defects.
In addition, like ArrayList, we also implement the List interface, LinkedList is more commonly used. LinkedList is special in that it implements not only the List interface but also the Queue interface, so you can see that LinkedList is often used as a Queue:
Queue<Integer> queue = new LinkedList<>();
Copy the codeAs the name suggests, the underlying LinkedList is, of course, list-based, and it’s a two-way list. The properties of linked lists and arrays are exactly the opposite, because there is no index, so the query efficiency is low, but the speed of adding and deleting.
2. How does ArrayList specify the underlying array size?
OK, first of all, since the real place to store data is array, when we initialize ArrayList, we naturally allocate a size to the array and create a memory space. Let’s start with the no-argument constructor for ArrayList:
As you can see, it assigns a default empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA to the underlying Object array, elementData. That is, after the ArrayList is initialized with the no-argument constructor, its array capacity at the time is 0.
What’s the use of initializing an array with capacity 0? You can’t save anything? Don’t worry, if we use the no-argument constructor to initialize the ArrayList, the array will be assigned a default initial capacity of DEFAULT_CAPACITY = 10 only when we actually add the data. See below:
The parameterless constructor of an ArrayList is pretty much the same as the size of the array passed in by the user:
3. Once the size of an array is specified, it cannot be changed. How does an ArrayList expand the underlying array?
The underlying implementation of an ArrayList is an Object array, and we know that once the size of an array is specified, it cannot be changed. So how does ArrayList scale up if we keep adding data to it? Or how is an ArrayList implemented to hold any number of objects?
OK, when is expansion happening? That’s definitely when we add a new element to the array and find that the array is full. That’s right, let’s go to the add method and see how ArrayList does this:
EnsureExplicitCapacity Determines whether expansion is required. Obviously, the grow method is the key to expansion:
To be honest, look no further than the yellow box in the figure above to see how ArrayList is expanded: The expanded array length = the current array length + the current array length / 2. Array. copyOf creates a new array and then copies it.
Here’s an example:
4. Since capacity expansion happens when data is added, how does ArrayList add data
OK, we are just in the middle of the add method. Before adding data, we will judge whether it needs to be expanded. The real operation of adding data is in the next part:
Add (int index, E Element) inserts element at index. Arraylist.add (0, 3), for example, means to insert element 3 in the header.
Take a look at the core of the Add method, System.arrayCopy, which takes five parameters:
- ElementData: Source array
- Index: The location in the source array from which the copy starts
- ElementData: Target array
- Index + 1: the location in the target array to copy to
- Size-index: the number of array elements in the source array to copy
To explain what arrayCopy means in the above code, for example, if we want to insert an element at index = 5, we will first copy the source array elementData (let’s call it a new array), Then place the elements from the source array at index = 5 to the end of the array at index + 1 = 6:
This gives space for the new element to be added, and completes the addition by placing element Element at index = 5:
Obviously, needless to say, an ArrayList’s ability to insert data into a specified location is very slow, since creating new array copy elements is even slower when scaling is involved.
ArrayList also has a built-in add method that adds elements directly to the end of the ArrayList. Instead of copying the array, just add the size ++ method, which is probably the most common method we use:
5. How does an ArrayList delete data?
Ctrl + F find the remove method, right there? Just like adding, you copy an array
For example, if we want to delete the element whose index = 5 from the array, we first copy the source array and place the elements from index + 1 = 6 to the end of the array at the index = 5 of the new array:
That is, the index = 5 element is overwritten, giving you the impression of being deleted. Similarly, it is naturally very inefficient
6. Is ArrayList thread-safe? Signs of insecurity
ArrayList and LinkedList are not thread-safe. Let’s use the add method, which adds elements to the end, as an example to see how an ArrayList thread is not safe:
The yellow box is not an atomic operation, it consists of two steps:
elementData[size] = e;
size = size + 1;
Copy the codeWhen executing these two pieces of code in a single thread, that’s fine, of course, but when executing in a multithreaded environment, it can happen that a value added by one thread overwrites a value added by another. Here’s an example:
- Assuming size = 0, we’re going to add elements to the end of this array
- Thread A starts adding an element with the value A. It now performs the first operation, placing A in the array elementData with subscript 0
- Then thread B just happens to start adding an element of value B, and gets to the first step. Thread B still gets the size value of 0, so it also places B at elementData subscript 0
- Thread A starts incrementing size, size = 1
- Thread B starts incrementing size, size = 2
After thread A and thread B have finished executing, the ideal situation should be size = 2, elementData[0] = A, elementData[1] = B. Instead, size = 2, elementData[0] = B (thread B overwrites thread A’s operations), and there is nothing at subscript 1. And unless we use the set method to change the value of subscript 1, this position will remain null, because adding elements at the end will start at size = 2.
Verify the following code:
The result is the same as our analysis:
The thread-safe version of ArrayList is Vector, which is implemented simply by adding synchronized to all its methods:
Since it requires additional overhead to maintain synchronization locks, it is theoretically slower than ArrayList.
7. Why use it when threads are unsafe?
Because in most scenarios, the queries are more frequent and do not involve frequent additions or deletions. So if it does involve frequent additions and deletions, you can use LinkedList, the underlying list implementation, for additions and deletions. If you must be thread-safe, use Vector. Of course, the most used in the actual development is ArrayList, although the thread is not safe, inefficient to add and delete, but efficient query ah.
| flying veal 🎉 pay close attention to the public, get updates immediately
- The blogger is a master student in Southeast University. In her spare time, she runs a public account “Flying Veal”, which was opened on December 29, 2020/29. Focus on sharing computer basics (data structure + algorithm + computer network + database + operating system + Linux), Java basics and interview guide related original technical good articles. The purpose of this public account is to let you can quickly grasp the key knowledge, targeted. I hope you can support me and grow with veal 😃
- And recommend personal maintenance of open source tutorial project: CS-Wiki (Gitee recommended project, has accumulated 1.5K + STAR), is committed to creating a perfect back-end knowledge system, in the road of technology to avoid detours, welcome friends to come to exchange learning ~ 😊
- If you don’t have any outstanding projects, you can refer to the Gitee official recommended project of “Open Source Community System Echo” written by me, which has accumulated 500+ star so far. SpringBoot + MyBatis + Redis + Kafka + Elasticsearch + Spring Security +… And provide detailed development documents and supporting tutorials. Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo Echo