An overview of JAVA collection classes

Read with questions

1. What collections do Java have

2. What are the application scenarios of different sets

Which implementation classes are thread-safe

4. Why can’t Java collections store primitive types

5. What are fail-fast and Fail-safe for collections

An overview of Java collections

Java provides developers with a set of interfaces and implementations for Collections, which are Collections of Java objects, through the Java Collections Framework(JCF).

Students who have studied data structure are certainly familiar with the definition of all kinds of collections. Java improves the convenience of development for developers, improves the compatibility of programs and reduces the complexity of programming by providing a series of built-in data structures.

Images from www.pdai.tech/md/java/col…

A Java Collection consists of two top-level interfaces: Collection, which is a Collection that primarily holds objects, and Map, which is a Collection that holds key-value pairs.

Let’s make a brief introduction to the implementation of the two types of collections.

Collection

Collection is an interface introduced in Jdk1.2 to describe a Collection of stored objects. Its extended interfaces include List, Queue, and Set.

List

List accesses elements sequentially in the form of a List, ensuring that elements are inserted in the same order as they are stored.

Vector is a thread-safe list implementation introduced in Jdk1.0, which predated the design of Collection interface. Synchronized is directly added to the method to ensure thread-safe. Stack is the Stack structure inherited from Vector implementation. It is not recommended in actual environments.

Queue

A Queue is a first-in, first-out structure, with elements added from the end of the Queue and ejected from the head. The subinterface Deque is a double-endian queue, that is, both ends can enter and exit.

Because BlockingQueue is a bit more complex and involves some more advanced scenarios, I’ll leave it to you later.

Set

A Set is a collection of non-repeating elements that do not contain the same elements and generally do not maintain the order in which they are inserted

Map

Map is used to store <Key, Value> key-value pairs.

Why can’t Java collections hold primitive types

Java introduced the JCF framework in version 1.2 and Java generics in version 1.5, so collections used Object as their storage type by default before generics were introduced.

Take List for example. List List =new ArrayList();
list.add(123); / / automatic boxing
list.add("123");
int num = (int) list.get(0);
String str = (String) list.get(1);
Copy the code

It is obvious that there are defects in this method. Any element based on Object can be put into the collection, but the acquirer of the element cannot determine the specific type of the element, which is prone to type conversion errors. After the introduction of generics in version 1.5, the collection interface was standardized and generic parameters were added. Java’s generics mechanism still essentially erases concrete types as Object, so when a generic collection is initialized, it cannot specify parameters as primitive types that are not derived from Object.

What are fail-fast and Fail-safe

List<String> list = new ArrayList();
list.add("123");
list.add("456");

//(1) throw ConcurrentModificationException
for (String s : list) {
	list.remove(s);
}

//(2) Normal removal
Iterator<String> it = list.iterator();
while (it.hasNext()) {
	it.next();
	it.remove();
}

//(3) throw ConcurrentModificationException
new Thread(() -> {
	for (String s : list) {
		System.out.println(s);
		try {
			TimeUnit.SECONDS.sleep(1);
		} catch (InterruptedException ignore)
		{
		
		}
	}
}).start();
new Thread(() -> {list.add("789"); }).start();Copy the code

The code above, (1) (3) will throw ConcurrentModificationException, (2) can remove all elements properly. First learn about ConcurrentModificationException, when to modify an object to make concurrent not allowed, will throw this exception.

This exception may be thrown by methods that have detected concurrent modification of an object when such modification is not permissible.

So (1) it’s a single thread, and (3) the element is added concurrently without modifying the existing element.

ArrayList var1 = new ArrayList();
var1.add("123");
var1.add("456");
Iterator var2 = var1.iterator();
while(var2.hasNext()) {
     String var3 = (String)var2.next();
     var1.remove(var3);
}
Copy the code

A decompilation of the class file of code (1) shows that foreach is actually iterating through the Iterator, and removing the Iterator is done directly by calling list.remove. Let’s dive into the list.iterator method again.

/** Returns an iterator over the elements in this list in proper sequence. * The returned iterator is fail-fast. */
public Iterator<E> iterator(a) {
    return new Itr();
}

private class Itr implements Iterator<E> {...intexpectedModCount = modCount; .final void checkForComodification(a) {
        if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

Iterator method will create a Itr object, when its a copy modCount to expectedModCount, each iteration will determine when the two values are the same, if different throw ConcurrentModificationException.

ModCount is a member variable derived from AbstractList that counts the number of times the list has been modified. ModCount is incremented every time add/remove is called.

// The number of times this list has been structurally modified.
protected transient int modCount = 0;
Copy the code

The problem is obvious. ModCount changes every time a list is modified. The iterator in foreach records the modCount value at the time the iterator is created. Cause modCount! ExpectedModCount = expectedModCount, so an exception is thrown. (3) The code is the same problem and will not be repeated.

* <p><a name="fail-fast">
* The iterators returned by this class's {@link #iterator() iterator} and
* {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
* if the list is structurally modified at any time after the iterator is
* created, in any way except through the iterator's own * {@link ListIterator#remove() remove} or * {@link ListIterator#add(Object) add} methods, the iterator will throw a * {@link ConcurrentModificationException}. Thus, in the face of * concurrent modification, the iterator fails quickly and cleanly, rather * than risking arbitrary, non-deterministic behavior at an undetermined * time in the future.Copy the code

In all Java collection classes, all collections directly under java.util except Vector, Stack, and HashTable are fail-fast, while collections under java.util. Concurrent are fail-safe. That is, a collection of concurrent traversal and modification, the implementation of which is guaranteed by the respective thread safety mechanism.

Why fail-fast

Fail-fast means to fail quickly. In a non-thread-safe collection application, concurrent additions or deletions to a collection can cause another thread traversing the collection to have unknown errors, such as a number of groups out of bounds. Therefore, non-thread-safe collection implementations introduce Fail-fast as a way to quickly interrupt threads without causing unknown interlocking problems.

reference

• Java collection framework in detail
• Fail-fast vs. Fail-safe