Why I want to write this article, I am not really curious, or because the team technology share, I also want to make a share of the content, I look forward to (despair) and happy (sad).
The underlying data structure of ArrayList
The underlying data structure of an ArrayList is an array, which is an array of Object elements. All operations are based on the underlying array. (I even wondered at one point if I needed to explain what an array was, but spring trouble made me give up.)
2. Expansion mechanism of ArrayList
This is one of the more interesting things, and my entire technology sharing is based on this to keep my job.
2.1 Analysis of three constructors
To explain the scaling mechanism, we start with the three constructors of ArrayList:
transient Object[] elementData;
Copy the codeNote: elementData is the underlying data structure of ArrayList. It is an object array that stores the actual elements. It is marked as transient and will not be serialized when serialized.
2.1.1 Empty parameter constructor
Set an empty object array to elementData
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code2.1.2 Constructor for an array size parameter
If size >0, create an array of objects of the specified size. =0, specify an empty object array <0, throw exception
private static final Object[] EMPTY_ELEMENTDATA = {};
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); }}Copy the code2.1.3 Constructors for set parameters
A. Convert set to array B. Determine the length of array, length! = 0; Is the array type an Object array? -> No, copy elementData’s data, copy it as an Object array, assign it to elementData False: Set elementData to an empty Object array
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA; }}Copy the code2.1.4 What are deep and shallow copies of arrays?
Deep copy: not only reference copy, but also create a new memory space
Shallow copy: reference copy
Q: Arrays. CopyOf deep copy or shallow copy? A: Shallow copy, which only copies references to objects, i.e. memory addresses, without creating new objects for each element. To explain why, check out this blog post. Blog.csdn.net/abysscarry/…
2.2. Time when expansion mechanism occurs
When you add()
1. The add (E, E); Add a specific element code operation definition: check whether the expansion operation is required; Add the actual number of elements in the set +1;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Copy the code2. Add (int index, E element); Add an element according to the subscript
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
// The original array; The starting position of the source array to copy; Target array; The starting position of the target array copy; The length of the array to copy
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
Copy the codeIs system.arrayCopy () a deep copy or a shallow copy?
A: Deep copying is only done if the array is a one-dimensional array and the elements are of type primitive or String. System.arraycopy() is often used to expand arrays, such as the underlying array of ArrayList
2.3 Differences between ArrayList and LinkedList when inserting data
2.3.1 How to Insert Data into an ArrayList?
Add (index, e) arrayList.add (index, e) efficiency
To insert data at the specified index, copy all data from the target index position to size-index, just to make room for an add.
If the array is 100, then add(0, Element) means that in order to make way for it, we need to copy and move the data between 1 and 99.
2.3.2 How does LinkedList insert data?
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Copy the codeLinkBefore (Element, node (index)); Target element; 2. The current node object of the target element.
LinkedList insert data process:
- Get the current target node pre=pred;
- New a new nodule newNode, the three parameters represent :a. Pre =pred of the current node; B. Element e=e; C. Next node next=succ;
- Set the new node of new to the pre of the current operating node. (Set the pre of the operation node to the newly inserted element node)
- Determine if the currently inserted element is the head node of the LinkedList. If not, next of the current operation element node is the node to be inserted into as new. (Point next of the operation node to the node of the newly inserted element)
The approximate flow of inserting an element at a location is shown below:
Comparison of insertion efficiency between ArrayList and LinkedList
ArrayList add is tail: efficiency ArrayList>LinkedList; Add to ArrayList is the header: efficiency ArrayList
Reason: ArrayList has contiguous memory space and does not need to copy the array. The LinkedList needs to create a new node, with references rearranged.
I don’t know if it hit you guys, but it hit me.
What does expansion have to do with the constructor?
2.4 Triggering capacity Expansion and Capacity Expansion
Add (e) {add(e) {add(e) {
add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Copy the codeEnsureCapacityInternal (int minCapacity) : Ensures the smallest value of the inserted element container; MinCapacity: the current array length +1
If the constructor is an empty parameter constructor, set the default value for minCapacity to minCapacity=DEFAULT_CAPACITY=10. If there is no null parameter constructor, minCapacity= size+1 of the array’s existing data
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
Copy the codeEnsureExplicitCapacity (int minCapacity) : Determines whether to expand elementData. Length is the length of existing data.
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the codeGrow (int minCapacity) : The capacity is expanded
- Get old capacity
- Now increase the length of the original element array by 1.5 times and compare it with newCapacity.
- If the newCapacity is smaller than the specified capacity, modify the newCapacity: newCapacity (newCapacity)
- NewCapacity >minnewCapacity: newCapacity: the array will be copied to the new array after expansion.
private void grow(int minCapacity) {
int oldCapacity = elementData.length; / / the old capacity
int newCapacity = oldCapacity + (oldCapacity >> 1); // The new capacity is 1.5 times the old capacity
if (newCapacity - minCapacity < 0) If the new capacity is smaller than the specified capacity, modify the new capacity
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // The new capacity exceeds the maximum capacity
newCapacity = hugeCapacity(minCapacity); // Specify a new capacity
// Copy capacity expansion
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeIf the ArrayList gives a specific initial value, the difference between the actual array length and the array capacity is used to determine whether to invoke capacity expansion. If no initial capacity is specified, the first call to add must require a call to grow()
The thread safety of ArrayList
In multithreading, an ArrayList is not guaranteed to be atomic (that is, only one thread can operate on it at a time).
For example: thread A ++ an ArrayList, expecting 100; Thread B performs — processing on the ArrayList, expecting 98. When you’re doing multiple threads, maybe it should be 100, because you have — again, maybe you ++, and it’s still 99.
ArrayList threads are not safe in multithreaded environments.
Methods to ensure thread-safety:
1. Use the synchronized keyword.
2. Call Arraylist with synchronizedList(), the static method in the Collection class
Introduction to the common methods of ArrayList
Arraylist. get(position) : Values by array subscript, same as set
Arraylist. add(postion) : Determines whether to expand capacity and assigns values according to array subscripts
Arraylist.remove (index) step: 1. Set the starting position of assignment at the location of the target element. 2. Copy the array from the target position to the last bit of the array. 3. Copy the overwrite to the position to be removed, and then overwrite the position to be removed. 4. Null the data in the last position and wait for recycling.
Remove (index) of the source code:
public E remove(int index) {
/ / the first step to determine whether there is crossing the line, if cross-border IndexOutOfBoundsException directly
rangeCheck(index);
modCount++;
// Remove the element from the array
E oldValue = elementData(index);
// The length to copy
int numMoved = size - index - 1;
if (numMoved > 0)
// The original array, where to start the copy, the target array, where to start the copy, the length. The process is shown as follows:
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// Assign null to wait for collection
elementData[--size] = null;
return oldValue;
}
Copy the code5.ArrayList deprocessing
1. Loop through all the elements in the list and delete them
public static ArrayList removeDuplicate_1(ArrayList list){
for(int i =0; i<list.size()-1; i++){for(int j=list.size()-1; j>i; j--){if(list.get(i).equals(list.get(j))) list.remove(j); }}return list;
}
Copy the code2. Use hashSet to remove duplicate elements
public static ArrayList removeDuplicate_2(ArrayList list){
HashSet set = new HashSet(list);
// Use LinkedHashSet to ensure the order of input
//LinkedHashSet<String> set2 = new LinkedHashSet<String>(list);
list.clear();
list.addAll(set);
return list;
}
Copy the code3. Use the contains method of list to remove weights
public static ArrayList removeDuplicate_3(ArrayList list){
ArrayList tempList = new ArrayList(list.size());
for(int i=0; i<list.size(); i++){if(! tempList.contains(list.get(i))) tempList.add(list.get(i)); }return tempList;
}
Copy the codeWhat is the principle by which Contains compares? So you can see that contains actually compares equals, and equals is the address of the comparison
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the codeWhen to select ArrayList?
6.1 Difference in traversal efficiency between For and Iterator of ArrayList
ArrayList implements the RandomAccess interface, which is a flag interface and can be accessed randomly, making ArrayList’s for loop traverse more efficient than Iterator’s. LinkedList is a more efficient Iterator.
For () versus Iterator?
For loop traversal, counter based: sequential storage: high read performance. Suitable for traversing sequential storage collections. Chained storage: The time complexity is too great to traverse a collection of chained storage.
Iterator Iterator: Sequential storage: If you are not too concerned with time, this method is recommended. After all, the code is simpler and avoids off-by-one problems. Chain storage: The average time complexity is reduced to O(n). This traversal mode is recommended.
6.1.2 Differences between remove() for and Iterator()
ArrayList traversal:
Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator Iterator
2. The for loop cannot call the remove() method of the list while the for loop is running.
6.3 Compare the advantages and disadvantages of each implementation class in the set
For the operation of data, generally add, delete, change, search, sort, data repetition, whether can be empty, thread safety. The advantages and disadvantages of the corresponding collections will be compared and sorted according to the above operations. As follows:
List: Ordered, repeatable elements
Implementation classes: thread-safe: Vector, thread-unsafe: ArrayList, LinkedList Insert and delete efficiency: LinkedList query speed: ArrayList
Set: Element cannot be repeated
Query speed: LinkedHashSet=HashSet query, search speed: HashSet>TreeSet query, delete, add elements are very efficient
Map
Thread safety: HashTable, key, and value cannot be null Thread safety: HashMap, key, and value can be accessed by empty iteration fast: LinkedHashMap, iterated over, retrieved key-value pairs in the order they were inserted; Traversal speed <HashMap