ArrayList analysis of JDK collection source code (with an example of interview questions)
1. ArrayList inheritance system
ArrayList is also called dynamic array. The bottom layer is a List based on array. The difference between ArrayList and array is that it has the ability of dynamic expansion. As can be seen from the inheritance system diagram.
ArrayList:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
...
}
- List, RandomAccess, clonable, java.io.Serializable and other interfaces are implemented
- List is implemented, with basic operations such as adding, deleting and traversing
- RandomAccess is realized, which has the ability of random access
- It implements serializable and can be serialized
2. ArrayList implements Cloneable, RandomAccess and Serializable interfaces
Implement clonable interface, which can be shallow copied
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
**Friends who want to know more about deep copy and shallow copy can go to this blog:** https://www.cnblogs.com/gesh-code/p/15246798.html
RandomAccess interface is implemented, which can improve the efficiency of random access list
ArrayList implements the RandomAccess interface, so the efficiency of random access list is higher than that of sequential access list. Let's take an example:
@Test
public void test01(){
ArrayList list=new ArrayList();
for (int i = 0; i <= 99999; i++) { //Add 100000 pieces of data to the collection
list.add(i);
}
//Test the efficiency of random access:
Long startTime=System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) { //Random access
//Access each element from the collection
list.get(i);
}
Long endTime=System.currentTimeMillis();
System.out.println("The time taken for random access execution is:"+(endTime-startTime));
//Test the efficiency of sequential access:
startTime=System.currentTimeMillis();
Iterator it=list.iterator(); //Sequential access, or enhanced for
while (it.hasNext()){
//Access each element from the collection
it.next();
}
endTime=System.currentTimeMillis();
System.out.println("Time taken to perform sequential access:"+(endTime-startTime));
}
View output results:
The time taken for random access execution is: 1 Time taken to perform sequential access: 4
It can be seen that the efficiency of random access of ArrayList implementing RandomAccess interface is higher than that of sequential access.
For comparison, let's take another look at the LinkedList set that does not implement the RandomAccess interface to test the efficiency comparison between random access and sequential access lists:
@Test
public void test02(){
LinkedList list=new LinkedList();
for (int i = 0; i <= 99999; i++) { //Add 100000 pieces of data to the collection
list.add(i);
}
//Test the efficiency of random access:
Long startTime=System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) { //Random access
//Access each element from the collection
list.get(i);
}
Long endTime=System.currentTimeMillis();
System.out.println("The time taken for random access execution is:"+(endTime-startTime));
//Test the efficiency of sequential access:
startTime=System.currentTimeMillis();
Iterator it=list.iterator(); //Sequential access, or enhanced for
while (it.hasNext()){
//Access each element from the collection
it.next();
}
endTime=System.currentTimeMillis();
System.out.println("Time taken to perform sequential access:"+(endTime-startTime));
}
View output results:
Time taken for random access execution: 3732 Time taken to perform sequential access: 1
It can be concluded from the results that the LinkedList set of RandomAccess interface is not implemented, and the efficiency of testing random access is far lower than that of sequential access.
3. ArrayList property
/**
* The default capacity is 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Empty array, used if the passed in capacity is 0
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* The default empty capacity array is 10 in length. It is used when passing in capacity and when adding the first element
* The default capacity size is restored
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array container in the collection that actually stores data elements
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* Number of elements in the collection
*/
private int size;
- **DEFAULT_ Capability: * * the default capacity of the collection is 10. When creating a List instance through new ArrayList(), the default capacity of the collection is 10
- **EMPTY_ELEMENTDATA: * * empty array, which is used when creating List collection instances through new ArrayList(0).
- **DEFAULTCAPACITY_EMPTY_ELEMENTDATA: * * the default capacity is an empty array. This empty array is used when creating a collection through the new ArrayList() parameterless construction method, which is the same as empty_ The difference of elementdata is that when adding the first element, the empty array will be initialized to default_ Capability (10) elements.
- **elementData: * * an array that stores data elements. It is decorated with transient. This field is not serialized.
- **size: * * the number of stored data elements. The length of elementData array is not the number of stored data elements.
4. ArrayList construction method
ArrayList(int initialCapacity) parameterized construction method
/**
* Construct an empty array with the specified initial capacity
* Pass in the initial capacity. If it is greater than 0, initialize elementData to the corresponding size. If it is equal to 0, use EMPTY_ELEMENTDATA empty array
* @param initialCapacity
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
ArrayList() null parameter construction method
/**
* Construct an empty array with an initial capacity of 10
* The initial capacity is not transmitted and is initialized to defaultcapability_ EMPTY_ Elementdata empty array
* When the first element is added, it will be expanded to the default size, that is, 10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
ArrayList(Collection c) parameterized construction method
/**
* Initializes the elements passed into the collection into the ArrayList
* @param c
*/
public ArrayList(Collection<? extends E> c) {
//Converts a collection parameter in a constructor to an array
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//Check whether the Object returned by c.toArray() is of type Object []. If not, copy it back to type Object[].class
if (elementData.getClass() != Object[].class)
//Creating and copying arrays
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//If c is an empty collection, it is initialized to an empty array EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
}
}
Question: why check whether the Object [] returned by c.toArray() is of type Object [], and copy it back to type Object[].class?
First of all, we all know that Object is a super parent class in java, and all classes inherit from Object indirectly or directly. Then let's take a look at an example:
public class ArrayListTest {
class Father{
}
class Son extends Father{
}
class MyList extends ArrayList<String>{
/**
* Subclasses override the methods of the parent class. The return values can be different, but only array types can be used here
* It can't be changed to Object. It should be a bug in java itself
* @return
*/
@Override
public String[] toArray() {
//For the convenience of examples, write them directly
return new String[]{"a","b","c"};
}
}
@Test
public void test01(){
Father[] fathers=new Son[]{};
//Output result: class [LArrayListTest$Son;
System.out.println(fathers.getClass());
List<String> list=new MyList();
//Output result: class [Ljava.lang.String;
System.out.println(list.toArray().getClass());
}
}
5.ArrayList related operation methods
Add (E) adds an element to the collection
Add the element to the end with an average time complexity of O(1):
/**
* Add the element to the end with an average time complexity of O(1)
* @param e
* @return
*/
public boolean add(E e) {
//For each element added, the size of minCacpacity is + 1, and check whether it needs to be expanded
ensureCapacityInternal(size + 1); // Increments modCount!!
//Insert the element to the last bit
elementData[size++] = e;
return true;
}
/**
* Calculate minimum capacity
* @param elementData
* @param minCapacity
* @return
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//If it is an empty array, defaultcopy_empty_elementdata
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//Returns the party with the largest DEFAULT_CAPACITY and minCapacity
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* Check whether capacity expansion is required
* @param minCapacity
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//Capacity expansion
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //The number of times the array structure has been modified
//When the data length of the storage element is less than the minimum capacity required
if (minCapacity - elementData.length > 0)
//Capacity expansion
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//The true capacity expansion method increases the increment to ensure that it can accommodate at least the number of elements specified by the minimum capacity parameter
private void grow(int minCapacity) {
//Original capacity
int oldCapacity = elementData.length;
//The new capacity is 1.5 times the old capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//If the new capacity has exceeded the maximum capacity of the array MAX_ARRAY_SIZE, the maximum capacity MAX_ARRAY_SIZE is used, and the maximum is MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//Copy out a new array with new capacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
//When the new capacity after expansion is greater than MAX_ARRAY_SIZE, ensure to use the maximum capacity
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Execution process:
- Check whether capacity expansion is required
- If elementData is equal to defaultcapability_empty_elementData, the initialization capacity is default_capability;
- Calculate the required minimum capacity through the calculateCapacity method. After determining the minimum capacity, continue to call ensureExplicitCapacity for capacity expansion
- When the capacity expansion method is really implemented, the new capacity of grow() is 1.5 times that of the old capacity (OldCapacity + (OldCapacity > > 1)). If so much is added and it is found that it is smaller than the required capacity, the required capacity shall prevail.
- Create an array of new capacity and copy the old array to the new array.
add(int index,E element) adds an element to the specified location
Add an element to the specified location. The average time complexity is O(n):
/**
* Add an element to the specified location with an average time complexity of O(n)
* @param index Specifies the index to insert
* @param element Element to insert
*/
public void add(int index, E element) {
//Check whether the subscript is out of bounds
rangeCheckForAdd(index);
//Check whether capacity expansion is required
ensureCapacityInternal(size + 1); // Increments modCount!!
//Move the index and its subsequent elements back one bit, and the index position will be empty
//The size index operation was performed twice
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//Insert the element at the location of the index
elementData[index] = element;
//Increase the number of elements by 1
size++;
}
/**
* Check for out of bounds
* @param index
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Execution process:
- Check whether the index is out of bounds
- Check whether capacity expansion is required
- Move the elements inserted into the index position back one bit
- Place the inserted element at the insertion index
- Number of elements + 1
addAll(Collection c) adds all elements in all collection parameters
Find the union of two sets:
/**
* Adds all the elements in the collection c to the current ArrayList
* @param c Collection to add
* @return
*/
public boolean addAll(Collection<? extends E> c) {
//Convert set c to an array
Object[] a = c.toArray();
int numNew = a.length;
//Check whether capacity expansion is required
ensureCapacityInternal(size + numNew); // Increments modCount
//Copy all the elements in set c to the end of the array
System.arraycopy(a, 0, elementData, size, numNew);
//The size of the number of elements in the collection increases by the size of c
size += numNew;
//If c is not empty, it returns true; otherwise, it returns false
return numNew != 0;
}
get(int index) gets the element at the specified index position
Gets the element at the specified index location with a time complexity of O(1).
/**
* Gets the element at the specified index location
* @param index Specify index location
* @return
*/
public E get(int index) {
//Check for out of bounds
rangeCheck(index);
//Returns the element at the index position of the array
return elementData(index);
}
/**
* Checks whether the given index is within the number of valid elements of the collection
* @param index Given index
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
Execution process:
- Check whether the index is out of bounds. Here, only check whether it is over the upper bound. If it is over the upper bound, throw indexoutofboundsexception (outofboundssg (index)); If the lower bound is crossed, an ArrayIndexOutOfBoundsException exception is thrown
- Returns the element at the index position (to be forced)
remove(int index) deletes the element at the specified index position
Delete the element at the specified index position with a time complexity of O(N).
/**
* Delete the element at the specified index position with a time complexity of O(n)
* @param index Specified index
* @return
*/
public E remove(int index) {
//Check for out of bounds
rangeCheck(index);
//Number of modifications to the underlying array structure of the collection + 1
modCount++;
//Gets the element at the index location
E oldValue = elementData(index);
//Number of elements to move
int numMoved = size - index - 1;
if (numMoved > 0)
//size index - 1 move operation was performed
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//Delete the last element to help GC
elementData[--size] = null; // clear to let GC do its work
//Returns the old value (that is, the deleted value)
return oldValue;
}
Note: from the source code, the ArrayList does not expand when deleting elements
remove (Object o) deletes the element with the specified element value
Delete the element with the specified element value, and the time complexity is O(n).
/**
* Delete the element with the specified element value, and the time complexity is O(n)
* The element (if any) to remove from this list
* @param o
* @return
*/
public boolean remove(Object o) {
if (o == null) {
//Traverse the entire array, find the position where the element first appears, and quickly delete it
for (int index = 0; index < size; index++)
//If the element to be deleted is null, compare it with null and use==
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//Traverse the entire array, find the position where the element first appears, and quickly delete it
for (int index = 0; index < size; index++)
//If the element to be deleted is not null, compare it and use the equals() method
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/**
* The special remove method skips the boundary check and does not return the deleted value
* @param index
*/
private void fastRemove(int index) {
//Number of modifications to the underlying array structure of the collection + 1
modCount++;
//If index is not the last bit, move the elements after index forward one bit in turn
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
Execution process:
-
Find the first element equal to the specified element value
-
Quick delete
Compared with remove(int index), fastRemove(int index) has fewer operations to check the index out of bounds. It can be seen that JDK has been doing performance optimization
Retain all (cooling C) find the intersection of two sets
/**
* Find the intersection of two sets
* @param c Collection object
* @return
*/
public boolean retainAll(Collection<?> c) {
//Collection object c cannot be null
Objects.requireNonNull(c);
//Batch deletion is adopted. In this case, true is passed in the completion to delete the elements not included in c
return batchRemove(c, true);
}
/**
* Batch delete elements
* @param c Collection object
* @param complement true to delete elements not contained in c
* complement false means to delete the elements contained in c
* @return
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
/**
* Use both read and write pointers to traverse the array at the same time
* The read pointer is incremented by 1 each time, and the write pointer is incremented by 1 when it is put into the element
* In this way, no additional space is required, just operate on the original array
*/
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//Traverse the entire array. If c contains this element, put the element at the position of the write pointer (subject to the completion)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
//Normally, r is finally equal to size unless c.contains() throws an exception
if (r != size) {
//If an exception occurs in c.contains(), all unread elements are copied to the write pointer
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
//Set the element after the write pointer to null to help GC
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
//The new size is equal to the position of the write pointer (because the write pointer is incremented by 1 every time, the new size is exactly equal to the position of the write pointer)
size = w;
modified = true;
}
}
//Return true if there is modification
return modified;
}
Execution process:
- Traversing the elementData array
- If the element is in c, add the element to the w position of the elementData array and move the w position one bit back
- After traversal, the elements before W are shared by both, and the elements after w (including) are not shared by both
- Set the elements after w (included) to null to facilitate GC recycling
removeAll (Collection c) find the unidirectional difference set of two sets
Find the unidirectional difference set of two sets, only keep the elements not in c in the current set, not in c and not in the current set
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
* Removes all elements contained in the specified collection from this collection.
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
// Set c cannot be empty
Objects.requireNonNull(c);
// Similarly, the batch delete method is called. In this case, false is passed in the complex to delete the elements contained in c
return batchRemove(c, false);
}
It is similar to the retain all (collection c) method, except that the elements not in c are retained here.
6. Expand knowledge
Analysis of toString() method used by ArrayList:
We all know that the ArrayList collection can directly use the toString() method. Let's dig into how the toString() method of ArrayList is implemented:
There is no direct toString() method in the source code of ArrayList. We need to find it in the parent class AbstractCollection of its parent class AbstractList:
public String toString() {
Iterator<E> it = iterator(); //Get iterator
if (! it.hasNext()) //If it is empty, return directly
return "[]";
//String splicing with StringBuilder
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) { //Infinite loop
E e = it.next(); //The iterator the next method removes the element and moves its cursor back
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString(); //There are no more elements. Then splice the right parenthesis
sb.append(',').append(' '); //There are elements
}
}
Summary: (1)ArrayList The array is used internally to store elements. When the length of the array is not enough, it will be expanded by half each time, ArrayList No volume reduction. (2)ArrayList It supports random access. It accesses elements through index very quickly, and the time complexity is O(1) (3)ArrayList Adding elements to the tail is extremely fast, with an average time complexity of O(1) (4)ArrayList Adding elements to the middle is slow because the average time complexity to move elements is O(n) (5)ArrayList Deleting elements from the tail is extremely fast, with a time complexity of O(1) (6)ArrayList Removing elements from the middle is slow because the average time complexity to move elements is O(n) (7)ArrayList Support union set, call addAll(Collection c)Method can (8)ArrayList Support intersection, call retainAll(Collection c)Method can (9)ArrayList Support one-way difference set, call removeAll(Collection c)Method can
Q & A: if elementData is set to transient, how does ArrayList serialize elements?
/**
* Save the state of the ArrayList instance to the stream (serialize it)
* @param s
* @throws java.io.IOException
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
//Prevent modification during serialization
int expectedModCount = modCount;
//Write out non transient and non static attributes (the size attribute will be written out)
s.defaultWriteObject();
//Write the number of elements
s.writeInt(size);
//Write out the elements in turn
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
//If there is any modification, an exception will be thrown to ensure that operations such as adding and deleting will not be performed during serialization
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Refactoring an ArrayList instance (that is, deserialization) from the stream
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
//Set to an empty array when reading in
elementData = EMPTY_ELEMENTDATA;
//Read in non transient and non static attributes (the size attribute will be read)
s.defaultReadObject();
// It is useless to read in the number of elements, just because the size attribute is written when writing out, and it should be read in order when reading in
s.readInt(); // ignored
if (size > 0) {
//Calculate minimum capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
//Check whether capacity expansion is required
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
//Read the elements into the array in turn
a[i] = s.readObject();
}
}
}
Looking at the writeObject() method, we can see that we first call the s.defaultWriteObject() method, then write the size to the stream, and then write the elements to the stream one by one.
Generally, as long as the Serializable interface is implemented, it can be serialized automatically. writeObject() and readObject() are used to control the serialization method. These two methods must be declared private, and then the writeObject() method is obtained through reflection in the java.io.ObjectStreamClass#getPrivateMethod() method.
In the writeObject() method of ArrayList, the s.defaultWriteObject() method is called first. This method writes non static and non transien attributes, that is, the size attribute in ArrayList. Similarly, in readObject(), the s.defaultyreaderobject() method is called to resolve the size attribute.
elementData is defined as the advantage of transient. It serializes real elements according to size instead of array length, which reduces the occupation of space.
7. ArrayList related interview questions
7.1 how to expand ArrayList?
For the first time, expand the capacity by 10, and then expand the capacity by 1% of the original capacity every time.5 Times, the capacity expansion moves one bit right through bit operation
7.2. Frequent capacity expansion of ArrayList leads to a sharp decline in the number of new users. How to deal with it?
@Test
public void test06(){
//The frequent capacity expansion of ArrayList leads to a sharp decline in add performance. How to deal with it?
//The cases are as follows:
ArrayList list=new ArrayList();
long startTime=System.currentTimeMillis();
//Add 100w pieces of data to the collection
for (int i = 0; i < 10000000; i++) {
list.add(i);
}
long endTime=System.currentTimeMillis();
System.out.println("Before optimization, add 100 w Data time:"+(endTime-startTime));
System.out.println("---------------Below is the solution-------------------");
ArrayList list1=new ArrayList(1000000);
startTime=System.currentTimeMillis();
//Add 100w data to collection
for (int i = 0; i < 10000000; i++) {
list1.add(i);
}
endTime=System.currentTimeMillis();
System.out.println("After optimization, add 100 w Data time:" + (endTime - startTime));
}
Output results:
Before optimization, add 100 w Data time: 2522 ---------------Below is the solution------------------- After optimization, add 100 w Data time: 863
It can be seen that if a large amount of data needs to be added to the collection, the initial capacity of the ArrayList collection should be defined in advance, so that it does not need to spend a lot of time on automatic capacity expansion.
7.3. Does ArrayList insert or delete elements slower than LinkedList?
In terms of their underlying data structures:
- ArrayList is a data structure based on dynamic array
- LinkedList is a linked list based data structure.
Efficiency comparison:
- Header insert: the LinkedList header inserts data quickly, because only the prev value and next value set of the node in front of the inserted element need to be modified. ArrayList is slow to insert data in the header, because the shift of array assignment takes a lot of time.
- Intermediate insertion: it is slow to insert data in the LinkedList because it takes a lot of time to traverse the linked list pointer (binary search); Inserting data in the middle of ArrayList is fast, because it is fast to locate the position of inserted elements, and there are not so many elements for shift operation.
- Tail insertion: it is slow to insert data at the tail of LinkedList because it takes a lot of time to traverse the linked list pointer (binary search); The tail of ArrayList inserts data quickly. In order to locate the position of the inserted element quickly, the amount of data for shift operation after operation is less.
Summary:
- The comparison results of inserting elements in the set are: the header is inserted faster than the LinkedList; Middle and tail insertion, ArrayList is faster.
- Similar to deleting elements in the collection, the header is deleted and the LinkedList is faster; Middle and tail deletion, ArrayList is faster.
Therefore, * * sets with a small amount of data are mainly used for insertion and deletion, and LinkedList is recommended; For collections with large amount of data, ArrayList can be used. It not only has fast query speed, but also has relatively high insertion and deletion efficiency.
7.4 is ArrayList thread safe?
The answer must be No. let's take an example:
First, create a new thread task class:
public class CollectionTask implements Runnable {
//Shared collection
private List<String> list;
public CollectionTask(List<String> list) {
this.list = list;
}
@Override
public void run() {
try {
Thread.sleep(50);
} catch (InterruptedException e) {
e.printStackTrace();
}
//Adds the current thread name to the collection
list.add(Thread.currentThread().getName());
}
}
Test code:
@Test
public void test03() throws InterruptedException {
//Create collection
List<String> list=new ArrayList<>();
//Create thread task
CollectionTask collectionTask=new CollectionTask(list);
//Open 50 tasks
for (int i = 0; i < 50; i++) {
new Thread(collectionTask).start();
}
//Ensure that the child thread is completed
Thread.sleep(3000);
/**
* If the ArrayList is thread safe, you can get 50 pieces of data by traversing the collection
* Print set length is 50
* Otherwise, it means that it is not thread safe
*/
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
System.out.println("--------------------------------");
System.out.println("Set length:"+list.size());
}
}
Output:
null null Thread-1 Thread-3 Thread-5 Thread-7 Thread-4 Thread-30 Thread-33 Thread-32 Thread-31 Thread-28 Thread-29 Thread-27 Thread-25 Thread-26 Thread-23 Thread-22 Thread-24 Thread-21 Thread-20 Thread-17 Thread-16 Thread-19 Thread-18 Thread-13 Thread-12 Thread-15 Thread-9 Thread-8 Thread-14 Thread-11 Thread-10 null Thread-48 Thread-45 Thread-44 Thread-41 Thread-40 Thread-37 Thread-36 Thread-47 Thread-46 Thread-43 Thread-42 Thread-39 Thread-38 Thread-35 Thread-34 -------------------------------- Set length: 49
Therefore, it is concluded that ArrayList is not a thread safe collection! If you need to ensure thread safety, it is recommended to use the Vector collection, which is thread safe, but it is less efficient than ArrayLisyt.
The reason why Vector is thread safe relative to ArrayList is that its add() method adds elements to the collection:
// You can see that the Vector add method adds the synchronized synchronization keyword
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
In addition to the Vector set, you can also use the following methods:
List<String> list = new ArrayList<>(); List<String> synchronizedList = Collections.synchronizedList(list);
The synchronized obtained in this way is also thread safe!
**Note: * * under what circumstances do you not need to add synchronization lock to ArrayList?
- First: in the case of single thread, there is no need to lock. It is considered for efficiency!
- Second, when ArrayList is used as a local variable, it does not need to be locked, because the local variable belongs to a thread. In the above example, ArrayList is used as a member variable. The collection of member variables needs to be shared by all threads, which needs to be locked!
7.5 how to assign an ArrayList to another ArrayList? How many can you list?
- The clone() method is used because the ArrayList method implements the Cloneable interface and can be cloned
- Use the ArrayList construction method, ArrayList (collection <? Extensions E > C)
- Use addall (collection <? Extensions E > C)
- Write a loop to add one by one
7.6 how can ArrayList be modified concurrently without concurrent modification exceptions?
Question: the member variable set is known to store N multi-user names. In a multi-threaded environment, how to ensure that data can be written to the set normally while using the iterator to read the set data?
Create a new thread task class:
/**
* @Description: The thread task class uses ArrayList to modify collection data in a multithreaded environment,
* And there is no concurrent modification exception
*/
public class CollectionThread implements Runnable{
private static ArrayList<String> list = new ArrayList<>();
static {
list.add("Jack");
list.add("Amy");
list.add("Lucy");
}
@Override
public void run() {
for (String value : list){
System.out.println(value);
// While reading data, it also writes data to the collection
list.add("Coco");// Concurrent modification exceptions will occur
}
}
}
The test reads and writes shared collection data to it simultaneously in a multithreaded environment:
/**
* @Description: Interview questions:
* The known member variable set stores N multi-user names. In a multi-threaded environment, the iterator is used to read the set data at the same time,
* How to ensure that data can be normally written to the collection?
*/
public class Test03 {
public static void main(String[] args) {
// Create thread task
CollectionThread collectionThread = new CollectionThread();
// Open 10 threads
for (int i = 0; i < 10; i++) {
new Thread(collectionThread).start();
}
}
}
Test results:
Jack Jack Jack Jack Jack Jack Jack Jack Jack Jack Exception in thread "Thread-0" Exception in thread "Thread-1" Exception in thread "Thread-4" Exception in thread "Thread-5" Exception in thread "Thread-8" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) Exception in thread "Thread-9" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) Exception in thread "Thread-2" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) Exception in thread "Thread-7" Exception in thread "Thread-6" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) Exception in thread "Thread-3" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748) java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at com.haust.list.CollectionThread.run(CollectionThread.java:21) at java.lang.Thread.run(Thread.java:748)
Concurrent modification exception occurs. To solve this problem, java introduces a thread safe collection (read-write separation collection) that can ensure that both reads and writes are thread safe: CopyonWriteArrayList
So the solution is:
// private static ArrayList<String> list = new ArrayList<>();
// Replace the original ArrayList with a read-write separated collection
private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
static {
list.add("Jack");
list.add("Amy");
list.add("Lucy");
}
@Override
public void run() {
for (String value : list){
System.out.println(value);
// While reading data, it also writes data to the collection
list.add("Coco");// Concurrent modification exceptions will occur
}
}
currentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at com.haust.list.CollectionThread.run(CollectionThread.java:21)
at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at com.haust.list.CollectionThread.run(CollectionThread.java:21)
at java.lang.Thread.run(Thread.java:748)
Concurrent modification exception occurs. To solve this problem, java introduces a thread safe collection (read-write separation collection) that can ensure that both reads and writes are thread safe: CopyonWriteArrayList
So the solution is:
// private static ArrayList<String> list = new ArrayList<>();
// Replace the original ArrayList with a read-write separated collection
private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
static {
list.add("Jack");
list.add("Amy");
list.add("Lucy");
}
@Override
public void run() {
for (String value : list){
System.out.println(value);
// While reading data, it also writes data to the collection
list.add("Coco");// Concurrent modification exceptions will occur
}
}