1, Collection,
- List, an ordered collection that provides easy access, insertion, deletion, and so on.
- Set does not allow duplicate elements. This is the most obvious difference from List: there are no two objects equals returns true.
- Queue/Deque is the implementation of the standard Queue structure provided by Java. In addition to the basic functions of collections, it also supports specific behaviors such as [FIFO, first-in-first-out] or [LIFO, last-in-first-out].
1-1, the ArrayList
List of array structures, non-thread-safe;
1-2, LinkedList
A list of linked lists, not thread-safe;
1-3, the Vector
List of array structures, thread-safe;
1-4. Differences between ArrayList and LinkedList
Vector is a thread-safe (synchronized modified) dynamic list. A Vector uses an array of objects to hold data inside it. It automatically increases the size of the Vector as needed. When the array becomes full, a new array is created and the data in the original array is copied. It will be doubled by capacity expansion.
private void grow(int minCapacity) { int oldCapacity = elementData.length; Int newCapacity = oldCapacity + ((capacityIncrement > 0)? Int newCapacity = oldCapacity + ((capacityIncrement > 0)? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }Copy the codeArrayList, a more widely used implementation of dynamic arrays, is not inherently thread-safe, so it performs much better. Like Vector, ArrayList can be adjusted to increase capacity by 50%.
private void grow(int minCapacity) { int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); // newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }Copy the codeLinkedList is a bidirectional list provided by Java, so it does not need to be scaled as the above two do, and it is not thread-safe.
Applicable scenarios:
- Vector and ArrayList are dynamic arrays whose internal elements are stored sequentially, so they are well suited for random access. With the exception of tail insert and delete elements, performance tends to be relatively poor, such as when we insert an element in the middle and move all subsequent elements.
- LinkedList is much more efficient for node insertion and deletion, but random access performance is slower than dynamic array.
class
The data structure
capacity
Thread safety
Insert/delete time complexity
Access time complexity
Vector
An array of
1 times
unsafe
O(n)
O(1)
Array random access
ArrayList
An array of
0.5 times
unsafe
O(n)
O(1)
Array random access
LinkedList
Two-way linked list
Don’t need to increase
unsafe
O(1)
O(n)
1-5, the Set
- TreeSet supports natural sequential access, but add, delete, and include operations are relatively inefficient (log(n) time).
- A HashSet, on the other hand, utilizes a hash algorithm. Ideally, if a hash hash is working, it can provide constant time additions, deletions, and inclusions, but it does not guarantee order.
- LinkedHashSet, which internally builds a bidirectional list to record the insertion order, thus providing the ability to traverse the insertion order. At the same time, it also guarantees constant time add, delete, include, etc. These operations are slightly lower than HashSet due to the overhead of maintaining the linked list.
The performance of a HashSet is affected by its capacity as it traverses elements, so do not set the size of the HashMap behind it to too large during initialization unless necessary. For LinkedHashSet, traversal performance is dependent only on the number of elements, due to the convenience provided by its internal linked list.
1-6. How does ArrayList implement thread safety?
The synchronizedList(List List) method inside the Java.util. Collections utility class implements ArrayList thread-safe, making every basic method, such as get, set, add, etc., Both add basic synchronization support with synchronized, which is very simple and crude, but also very practical.
Pay attention to these methods to create thread-safe collections, meet the iteration 】 【 fail – fast behavior, when the accident of concurrent modification, throw ConcurrentModificationException exception 】 as soon as possible, to avoid the unexpected behavior.
public static <T> Collection<T> synchronizedCollection(Collection<T> c) { return new SynchronizedCollection<>(c); } public static <T> List<T> synchronizedList(List<T> list) { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : new SynchronizedList<>(list)); } static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> { final List<E> list; SynchronizedList(List<E> list) { super(list); this.list = list; } public boolean equals(Object o) { if (this == o) return true; synchronized (mutex) {return list.equals(o); } } public E get(int index) { synchronized (mutex) { return list.get(index); } } public E set(int index, E element) { synchronized (mutex) {return list.set(index, element); } } public void add(int index, E element) { synchronized (mutex) {list.add(index, element); } } public E remove(int index) { synchronized (mutex) {return list.remove(index); }}Copy the code1-7, ConcurrentModificationException
* * some object, according to a document describes ConcurrentModificationException, don’t allow concurrent modification 】 【 * * as these changes behavior is detected, the exception will be thrown. (For example, some collections do not allow one thread to iterate while another thread changes the collection).
In an Iterator implementation of collections (e.g., Collection, Vector, ArrayList, LinkedList, HashSet, Hashtable, TreeMap, AbstractList), If this is provided, these iterators can be called “fail-fast iterators “, which means that when a concurrent change is detected, an exception is thrown, rather than continuing to throw an exception until some error value is obtained.
Exception detection is mainly implemented by two variables, [modCount] and [expectedModCount]
The number of times the modCount collection is modified, usually by the collection (such as ArrayList). Each call to add(), remove() causes modCount+1;
ExpectedModCount Specifies the expected number of changes that are held by Iterator(the object returned by arrayList.iterator ()) and are assigned to the initial value when the Iterator is initialized. ExpectedModCount is updated when Iterator’s remove() method is called.
Then, when the Iterator calls next() to iterate over the elements,
The checkForComodification() method is called
Compare modCount with expectedModCount,
Just throw ConcurrentModificationException.
Single thread operation Iterator is not at that time also can throw ConcurrentModificationException. (The above example is);
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {} public boolean hasNext() { return cursor ! = size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } final void checkForComodification() { if (modCount ! = expectedModCount) throw new ConcurrentModificationException(); }Copy the codeconclusion
Because the iterators of ArrayList and HashMap are “fail fast iterators”, the iterators compare expectedModCount and modCount when they get the next element and delete the element, Inconsistency throws an exception.
Iterator’s remove() method must be used to remove elements from Iterator. Instead of calling the Remove () method of ArrayList or HashMap itself, which would cause the expectedModCount in Iterator to not update in time and then fetch the next element or delete the element later, ExpectedModCount and modCount inconsistent, and then throw ConcurrentModificationException.
In the 1-7-1 s, iterators, and ConcurrentModificationException
Objective: In [concurrent environment], container modification is a quick failure, to ensure container security and data consistency;
Implementation method: counter, record the change of the container number, if the counter is modified iteration 】 【, will throw ConcurrentModificationException hasNext or next.
When designing iterators for synchronous container classes, the problem of concurrent modification is not considered and the behavior is fail-fast. The container in the iteration process is modified, it will throw ConcurrentModificationException.
1-8. Fast-fail and fast-safe design in the collection framework
Java 1.0-Java 1.4 Collection framework design is fast-fail
Java.util. concurrent and the concurrency security framework fast-safe were added as of Java1.5