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);

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

Copy after login

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();
  
      }

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

. 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());
            }
    }

hasNext() determines whether there are still elements

remove() deletes the specified element


ListIterator

    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);

        ...

    }

Copy after login

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

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

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.

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!