Java并发 - J.U.C并发容器类 list、set、queue

叁歲伎倆 2023-10-14 20:55 26阅读 0赞

##### 1. List #####

###### ArrayList ######

*  本质就是一个数组
 *  初识化大小默认为 10

/**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;

*  每次扩容后大小变为原大小的1.5倍

private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);    // 扩容为1.5倍大小
            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);
        }

*  使用 `for(Object o : list)` 迭代器进行迭代循环的时候不应该对列表 `list` 进行新增或者删除操作，否则会报`ConcurrentModificationException` 异常，原因是因为迭代过程中会检查变量数量和期望的数量是否一致。

> 如以下操作就会报错

int i=0;
            for (Object o : list) {
                if(i==0)  list.add("neco");
                i++;
            }

> 抛出异常的代码

final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }

###### LinkedList ######

*  本质就是一个链表，没有什么特殊的内容
 *  里边的Node<E>是支持双向链表的

private static class Node<E> {
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

###### CopyOnWriteArrayList ######

*  在写的时候复制了一份出来，然后重新写入数据

/**
         * Appends the specified element to the end of this list.
         *
         * @param e element to be appended to this list
         * @return {@code true} (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] elements = getArray();
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len + 1);
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally {
                lock.unlock();
            }
        }

*  确保了读写可以同步进行，但是可能会有脏读的情况
 *  在多读少写的情况下可以使用

**CopyOnWriteArrayList**容器即写时复制的容器。和ArrayList比较，**优点是并发安全**，**缺点**有两个:  
1、多了内存占用:写数据是copy一份完整的数据，单独进行操作。占用双份内存。  
2、数据一致性:数据写完之后，其他线程不一定是马上读取到最新内容。

![format_png][]

##### 2. Set 集合 #####

和List比较：**不会重复**

<table> 
 <thead> 
  <tr> 
   <th>实现</th> 
   <th>原理</th> 
   <th>特点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HashSet</td> 
   <td>基于HashMap实现</td> 
   <td>非线程安全</td> 
  </tr> 
  <tr> 
   <td>CopyOnWriteArraySet</td> 
   <td>基于CopyOnWriteArrayList</td> 
   <td>线程安全</td> 
  </tr> 
  <tr> 
   <td>TreeSet</td> 
   <td>基于TreeMap</td> 
   <td>线程安全，有序，查询快</td> 
  </tr> 
 </tbody> 
</table>

###### HashSet ######

内部的实现本质就是一个Map（因为key值不重复），但是只是使用了Key，对于value无所谓

/**
         * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
         * default initial capacity (16) and load factor (0.75).
         */
        public HashSet() {
            map = new HashMap<>();
        }
    
    
        /**
         * Adds the specified element to this set if it is not already present.
         * More formally, adds the specified element <tt>e</tt> to this set if
         * this set contains no element <tt>e2</tt> such that
         * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
         * If this set already contains the element, the call leaves the set
         * unchanged and returns <tt>false</tt>.
         *
         * @param e element to be added to this set
         * @return <tt>true</tt> if this set did not already contain the specified
         * element
         */
        public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
    
        // Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();

###### CopyOnWriteArraySet ######

内部的本质是一个 CopyOnWriteArrayList，通过判断是否存在来确定是否放入数据

/**
         * Creates an empty set.
         */
        public CopyOnWriteArraySet() {
            al = new CopyOnWriteArrayList<E>();
        }
        
        /**
         * Adds the specified element to this set if it is not already present.
         * More formally, adds the specified element {@code e} to this set if
         * the set contains no element {@code e2} such that
         * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
         * If this set already contains the element, the call leaves the set
         * unchanged and returns {@code false}.
         *
         * @param e element to be added to this set
         * @return {@code true} if this set did not already contain the specified
         *         element
         */
        public boolean add(E e) {
            return al.addIfAbsent(e);
        }
    
        /**
         * Appends the element, if not present.
         *
         * @param e element to be added to this list, if absent
         * @return {@code true} if the element was added
         */
        public boolean addIfAbsent(E e) {
            Object[] snapshot = getArray();
            return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
                addIfAbsent(e, snapshot);
        }
    
        /**
         * A version of addIfAbsent using the strong hint that given
         * recent snapshot does not contain e.
         */
        private boolean addIfAbsent(E e, Object[] snapshot) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] current = getArray();
                int len = current.length;
                if (snapshot != current) {
                    // Optimize for lost race to another addXXX operation
                    int common = Math.min(snapshot.length, len);
                    for (int i = 0; i < common; i++)
                        if (current[i] != snapshot[i] && eq(e, current[i]))
                            return false;
                    if (indexOf(e, current, common, len) >= 0)
                            return false;
                }
                Object[] newElements = Arrays.copyOf(current, len + 1);
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally {
                lock.unlock();
            }
        }

###### TreeSet ######

本质是一个TreeMap，但是也只用到了Key值，Value值没有什么意义。

/**
         * Constructs a new, empty tree set, sorted according to the
         * natural ordering of its elements.  All elements inserted into
         * the set must implement the {@link Comparable} interface.
         * Furthermore, all such elements must be <i>mutually
         * comparable</i>: {@code e1.compareTo(e2)} must not throw a
         * {@code ClassCastException} for any elements {@code e1} and
         * {@code e2} in the set.  If the user attempts to add an element
         * to the set that violates this constraint (for example, the user
         * attempts to add a string element to a set whose elements are
         * integers), the {@code add} call will throw a
         * {@code ClassCastException}.
         */
        public TreeSet() {
            this(new TreeMap<E,Object>());
        }
    
        /**
         * Adds the specified element to this set if it is not already present.
         * More formally, adds the specified element {@code e} to this set if
         * the set contains no element {@code e2} such that
         * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
         * If this set already contains the element, the call leaves the set
         * unchanged and returns {@code false}.
         *
         * @param e element to be added to this set
         * @return {@code true} if this set did not already contain the specified
         *         element
         * @throws ClassCastException if the specified object cannot be compared
         *         with the elements currently in this set
         * @throws NullPointerException if the specified element is null
         *         and this set uses natural ordering, or its comparator
         *         does not permit null elements
         */
        public boolean add(E e) {
            return m.put(e, PRESENT)==null;
        }
    
        // Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();

**SET接口没有所谓的有序还是无序。 TreeSet是有序的，此有序是说读取数据的顺序和插入数据的顺序一样。 HashSet无序？ 此无序说的是读取数据的顺序不一定和插入数据的顺序一样。**

##### 3. Queue #####

###### Queue API ######

Queue -队列数据结构的实现。分为阻塞队列和非阻塞队列。下列的蓝色区块，为阻塞队列特有的方法。

![format_png 1][]

阻塞是通过condition来实现的，可参考 [Java并发 - Lock接口][Java_ - Lock]

*  ArrayBlockingQueue 阻塞
 *  LinkedBlockingQueue 阻塞
 *  ArrayQueue 非阻塞
 *  LinkedQueue 非阻塞

[format_png]: https://img-blog.csdnimg.cn/img_convert/e47c34eaf683930de4b8c209616d8b80.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/c99c1b9278d4707ea8ec806ff8337f0b.webp?x-oss-process=image/format,png
[Java_ - Lock]: https://www.jianshu.com/p/5662487727e3