Detailed introduction to a comprehensive summary of Java container related knowledge (picture)

Java PracticalClass Library provides a fairly complete set of containers to help us solve many specific problems. Because I am an Android developer myself, and many Android developers, including myself, are best at the Three Musketeers of ListView (RecycleView) + BaseAdapter + ArrayList. The only containers I usually use are ArrayList and HashMap. As a result, the understanding and use of the entire Java container system is still at a very shallow level. If you don't want to save yourself and think about improvements, then follow me to summarize the relevant knowledge of Java containers.

Structure

• Java container classInheritanceStructure

• Detailed introduction

• List

• Set

• Queue

• ##Iteration Device

• Collection

• Map

• Some suggestions

• Advanced·Concurrent Container

##CopyOnWriteArrayList and Copy-On-Write Strategy
ConcurrentLinkedQueue
ConcurrentHashMap and lock segmentation technology
Blocking queue

Inheritance structure of java container class

The Java container class library defines two containers with different concepts, Collection and Map

##Collection
• A sequence of independent elements, these elements are Obey one or more rules. List must hold elements in the order of insertion. Set cannot have duplicate elements. Queue determines the order in which

  objects are generated according to queuing rules.

  (The Jdk source code version in the article is jdk1.8.0_101 without special instructions)

    public interface Collection<E> extends Iterable<E> {
        int size();

        boolean isEmpty();

        boolean contains(Object o);

        Iterator<E> iterator();

        Object[] toArray();

        <T> T[] toArray(T[] a);

        boolean add(E e);

        boolean remove(Object o);

        boolean containsAll(java.util.Collection<?> c);

        boolean addAll(java.util.Collection<? extends E> c);

        boolean removeAll(java.util.Collection<?> c);

        ... //省略了其他方法
    }

As you can see, java defines the Collection interface and the basic operation methods of internal collections , Collection can perform operations such as adding elements to the end of the collection and deleting specified elements by default. List, Set, and Queue interfaces all inherit from Collection and define different methods.

Map
• A set of "key-value" objects that allow us to use the key to find the value.

      public interface Map<K,V> {
          int size();
  
          boolean containsKey(Object key);
  
          boolean containsValue(Object value);
  
          V get(Object key);
  
          V put(K key, V value);
  
          V remove(Object key);
  
          void putAll(java.util.Map<? extends K, ? extends V> m);
  
          void clear();
  
          Set<K> keySet();
  
          Collection<V> values();
  
          Set<java.util.Map.Entry<K, V>> entrySet();
  
          interface Entry<K,V> {
              K getKey();
  
              V getValue();
  
              V setValue(V value);
  
              boolean equals(Object o);
  
              int hashCode();
  
              ...
          }
  
          boolean equals(Object o);
  
          int hashCode();
  
      }

  Map internal interface Entry corresponds to the key-value pair of Map.

Detailed introduction

Iterator

First introduce the iterator. The iterator itself is also a

design pattern

. The original intention of the design is: there are many kinds of container implementations, and if we want to traverse the container, we should not care about the container implementation first. Details, secondly the traversal operation should be lightweight. Iterators unify access to containers and are cheap to create. It is worth noting that iterators can only move in one direction.

    public interface Iterator<E> {
        boolean hasNext();

        E next();

        default void remove() {
            throw new UnsupportedOperationException("remove");
        }

        default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
            }
    }

Get the iterator of the container through the iterator() method of the container

Next() of the iterator gets the next element

hasNext() determines whether there are still elements

remove() deletes the specified element


ListIterator

ListIterator is an extension of Iterator and is used for various List class accesses and supports two-way movement.

Collection

List

List promises to maintain elements in a specific sequence. The List interface adds a large number of methods based on Collection, making it possible to Insert and remove elements.

    public interface List<E> extends Collection<E> {

        ...

        boolean add(E e);

        boolean remove(Object o);

        boolean containsAll(Collection<?> c);

        boolean addAll(Collection<? extends E> c);

        boolean addAll(int index, Collection<? extends E> c);

        boolean removeAll(Collection<?> c);

        boolean retainAll(Collection<?> c);

        E get(int index);

        E set(int index, E element);

        void add(int index, E element);

        E remove(int index);

        int indexOf(Object o);

        int lastIndexOf(Object o);

        java.util.List<E> subList(int fromIndex, int toIndex);

        ...

    }

There are two types of List, ArrayList and LinkedList

List typeAdvantagesDisadvantagesUnderlying implementationArrayListRandom access to elements is fasterInsertion and deletion of intermediate elements are slower Insertion and deletion of intermediate elements, optimization of sequential access#Set

		Array	##LinkedList
Random Accessing elements is slower	Doubly linked list

Set does not save duplicate elements and is usually used for Find elements quickly. It is worth mentioning that Set has exactly the same interface as Collection without any additional features. The stored elements must define the equals() method

##Set type

Usage scenariosUnderlying implementationHashSetFast search, the element must define hashCode()Linked listTreeSet To maintain order, elements must implement the Comparable interface Red-black tree structure LinkedHashSetHashSet to maintain order, elements must define hashCode ()Linked list

Queue

除了并发应用，Queue仅有的两个实现是LinkedList和PriorityQueue, 其中LinkedList同时实现了List, Deque接口。它们的差异在于排序行为而不是性能。

    public interface Queue<E> extends Collection<E> {
        boolean add(E e);

        boolean offer(E e);

        E remove();

        E poll();

        E element();

        E peek();
    }

Map

Map类型	使用场景	底层实现
HashMap	快速查询	散列表
LinkedHashMap	迭代遍历具有顺序(插入顺序 or 最近最少使用)	链表
TreeMap	具有排序，唯一可以返回子树的Map(subMap())	红-黑树结构
WeakHashMap	弱键映射，映射之外无引用的键，可以被垃圾回收	散列表
ConcurrentHashMap	线程安全的Map	链表
IdentityHashMap	使用==代替equals()对键进行排序，专位解决特殊问题	链表

We can manually adjust HashMap to adjust performance, involving concepts such as capacity, initial capacity, size, load factor, etc. If you are interested, you can read some relevant information.

Some suggestions

• Don’t use outdated containers such as Vector Enumeration Hashtable Stack (yes, this is the original bad design of java. If you use the stack in practice, LinkedList is recommended)

Advanced·Concurrent Container

I will not discuss the detailed implementation here. I will only briefly introduce the basic knowledge. If you are interested, you can read "Java Concurrent Programming" Art" book.

CopyOnWriteArrayList and Copy-On-Write Strategy

Copy-On-Write, referred to as COW, is an optimization strategy used in programming. The basic idea is that everyone is sharing the same content from the beginning. When someone wants to modify the content, they will actually copy the content to form a new content and then modify it. This is a kind of delayed laziness. Strategy. Starting from JDK1.5, the Java concurrency package provides two concurrent containers implemented using the CopyOnWrite mechanism, which are CopyOnWriteArrayList and CopyOnWriteArraySet. The CopyOnWrite container is very useful and can be used in many concurrent scenarios.

The CopyOnWrite container is a container that is copied on write. The popular understanding is that when we add elements to a container, we do not add them directly to the current container, but first copy the current container to create a new container, and then add elements to the new container. After adding the elements, Then point the reference of the original container to the new container. The advantage of this is that we can perform concurrent reads on the CopyOnWrite container without locking, because the current container will not add any elements. Therefore, the CopyOnWrite container is also an idea of ​​separation of reading and writing, and reading and writing are different containers.

The CopyOnWrite container can only guarantee the final consistency of the data, but cannot guarantee the real-time consistency of the data. So if you want the written data to be read immediately, please do not use the CopyOnWrite container.

ConcurrentLinkedQueue

In concurrent programming, sometimes you need to use a thread-safe queue or list. There are usually two ways to achieve thread safety, one is to use blocking algorithms, and the other is to use non-blocking algorithms. The basis of non-blocking algorithm implementation is loopCAS (Compare and Swipe comparison and exchange).

The technical implementation of ConcurrentLinkedQueue is similar to CopyOnWriteArrayList and Copy, but only part of the container content rather than the entire container can be copied and modified. ConcurrentLinkedQueue consists of head node and tail node. Each node consists of a node element (item) and a reference pointing to the next node (next). The nodes are associated through next to form a queue with a linked list structure.

ConcurrentHashMap and lock segmentation technology

ConcurrentHashMap is a thread-safe and efficient HashMap. In a multi-threaded environment, using a non-thread-safe HashMap will lead to an infinite loop, and as suggested in the article, outdated containers such as HashTable are inefficient (use synchronized to ensure thread safety). ConcurrentHashMap uses lock segmentation technology to greatly improve the efficiency of concurrent use.

Lock segmentation technology: Assume that the container has multiple locks, and each lock is used to lock a part of the data in the container. When multiple threads access different data segments of the container, there is no lock between threads. Competition to improve concurrent access efficiency.

Blocking Queue

JDK7 provides 7 blocking queues. The implementation principles are all based on the production-consumption mode waiting notification mechanism.

##ArrayBlockingQueue Bounded blocking queue composed of array structureLinkedBlockingQueueBounded blocking queue composed of linked list structurePriorityBlockingQueue SupportDelayQueueUnbounded blocking queue implemented using priority queueSynchronousQueueA blocking queue that does not store elementsLinkedTransferQueueAn unbounded blocking queue composed of a linked list structure LinkedBlockingQueueA two-way blocking queue composed of a linked list structure

Blocking Queue Type	Features
	PrioritySorted unbounded blocking queue

The above is the detailed content of Detailed introduction to a comprehensive summary of Java container related knowledge (picture). For more information, please follow other related articles on the PHP Chinese website!