jdk1.8集合框架源码解析（三）List、Set、Queue源码解析

╰半橙微兮° 2022-03-31 13:56 256阅读 0赞

List 是有序集合的顶级接口，Set是无序集合的顶级接口，Queue是队列的顶级接口

# List源码解析 #

public interface List<E> extends Collection<E> {
        // Query Operations
    
        
        int size();
    
     
        boolean isEmpty();
    
    
        boolean contains(Object o);
    
    
        Iterator<E> iterator();
    
    
        Object[] toArray();
    
      
        <T> T[] toArray(T[] a);
    
    
        // Modification Operations
    
        
        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);
    
    
         void clear();
    
    
      
    
    
        // Positional Access Operations
    
    
        E get(int index);
    
      
        E set(int index, E element);
    
     
        void add(int index, E element);
    
     
        E remove(int index);
    
    
        // Search Operations
    
    
        int indexOf(Object o);
    
       
        int lastIndexOf(Object o);
    
    
        // List Iterators
    
      
        ListIterator<E> listIterator();
    
     
        ListIterator<E> listIterator(int index);
    
        // View
    
    
        List<E> subList(int fromIndex, int toIndex);
        
        // Comparison and hashing
    
    
        boolean equals(Object o);
    
      
        int hashCode();
    
        /**
         * Replaces each element of this list with the result of applying the
         * operator to that element.  Errors or runtime exceptions thrown by
         * the operator are relayed to the caller.
         *
         * @implSpec
         * The default implementation is equivalent to, for this {@code list}:
         * <pre>{@code
         *     final ListIterator<E> li = list.listIterator();
         *     while (li.hasNext()) {
         *         li.set(operator.apply(li.next()));
         *     }
         * }</pre>
         *
         * If the list's list-iterator does not support the {@code set} operation
         * then an {@code UnsupportedOperationException} will be thrown when
         * replacing the first element.
         *
         * @param operator the operator to apply to each element
         * @throws UnsupportedOperationException if this list is unmodifiable.
         *         Implementations may throw this exception if an element
         *         cannot be replaced or if, in general, modification is not
         *         supported
         * @throws NullPointerException if the specified operator is null or
         *         if the operator result is a null value and this list does
         *         not permit null elements
         *         (<a href="Collection.html#optional-restrictions">optional</a>)
         * @since 1.8
         */
        default void replaceAll(UnaryOperator<E> operator) {
            Objects.requireNonNull(operator);
            final ListIterator<E> li = this.listIterator();
            while (li.hasNext()) {
                li.set(operator.apply(li.next()));
            }
        }
    
        /**
         * Sorts this list according to the order induced by the specified
         * {@link Comparator}.
         *
         * <p>All elements in this list must be <i>mutually comparable</i> using the
         * specified comparator (that is, {@code c.compare(e1, e2)} must not throw
         * a {@code ClassCastException} for any elements {@code e1} and {@code e2}
         * in the list).
         *
         * <p>If the specified comparator is {@code null} then all elements in this
         * list must implement the {@link Comparable} interface and the elements'
         * {@linkplain Comparable natural ordering} should be used.
         *
         * <p>This list must be modifiable, but need not be resizable.
         *
         * @implSpec
         * The default implementation obtains an array containing all elements in
         * this list, sorts the array, and iterates over this list resetting each
         * element from the corresponding position in the array. (This avoids the
         * n<sup>2</sup> log(n) performance that would result from attempting
         * to sort a linked list in place.)
         *
         * @implNote
         * This implementation is a stable, adaptive, iterative mergesort that
         * requires far fewer than n lg(n) comparisons when the input array is
         * partially sorted, while offering the performance of a traditional
         * mergesort when the input array is randomly ordered.  If the input array
         * is nearly sorted, the implementation requires approximately n
         * comparisons.  Temporary storage requirements vary from a small constant
         * for nearly sorted input arrays to n/2 object references for randomly
         * ordered input arrays.
         *
         * <p>The implementation takes equal advantage of ascending and
         * descending order in its input array, and can take advantage of
         * ascending and descending order in different parts of the same
         * input array.  It is well-suited to merging two or more sorted arrays:
         * simply concatenate the arrays and sort the resulting array.
         *
         * <p>The implementation was adapted from Tim Peters's list sort for Python
         * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
         * TimSort</a>).  It uses techniques from Peter McIlroy's "Optimistic
         * Sorting and Information Theoretic Complexity", in Proceedings of the
         * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
         * January 1993.
         *
         * @param c the {@code Comparator} used to compare list elements.
         *          A {@code null} value indicates that the elements'
         *          {@linkplain Comparable natural ordering} should be used
         * @throws ClassCastException if the list contains elements that are not
         *         <i>mutually comparable</i> using the specified comparator
         * @throws UnsupportedOperationException if the list's list-iterator does
         *         not support the {@code set} operation
         * @throws IllegalArgumentException
         *         (<a href="Collection.html#optional-restrictions">optional</a>)
         *         if the comparator is found to violate the {@link Comparator}
         *         contract
         * @since 1.8
         */
        @SuppressWarnings({"unchecked", "rawtypes"})
        default void sort(Comparator<? super E> c) {
            Object[] a = this.toArray();
            Arrays.sort(a, (Comparator) c);
            ListIterator<E> i = this.listIterator();
            for (Object e : a) {
                i.next();
                i.set((E) e);
            }
        }
    
    
       
    
        /**
         * Creates a {@link Spliterator} over the elements in this list.
         *
         * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
         * {@link Spliterator#ORDERED}.  Implementations should document the
         * reporting of additional characteristic values.
         *
         * @implSpec
         * The default implementation creates a
         * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator
         * from the list's {@code Iterator}.  The spliterator inherits the
         * <em>fail-fast</em> properties of the list's iterator.
         *
         * @implNote
         * The created {@code Spliterator} additionally reports
         * {@link Spliterator#SUBSIZED}.
         *
         * @return a {@code Spliterator} over the elements in this list
         * @since 1.8
         */
        @Override
        default Spliterator<E> spliterator() {
            return Spliterators.spliterator(this, Spliterator.ORDERED);
        }
    }

## List3个默认方法 ##

<table>  List接口默认方法  
 <tbody> 
  <tr> 
   <td style="width:367px;">默认方法</td> 
   <td style="width:482px;">作用</td> 
  </tr> 
  <tr> 
   <td style="width:367px;">default void replaceAll(UnaryOperator&lt;E&gt; operator)&nbsp;</td> 
   <td style="width:482px;">对每个元素进行指定的操作</td> 
  </tr> 
  <tr> 
   <td style="width:367px;">&nbsp;default void sort(Comparator&lt;? super E&gt; c)&nbsp;</td> 
   <td style="width:482px;">按指定的规则对list进行排序</td> 
  </tr> 
  <tr> 
   <td style="width:367px;">&nbsp;default Spliterator&lt;E&gt; spliterator()</td> 
   <td style="width:482px;">获取有序的迭代器(具有<span style="color:#f33b45;">Spliterator</span>.<span style="color:#3399ea;">ORDERED</span>特征)</td> 
  </tr> 
 </tbody> 
</table>

--------------------

# Set源码解析 #

public interface Set<E> extends Collection<E> {
        // Query Operations
    
       
        int size();
    
       
        boolean isEmpty();
    
        
        boolean contains(Object o);
    
        
        Iterator<E> iterator();
    
       
        Object[] toArray();
    
       
        <T> T[] toArray(T[] a);
    
    
        // Modification Operations
    
        /**
       
        boolean add(E e);
    
    
        boolean remove(Object o);
    
    
        // Bulk Operations
    
       
        boolean containsAll(Collection<?> c);
    
       
        boolean addAll(Collection<? extends E> c);
    
       
        boolean retainAll(Collection<?> c);
    
        
        boolean removeAll(Collection<?> c);
    
       
        void clear();
    
    
        // Comparison and hashing
    
       
        boolean equals(Object o);
    
       
        int hashCode();
    
        /**
         * Creates a {@code Spliterator} over the elements in this set.
         *
         * <p>The {@code Spliterator} reports {@link Spliterator#DISTINCT}.
         * Implementations should document the reporting of additional
         * characteristic values.
         *
         * @implSpec
         * The default implementation creates a
         * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator
         * from the set's {@code Iterator}.  The spliterator inherits the
         * <em>fail-fast</em> properties of the set's iterator.
         * <p>
         * The created {@code Spliterator} additionally reports
         * {@link Spliterator#SIZED}.
         *
         * @implNote
         * The created {@code Spliterator} additionally reports
         * {@link Spliterator#SUBSIZED}.
         *
         * @return a {@code Spliterator} over the elements in this set
         * @since 1.8
         */
        //创建不重复的迭代器
        @Override
        default Spliterator<E> spliterator() {
            return Spliterators.spliterator(this, Spliterator.DISTINCT);
        }

## set的默认方法 ##

<table>  Set的默认方法  
 <tbody> 
  <tr> 
   <td style="width:242px;">默认方法</td> 
   <td style="width:607px;">作用</td> 
  </tr> 
  <tr> 
   <td style="width:242px;">&nbsp;default Spliterator&lt;E&gt; spliterator()</td> 
   <td style="width:607px;">创建不重复的迭代器</td> 
  </tr> 
 </tbody> 
</table>

# Queue源码解析 #

public interface Queue<E> extends Collection<E> {
        /**
         * Inserts the specified element into this queue if it is possible to do so
         * immediately without violating capacity restrictions, returning
         * {@code true} upon success and throwing an {@code IllegalStateException}
         * if no space is currently available.
         *
         * @param e the element to add
         * @return {@code true} (as specified by {@link Collection#add})
         * @throws IllegalStateException if the element cannot be added at this
         *         time due to capacity restrictions
         * @throws ClassCastException if the class of the specified element
         *         prevents it from being added to this queue
         * @throws NullPointerException if the specified element is null and
         *         this queue does not permit null elements
         * @throws IllegalArgumentException if some property of this element
         *         prevents it from being added to this queue
         */
        boolean add(E e);
    
        /**
         * Inserts the specified element into this queue if it is possible to do
         * so immediately without violating capacity restrictions.
         * When using a capacity-restricted queue, this method is generally
         * preferable to {@link #add}, which can fail to insert an element only
         * by throwing an exception.
         *
         * @param e the element to add
         * @return {@code true} if the element was added to this queue, else
         *         {@code false}
         * @throws ClassCastException if the class of the specified element
         *         prevents it from being added to this queue
         * @throws NullPointerException if the specified element is null and
         *         this queue does not permit null elements
         * @throws IllegalArgumentException if some property of this element
         *         prevents it from being added to this queue
         */
        boolean offer(E e);
    
        /**
         * Retrieves and removes the head of this queue.  This method differs
         * from {@link #poll poll} only in that it throws an exception if this
         * queue is empty.
         *
         * @return the head of this queue
         * @throws NoSuchElementException if this queue is empty
         */
        E remove();
    
        /**
         * Retrieves and removes the head of this queue,
         * or returns {@code null} if this queue is empty.
         *
         * @return the head of this queue, or {@code null} if this queue is empty
         */
        E poll();
    
        /**
         * Retrieves, but does not remove, the head of this queue.  This method
         * differs from {@link #peek peek} only in that it throws an exception
         * if this queue is empty.
         *
         * @return the head of this queue
         * @throws NoSuchElementException if this queue is empty
         */
        E element();
    
        /**
         * Retrieves, but does not remove, the head of this queue,
         * or returns {@code null} if this queue is empty.
         *
         * @return the head of this queue, or {@code null} if this queue is empty
         */
        E peek();
    }

<table>  Queue方法及其作用  
 <tbody> 
  <tr> 
   <td style="width:186px;"><strong>方法</strong></td> 
   <td style="width:663px;"><strong>作用</strong></td> 
  </tr> 
  <tr> 
   <td style="width:186px;">boolean add(E e)</td> 
   <td style="width:663px;"> <p>将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。</p> </td> 
  </tr> 
  <tr> 
   <td style="width:186px;">boolean offer(E e)</td> 
   <td style="width:663px;"> <p>将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 <a rel="nofollow"><code>add(E)</code></a>，后者可能无法插入元素，而只是抛出一个异常。</p> </td> 
  </tr> 
  <tr> 
   <td style="width:186px;">&nbsp;E remove()</td> 
   <td style="width:663px;"> <p>获取并移除此队列的头。此方法与 <a rel="nofollow"><code>poll</code></a> 唯一的不同在于：此队列为空时将抛出一个异常</p> </td> 
  </tr> 
  <tr> 
   <td style="width:186px;">&nbsp;E poll()</td> 
   <td style="width:663px;"> <p>获取并移除此队列的头，如果此队列为空，则返回 null。</p> </td> 
  </tr> 
  <tr> 
   <td style="width:186px;">&nbsp;E element()</td> 
   <td style="width:663px;"> <p>获取，但是不移除此队列的头。此方法与 <a rel="nofollow"><code>peek</code></a> 唯一的不同在于：此队列为空时将抛出一个异常。</p> </td> 
  </tr> 
  <tr> 
   <td style="width:186px;">E peek()</td> 
   <td style="width:663px;"> <p>获取但不移除此队列的头；如果此队列为空，则返回 null。</p> </td> 
  </tr> 
 </tbody> 
</table>

在处理元素前用于保存元素的 collection。除了基本的 `Collection` 操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的；在大多数实现中，插入操作不会失败。

<table> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td><em>抛出异常</em></td> 
   <td><em>返回特殊值</em></td> 
  </tr> 
  <tr> 
   <td><strong>插入</strong></td> 
   <td><span style="color:#3399ea;">boolean add(E e)</span></td> 
   <td><span style="color:#3399ea;">boolean offer(E e)</span></td> 
  </tr> 
  <tr> 
   <td><strong>移除</strong></td> 
   <td><span style="color:#3399ea;">&nbsp;E remove()</span></td> 
   <td><span style="color:#3399ea;">&nbsp;E poll()</span></td> 
  </tr> 
  <tr> 
   <td><strong>检查</strong></td> 
   <td><span style="color:#3399ea;">&nbsp;E element()</span></td> 
   <td><span style="color:#3399ea;">E peek()</span></td> 
  </tr> 
 </tbody> 
</table>