Introduction: does map not belong to a subset of the Java collection framework? Like a list, a queue belongs to one of the three subsets of a set? More correct use of posture, let's see!

Collection in Java usually refers to the collection of the three collection frameworks list, set, queue and map under collection. Map does not belong to a subset of collection, but a top-level interface parallel to it. The relationship of subsets under collection is shown in the picture at the beginning of the article.

The focus of this paper will focus on the use of collections, performance, thread safety, differences, source code interpretation and so on.

The knowledge points involved in this paper are divided into two parts:

The first part, all subsets of the collection:

In the second part, map = > hashtable, HashMap, treemap, concurrenthashmap.

1、 List

Let's first look at the inheritance relationship among list, vector, ArrayList and LinkedList, as shown in the following figure:

It can be seen that vector, ArrayList and LinkedList all implement the list in the collection framework, that is, the so-called ordered collection. Therefore, the specific functions are similar. For example, they all provide positioning, addition or deletion according to location, and iterators to traverse its contents. However, due to the specific design differences, the performance is very different in behavior, performance, thread safety and so on.

See their main methods as follows:

Common methods:

1.1 Vector

Vector is a thread safe dynamic array provided by Java in the early days. If thread safety is not required, it is not recommended. After all, synchronization has additional overhead. Vector uses an object array to save data. It can automatically increase the capacity as needed. When the array is full, it will create a new array and copy the original array data.

From the source code, we can see that vector implements thread safety through synchronized:

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

Vector dynamically increases capacity. View the source code:

private void grow(int minCapacity) {
    // overflow-conscIoUs code
    int oldCapacity = elementData.length;
    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);
}

What is the capacityincrement variable? The answer is as follows:

public Vector(int initialCapacity,int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

Summary of vector dynamic capacity increase: from the above source code, if the dynamic capacity expansion size is specified when initializing vector, the specified dynamic size will be increased. If it is not specified, the capacity will be doubled.

1.2 ArrayList

ArrayList is a more widely used dynamic array. It is not thread safe, so its performance is much better.

ArrayList is similar to vector, but has different dynamic capacity expansion mechanisms. The source code is as follows:

private void grow(int minCapacity) {
    // overflow-conscIoUs code
    int oldCapacity = elementData.length;
    int 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);
}

Where "> > 1" is a bit operation, which is equivalent to dividing by 2. All ArrayList expansion is dynamic expansion of 50%

1.3 LinkedList

LinkedList, as its name implies, is a two-way linked list provided by Java, so it does not need to adjust the capacity like the above two. It is not thread safe. It contains a very important internal class: entry. Entry is the data structure corresponding to the two-way linked list node. It includes the following attributes: the value contained in the current node, the previous node and the next node.

1.4 differences among vector, ArrayList and LinkedList

The differences among vector, ArrayList and LinkedList can be compared from the following dimensions:

1.4. 1. Differences between underlying implementations

Vector and ArrayList are internally implemented by array, and LinkedList is internally implemented by two-way linked list.

1.4. 2. Differences in reading and writing performance

The addition and deletion of non last bits of ArrayList elements will cause dynamic changes in memory allocation space. Therefore, the operation speed of non last bits is slow, but the retrieval speed is fast.

LinkedList stores data based on linked list. It is faster to add and delete elements, but slower to retrieve.

1.4. 3 differences in thread safety

Vector uses synchronized to modify that the operation method is thread safe, while ArrayList and LinkedList are non thread safe.

If you need to use a thread safe list, you can use the copyonwritearraylist class.

2、 Map

Hashtable, HashMap and treemap are the most common map implementations. They are container types that store and manipulate data in the form of key value pairs.

The relationship between them is as follows:

The performance of HashMap depends very much on the validity of hash code. Please be sure to master some basic conventions between hashcode and equals, such as:

Thread safety: hashtable is thread safe, while HashMap and treemap are non thread safe. HashMap can use concurrent HashMap to ensure thread safety.

3、 Set

Set has two commonly used subsets: HashSet and TreeSet

HashSet is implemented internally by HashMap. You can see from the source code:

public HashSet() {
    map = new HashMap<>();
}

HashSet is not thread safe. HashSet is used to store unordered (the order of storage and retrieval is not necessarily the same) elements, and the values cannot be repeated.

HashSet can remove duplicate values, as shown in the following code:

public static void main(String[] args) {
        Set set = new HashSet();
        set.add("orange");
        set.add("apple");
        set.add("banana");
        set.add("grape");
        set.add("banana");
        System.out.println(set);
}

The compiler will not report an error. The execution result is: [orange, banana, apple, grape], and the repeated "banana" option is removed. But sorting is out of order. If you want to achieve orderly storage, you need to use TreeSet.

public static void main(String[] args) {
    Set set = new TreeSet();
    set.add("orange");
    set.add("apple");
    set.add("banana");
    set.add("grape");
    set.add("banana");
    System.out.println(set);
}

The output result is: [apple, grape, orange]

Similarly, we check the source code and find that the underlying implementation of TreeSet is treemap. The source code is as follows:

public TreeSet() {
    this(new TreeMap<E,Object>());
}

TreeSet is also non thread safe.

4、 Queue

Queue (queue) a data structure opposite to stack. A linear table that only allows insertion at one end and deletion at the other end. Stack is characterized by last in first out, while queue is characterized by first in first out. Queue is very useful, but it is mostly used in other data structures, such as traversal by layer of tree, breadth first search of graph, etc Columns are used as auxiliary data structures.

Direct subset of queue, as shown in the following figure:

One of the most commonly used is the thread safety class: BlockingQueue

4.1 queue method

be careful:

4.2 queue usage

Queue<String> queue =  new LinkedList<String>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
System.out.println(queue);
queue.poll();
System.out.println(queue);
queue.poll();
queue.poll();
queue.poll();
System.out.println(queue.peek());
// System.out.println(queue.element()); // element 查询失败会抛出异常
System.out.println(queue);

4.3 other queues

The bottom layer of arrayblockingqueue is array and bounded queue. If we want to use producer consumer mode, this is a very good choice.

The underlying layer of linkedblockingqueue is a linked list, which can be used as unbounded and bounded queues, so don't think it is an unbounded queue.

Synchronousqueue itself does not have space to store any elements. You can choose fair mode and unfair mode.

Priorityblockingqueue is an unbounded queue. It is based on an array. The data structure is a binary heap. The first node of the array is also the root node of the tree. It is always the minimum value.

Arrayblockingqueue: a bounded blocking queue composed of an array structure.

Linked blocking queue: a bounded blocking queue composed of a linked list structure.

Priorityblockingqueue: an unbounded blocking queue that supports prioritization.

Delayqueue: an unbounded blocking queue implemented using priority queue.

Synchronous queue: a blocking queue that does not store elements.

Linkedtransferqueue: an unbounded blocking queue composed of a linked list structure.

Linked blocking deque: a bidirectional blocking queue composed of linked list structure

5、 Extension: thread safety of string

Thread safety of string, StringBuffer and StringBuilder

String is a typical immutable (immutable) class. It is declared as final. All attributes are also final. It is immutable. All actions such as splicing and interception will produce new string objects.

StringBuffer was born to solve the above problems. It provides the append method to realize the splicing of strings, and the append method uses synchronized to realize thread safety.

StringBuilder is a new feature of JDK 1.5. As a performance supplement to StringBuffer, the append method of StringBuffer uses synchronized to achieve thread safety, but it also brings performance overhead. StringBuilder can be used preferentially without thread safety.

6、 Summary

List is the most ordered set that we introduced earlier. It provides convenient access, insertion, deletion and other operations.

Set does not allow duplicate elements, which is the most obvious difference from list, that is, there are no two objects, and equals returns true. In our daily development, there are many occasions where we need to ensure the uniqueness of elements.

Queue / deque is the implementation of the standard queue structure provided by Java. In addition to the basic functions of the collection, it also supports specific behaviors such as first in first out (FIFO) or last in first out (LIFO). BlockingQueue is not included here. Because it is usually used in concurrent programming, it is placed in the concurrent package.

Map is another part of the generalized Java collection framework. The map interface stores a set of key value objects and provides key to value mapping.

7、 References

Code out efficiency: Java Development Manual

Lecture 36 on Java core technology: http://t.cn/EwUJvWA

Oracle docs： https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html