无题

参考文献

• 3W 字详解 Java 集合
• 源码阅读(1)：Java中主要的List结构——概述

集合框架

所有集合实现类的最顶层接口为Iterable和Collection接口,再向下Collection分为了三种不同的形式,分别是List,Queue和Set接口,然后就是对应的不同的实现方式.

• List

  • ArrayList： Object[] 数组

  • Vector：Object[] 数组

  • LinkedList： 双向链表(JDK1.6 之前为循环链表,JDK1.7 取消了循环)

• Set

  • HashSet(无序,唯一): 基于 HashMap 实现的,底层采用 HashMap 来保存元素

  • LinkedHashSet: LinkedHashSet 是 HashSet 的子类,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样,不过还是有一点点区别的

  • TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树)

• Queue

  • PriorityQueue: Object[] 数组来实现二叉堆,底层使用可变长的数组来存储数据

  • ArrayDeque: Object[] 数组 + 双指针,是基于可变长的数组和双指针来实现

• Map

  • HashMap： JDK1.8 之前 HashMap 由数组+链表组成的,JDK1.8之后由数组+链表+红黑树组成.

  • LinkedHashMap： LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。

  • Hashtable： 数组+链表组成的,数组是 Hashtable 的主体,链表则是主要为了解决哈希冲突而存在的

  • TreeMap： 红黑树（自平衡的排序二叉树）

顶层接口

java.util.Iterable

public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

Iterator 与 ListIterator详解

Iterator

• Iterator是一个接口,它是集合的迭代器.集合可以通过Iterator去遍历集合中的元素.

• Iterator提供的API接口如下:

  • boolean hasNext():判断集合里是否存在下一个元素.如果有,hasNext()方法返回 true.
  • Object next():返回集合里下一个元素.
  • void remove():删除集合里上一次next方法返回的元素.

• Iterator只能单向移动.

• Iterator.remove()是唯一安全的方式来在迭代过程中修改集合；如果在迭代过程中以任何其它的方式修改了基本集合将会产生未知的行为.而且每调用一次next()方法,remove()方法只能被调用一次,如果违反这个规则将抛出一个异常.

ListIterator

• **ListIterator是一个功能更加强大的迭代器, 它继承于Iterator接口,**只能用于各种List类型的访问.可以通过调用listIterator()方法产生一个指向List开始处的ListIterator, 还可以调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator.
• 由以上定义我们可以推出ListIterator可以:
  • 双向移动(向前/向后遍历).
  • 产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引.
  • 可以使用set()方法替换它访问过的最后一个元素.
  • 可以使用add()方法在next()方法返回的元素之前或previous()方法返回的元素之后插入一个元素.

java.util.Collection

public interface Collection<E> extends Iterable<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 removeAll(Collection<?> c);

    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }

    boolean retainAll(Collection<?> c);

    void clear();

    // Comparison and hashing

    boolean equals(Object o);

    int hashCode();

    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }

    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }

    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

java.util.Spliterator

• java.lang.Iterable接口中的另一个方法spliterator()，实际上它是“并行迭代器”的定义接口。要说明这个在JDK1.8中提供的“并行迭代器”接口

Set、List和Map可以看做集合的三大类

• List集合是有序集合,集合中的元素可以重复,访问集合中的元素可以根据元素的索引来访问.
• Set集合是无序集合,集合中的元素不可以重复,访问集合中的元素只能根据元素本身来访问(也是集合里元素不允许重复的原因).
• Map集合中保存Key-value对形式的元素,访问时只能根据每项元素的key来访问其value.

java.util.AbstractList抽象类

• 在Java中根据List性质的集合在各个维度上表现出来的工作特点，这些List结合可以被分成三种类型：

  • 是否支持随机访问的特点进行分类

    • 支持随机访问（读）的集合和不支持随机访问（读）的集合
      • 所谓支持随机访问集合，就是指集合提供相关功能可以对List集合中任意位置的元素进行时间复杂度不改变的定位操作。

    java.util.RandomAccess

  • 按照是否具有可修改权限进行分类

    • 分为可修改集合和不可修改集合
      • 所谓可修改集合是指操作者可以在集合指定的索引位置指定一个存储值；
      • 所谓不可修改集合既是操作者只能获取集合指定索引位置的存储值，但是并不能对这个索引位置的值进行替换，使用者也可以获取当前集合的大小，且这个大小的值一定是不可改变的。

    java.util.Collections.UnmodifiableCollection

  • 按照大小是否可变进行分类

    • 分为大小可变集合和大小不可变集合
    • 所谓大小不可变集合，既是说一旦这个集合完成了实例化，那么大小就一直固定下来不再变化，而大小可变集合的定义则刚好相反。

• Java中为List定义的“随机访问”的意义和磁盘IO上的“随机读”是有区别的（也有相似性），虽然两者都是在说“可以在某个指定的独立位置读取数据”这个事情，但是由于机械磁盘“旋转”的定位方式或者由于固态磁盘的垃圾标记/回收机制，所以磁盘IO读写中的“随机读”性能是要显著慢于磁盘IO读写中的“顺序读”的；List中定义的“随机访问”需要从算法的“时间复杂度”层面考虑，例如使用数组结构作为List集合基本结构时，其找到一个“指定”位置的时间复杂度为常量O(1)——因为可以直接定位到指定的内存起始位置，并通过偏移量进行最终定位。所以List性质的集合中定义的支持“随机访问”的集合结构，在数据读取性能上远远优于那些不支持“随机访问”的List集合

List

List表示一串有序的集合,和Collection接口含义不同的是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);

    // Bulk Modification Operations

    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);
    
    boolean removeAll(Collection<?> c);    
    
    boolean retainAll(Collection<?> c);
    
    void clear();

    // Comparison and hashing
  
    boolean equals(Object o);

    int hashCode();
    
    //============================
    // 		List独有方法
    //============================
    boolean addAll(int index, Collection<? extends E> c);

    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }

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

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

    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.ORDERED);
    }
}

Collection与List的区别

• Collection和List最大的区别是Collection是无序的,不支持索引操作,而List是有序的.Collection没有顺序的概念;
• List中Iterator为ListIterator;
• List可以进行排序,List接口支持使用sort方法;
• 两者的spliterator操作不一样;

ArrayList

LinkedList

Vector

Vector是线程安全的动态数组

Vector常量

/**
 * The array buffer into which the components of the vector are
 * stored. The capacity of the vector is the length of this array buffer,
 * and is at least large enough to contain all the vector's elements.
 *  这个数组就是用来存储Vector中每个元素的。其数组大小可以扩展，并且数组的最小值都足以存储下已写入Vector集合的每一个元素
 * 数组的大小也可以大于当前已写入Vector集合的所有元素的大小。如果是那样的话，那么多出来的数组位置上的值都为null
 * 该数组的初始化大小由构造函数中的initialCapacity参数决定，initialCapacity参数的默认大小为10
 * <p>Any array elements following the last element in the Vector are null.
 *
 * @serial
 */
protected Object[] elementData;

/**
 * The number of valid components in this {@code Vector} object.
 * Components {@code elementData[0]} through
 * {@code elementData[elementCount-1]} are the actual items.
 * 这个变量用于记录当前Vector集合中真实的元素数量，在后续的源代码阅读中会发现这个值在整个操作过程中更多起到的是验证作用。
 * 例如判断元素的位置是否超过了最大位置。
 * @serial
 */
protected int elementCount;

/**
 * The amount by which the capacity of the vector is automatically
 * incremented when its size becomes greater than its capacity.  If
 * the capacity increment is less than or equal to zero, the capacity
 * of the vector is doubled each time it needs to grow.
 * Vector集合支持大小扩容，实际上也就是对其中的elementData进行“变长”操作。
 * capacityIncrement变量表示每次扩容的大小，如果capacityIncrement的值小于等于0，那么扩容大小为其当前大小的一倍
 * @serial
 */
protected int capacityIncrement;

Vector构造函数

/**
     * Constructs an empty vector with the specified initial capacity and
     * capacity increment.
     *
     * @param   initialCapacity     the initial capacity of the vector
     * @param   capacityIncrement   the amount by which the capacity is
     *                              increased when the vector overflows
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        // elementData 数组从null被重新指定了一个数组的地址，数组大小默认为10；
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    /**
     * Constructs an empty vector with the specified initial capacity and
     * with its capacity increment equal to zero.
     *
     * @param   initialCapacity   the initial capacity of the vector
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

    /**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.
     */
    public Vector() {
        this(10);
    }

    /**
     * Constructs a vector containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this
     *       vector
     * @throws NullPointerException if the specified collection is null
     * @since   1.2
     */
    public Vector(Collection<? extends E> c) {
        Object[] a = c.toArray();
        elementCount = a.length;
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, elementCount, Object[].class);
        }
    }

Vector扩容

/**
 * This implements the unsynchronized semantics of ensureCapacity.
 * Synchronized methods in this class can internally call this
 * method for ensuring capacity without incurring the cost of an
 * extra synchronization.
 * 此私有方法用于在进行各种会引起容器内数据量发生变化的操作前，进行容器容量检查。
 * Vector集合是一个线程安全的集合（虽然锁性能不高），也就是说以上提到的各种“可能引起容器内数据量发生变化”的操作都是通过
 * synchronized关键字进行了线程安全控制的，所以此私有方法就无需再加synchronized关键字了，以便减少性能开销
 * @see #ensureCapacity(int)
 */
private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    // 入参所传入的最小容量（minCapacity）如果大于当前Vector集合elementData数组的大小，则进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    // 将“扩容”操作前当前elementData数组的大小保存下来（保存成oldCapacity），后面可能用到。
    int oldCapacity = elementData.length;
    // 这句代码非常关键，确定新的容量有两种情况：
// 1、如果当前设定了有效的扩容大小（在Vector集合初始化时可以设定），那么新的容量 = 老的容量 + 设定的扩容值
// 2、如果当前没有设定有效的扩容大小（既是capacityIncrement的值 <= 0 ），那么新的容量 = 老的容量 * 2
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    // 如果当前新的容量 小于 grow方法调用时传入的最小容量，则新的容量以传入的最小容量为准
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果当前新的容量 大于 MAX_ARRAY_SIZE常量，这个常量为2147483639[0x7ffffff7]
// 那么调用hugeCapacity()方法确认新的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 最后使用Arrays工具类提供的copyOf方法完成真实的扩容过程
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果当前方法调用传入的minCapacity的值，大于常量2147483639，那么取Java中整数类型的最大值2147483647
// 否则就取MAX_ARRAY_SIZE常量的值2147483639
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

• Arrays.copyOf(T[] original, int newLength)方法：该方法是一个工具性质的方法，其方法意义为复制指定数组（original）为一个新的数组对象，后者的长度为给定的新长度（newLength）。按照这样的描述，根据给定的新长度（newLength）就会出现两种不同的情况：
  • 第一种情况是新长度（newLength）小于指定的数组（original）的原始长度，那么无法复制的数组部分将会被截断；
  • 第二种情况是新长度（newLength）大于等于指定的数组（original）的原始长度，这时原始数组中的所有元素对象（的引用地址）将依据原来的索引位置被依次复制到新的数组中，多出来空余的部分将被填充null值。

Vector添加元素

/**
 * Appends the specified element to the end of this Vector.
 *
 * @param e element to be appended to this Vector
 * @return {@code true} (as specified by {@link Collection#add})
 * @since 1.2
 */
public synchronized boolean add(E e) {
    modCount++;
    // 该方法来确认是否进行elementData数组的“扩容”操作，并在满足条件时进行扩容。
    ensureCapacityHelper(elementCount + 1);
    // 在当前数组的elementCount位置之后，添加新的对象e
    elementData[elementCount++] = e;
    return true;
}

/**
 * Inserts the specified element at the specified position in this Vector.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws ArrayIndexOutOfBoundsException if the index is out of range
 *         ({@code index < 0 || index > size()})
 * @since 1.2
 */
public void add(int index, E element) {
    insertElementAt(element, index);
}
/**
 * Inserts the specified object as a component in this vector at the
 * specified {@code index}. Each component in this vector with
 * an index greater or equal to the specified {@code index} is
 * shifted upward to have an index one greater than the value it had
 * previously.
 *
 * <p>The index must be a value greater than or equal to {@code 0}
 * and less than or equal to the current size of the vector. (If the
 * index is equal to the current size of the vector, the new element
 * is appended to the Vector.)
 *
 * <p>This method is identical in functionality to the
 * {@link #add(int, Object) add(int, E)}
 * method (which is part of the {@link List} interface).  Note that the
 * {@code add} method reverses the order of the parameters, to more closely
 * match array usage.
 *
 * @param      obj     the component to insert
 * @param      index   where to insert the new component
 * @throws ArrayIndexOutOfBoundsException if the index is out of range
 *         ({@code index < 0 || index > size()})
 */
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

Vector移除元素

/**
 * Removes the element at the specified position in this Vector.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).  Returns the element that was removed from the Vector.
 *
 * @throws ArrayIndexOutOfBoundsException if the index is out of range
 *         ({@code index < 0 || index >= size()})
 * @param index the index of the element to be removed
 * @return element that was removed
 * @since 1.2
 */
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        // 复制数组,假设数组移除了中间某元素,后边有效值前移1位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

• System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法，该方法是一种JNI native方法，是JDK提供的进行两个数组中元素复制的性能最快的方法
  • src：该参数只能传入数组，表示当前进行数组元素复制的来源
  • srcPos：该参数描述源数组中进行复制操作时的起始元素位置
  • dest：该参数同样只能传入数组，标识当前进行数组元素复制的目标数组
  • destPos：该参数描述目标数组中进行复制操作时的起始元素位置
  • length：该参数指定进行复制的长度。

Stack

package java.util;

/**
 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.
 * <p>
 * When a stack is first created, it contains no items.
 *
 * <p>A more complete and consistent set of LIFO stack operations is
 * provided by the {@link Deque} interface and its implementations, which
 * should be used in preference to this class.  For example:
 * <pre>   {@code
 *   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
 *
 * @author  Jonathan Payne
 * @since   JDK1.0
 */
public
class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }

    /**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);

        return item;
    }

    /**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    /**
     * Tests if this stack is empty.
     *
     * @return  <code>true</code> if and only if this stack contains
     *          no items; <code>false</code> otherwise.
     */
    public boolean empty() {
        return size() == 0;
    }

    /**
     * Returns the 1-based position where an object is on this stack.
     * If the object <tt>o</tt> occurs as an item in this stack, this
     * method returns the distance from the top of the stack of the
     * occurrence nearest the top of the stack; the topmost item on the
     * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
     * method is used to compare <tt>o</tt> to the
     * items in this stack.
     *
     * @param   o   the desired object.
     * @return  the 1-based position from the top of the stack where
     *          the object is located; the return value <code>-1</code>
     *          indicates that the object is not on the stack.
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

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.
     * 增加一个元素.如果队列已满,则抛出一个IIIegaISlabEepeplian异常
     * @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.
     * 添加一个元素并返回true.如果队列已满,则返回false
     * @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.
     * 移除队列头部元素并返回,如果为空,返回null
     * @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.
     * 查询队列中第一个元素,如果为空,返回null
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();
}

• offer,add 区别:

  • 一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,多出的项就会被拒绝.

  • 这时新的 offer 方法就可以起作用了.它不是对调用 add() 方法抛出一个 unchecked 异常,而只是得到由 offer() 返回的 false.

• poll,remove 区别:

  • remove() 和 poll() 方法都是从队列中删除第一个元素.remove() 的行为与 Collection 接口的版本相似, 但是新的 poll() 方法在用空集合调用时不是抛出异常,只是返回 null.因此新的方法更适合容易出现异常条件的情况.

• peek,element区别:

  • element() 和 peek() 用于在队列的头部查询元素.与 remove() 方法类似,在队列为空时, element() 抛出一个异常,而 peek() 返回 null.

Deque接口

Deque英文全称是Double ended queue,也就是俗称的双端队列.对于这个队列容器,既可以从头部插入也可以从尾部插入,既可以从头部获取,也可以从尾部获取.

PriorityQueue

• 优先队列的作用是能保证每次取出的元素都是队列中权值最小的,元素大小的评判可以通过元素本身的自然顺序(natural orderingå),也可以通过构造时传入的比较器

PriorityQueue常量

  private static final int DEFAULT_INITIAL_CAPACITY = 11;

  /**
* 存放元素的数组    
   * Priority queue represented as a balanced binary heap: the twoå
   * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
   * priority queue is ordered by comparator, or by the elements'
   * natural ordering, if comparator is null: For each node n in the
   * heap and each descendant d of n, n <= d.  The element with the
   * lowest value is in queue[0], assuming the queue is nonempty.
   */
  transient Object[] queue; // non-private to simplify nested class access

  /**
   * 队列中存放了多少元素 
   * The number of elements in the priority queue.
   */
  private int size = 0;

  /**
   * 自定义的比较规则,有该规则时优先使用,否则使用元素实现的Comparable接口方法.
   * The comparator, or null if priority queue uses elements'
   * natural ordering.
   */
  private final Comparator<? super E> comparator;

  /**
   * 队列修改次数,每次存取都算一次修改
   * The number of times this priority queue has been
   * <i>structurally modified</i>.  See AbstractList for gory details.
   */
  transient int modCount = 0; // non-private to simplify nested class access

PriorityQueue添加元素

/**
 * Inserts the specified element into this priority queue.
 *
 * @return {@code true} (as specified by {@link Collection#add})
 * @throws ClassCastException if the specified element cannot be
 *         compared with elements currently in this priority queue
 *         according to the priority queue's ordering
 * @throws NullPointerException if the specified element is null
 */
public boolean add(E e) {
    return offer(e);
}

/**
 * Inserts the specified element into this priority queue.
 *
 * @return {@code true} (as specified by {@link Queue#offer})
 * @throws ClassCastException if the specified element cannot be
 *         compared with elements currently in this priority queue
 *         according to the priority queue's ordering
 * @throws NullPointerException if the specified element is null
 */
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

ArrayDeque

• ArrayDeque是Deque接口的一个实现,使用了可变数组,所以没有容量上的限制.同时,ArrayDeque是线程不安全的,在没有外部同步的情况下,不能再多线程环境下使用.
• ArrayDeque是 Deque的实现类,可以作为栈来使用,效率高于 Stack；也可以作为队列来使用,效率高于 LinkedList.
• ArrayDeque 是 Java 集合中双端队列的数组实现,双端队列的链表实现（LinkedList）
• 需要注意的是,ArrayDeque不支持 null值.

Set

Set是一种不包括重复元素的Collection.它维持它自己的内部排序,所以随机访问没有任何意义.与List一样,它同样允许null的存在但是仅有一个.由于Set接口的特殊性,所有传入Set集合中的元素都必须不同,同时要注意任何可变对象,如果在对集合中元素进行操作时,导致e1.equals(e2)==true,则必定会产生某些问题.Set接口有三个具体实现类,分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet.

Set是一种不包含重复的元素的Collection,无序,即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素.

需要注意的是:虽然Set中元素没有顺序,但是元素在set中的位置是由该元素的hashCode决定的,其具体位置其实是固定的.

HashSet

HashSet 是一个没有重复元素的集合.它是由HashMap实现的,不保证元素的顺序(这里所说的没有顺序是指:元素插入的顺序与输出的顺序不一致),而且HashSet允许使用null 元素.HashSet是非同步的,如果多个线程同时访问一个哈希set,而其中至少一个线程修改了该set,那么它必须保持外部同步. HashSet按Hash算法来存储集合的元素,因此具有很好的存取和查找性能.

HashSet使用和理解中容易出现的误区

• HashSet中存放null值.HashSet中是允许存入null值的,但是在HashSet中仅仅能够存入一个null值.

• HashSet中存储元素的位置是固定的.HashSet中存储的元素的是无序的,这个没什么好说的,但是由于HashSet底层是基于Hash算法实现的,使用了hashCode,所以HashSet中相应的元素的位置是固定的.

• 必须小心操作可变对象(Mutable Object).如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题.

LinkedHashSet

LinkedHashSet继承自HashSet,其底层是基于LinkedHashMap来实现的,有序,非同步.LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置,但是它同时使用链表维护元素的次序.这样使得元素看起来像是以插入顺序保存的,也就是说,当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素.

TreeSet

TreeSet是一个有序集合,其底层是基于TreeMap实现的,非线程安全.TreeSet可以确保集合元素处于排序状态.**TreeSet支持两种排序方式,自然排序和定制排序,其中自然排序为默认的排序方式.**当我们构造TreeSet时,若使用不带参数的构造函数,则TreeSet的使用自然比较器；若用户需要使用自定义的比较器,则需要使用带比较器的参数.

注意:TreeSet集合不是通过hashCode和equals函数来比较元素的.它是通过compare或者comparaeTo函数来判断元素是否相等.compare函数通过判断两个对象的id,相同的id判断为重复元素,不会被加入到集合中.

Map

Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射.同时它也没有继承Collection.在Map中它保证了key与value之间的一一对应关系.也就是说一个key对应一个value,所以它不能存在相同的key值,当然value值可以相同.

HashMap

HashMap分析

LinkedHashMap

LinkedHashMap是HashMap的一个子类,它保留插入的顺序,如果需要输出的顺序和输入时的相同,那么就选用LinkedHashMap.

**LinkedHashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序.**此实现提供所有可选的映射操作,并允许使用null值和null键.此类不保证映射的顺序,特别是它不保证该顺序恒久不变.

LinkedHashMap实现与HashMap的不同之处在于,后者维护着一个运行于所有条目的双重链接列表.此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序.

根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用get方法)的链表.默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表.

注意,此实现不是同步的.如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步.由于LinkedHashMap需要维护元素的插入顺序,因此性能略低于HashMap的性能,但在迭代访问Map里的全部元素时将有很好的性能,因为它以链表来维护内部顺序.

TreeMap

TreeMap是一个有序的key-value集合,非同步,基于红黑树(Red-Black tree)实现,每一个key-value节点作为红黑树的一个节点.TreeMap存储时会进行排序的,会根据key来对key-value键值对进行排序,其中排序方式也是分为两种,一种是自然排序,一种是定制排序,具体取决于使用的构造方法.

自然排序:TreeMap中所有的key必须实现Comparable接口,并且所有的key都应该是同一个类的对象,否则会报ClassCastException异常.

**定制排序:**定义TreeMap时,创建一个comparator对象,该对象对所有的TreeMap中所有的key值进行排序,采用定制排序的时候不需要TreeMap中所有的key必须实现Comparable接口.

TreeMap判断两个元素相等的标准:两个key通过compareTo()方法返回0,则认为这两个key相等.

常见问题

HashTable与HashMap

• 相同点:

  • 都实现了Map、Cloneable、java.io.Serializable接口.
  • 都是存储"键值对(key-value)"的散列表,而且都是采用拉链法实现的.

• 不同点:

  • 历史原因:HashTable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现 .

  • 同步性:HashTable是线程安全的,也就是说是同步的,而HashMap是线程序不安全的,不是同步的 .

  • 对null值的处理:HashMap的key、value都可为null,HashTable的key、value都不可为null .

  • 基类不同:HashMap继承于AbstractMap,而Hashtable继承于Dictionary.

  • 支持的遍历种类不同:HashMap只支持Iterator(迭代器)遍历.而Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历.

  • HashMap提供对key的Set进行遍历,因此它是fail-fast的,但HashTable提供对key的Enumeration进行遍历,它不支持fail-fast.

Fail-Fast与Fail-Safe有什么区别?

• Iterator的Fail-Fast属性与当前的集合共同起作用,因此它不会受到集合中任何改动的影响.

• Java.util包中的所有集合类都被设计为Fail-Fast的,而java.util.concurrent中的集合类都为Fail-Safe的.

• Fall-fast迭代器抛出ConcurrentModificationException;

• Fall-safe迭代器从不抛出ConcurrentModificationException.

ArrayList和Vector有何异同点?

• 相同点:

  • 两者都是基于索引的,内部由一个数组支持.
  • 两者维护插入的顺序,我们可以根据插入顺序来获取元素.
  • ArrayList和Vector的迭代器实现都是fail-fast的.
  • ArrayList和Vector两者允许null值,也可以使用索引值对元素进行随机访问.

• 不同点:

  • Vector是同步的,而ArrayList不是.然而,如果你寻求在迭代的时候对列表进行改变,你应该使用CopyOnWriteArrayList.

  • ArrayList比Vector快,它因为没有同步,不会过载.

  • ArrayList更加通用,因为我们可以使用Collections工具类轻易地获取同步列表和只读列表.

  • Vector默认增长为原来的一倍,而ArrayList却是原来的一半;

    // Vector
    private void grow(int minCapacity) {
           // overflow-conscious code
           int oldCapacity = elementData.length;
           // 若没有指定capacityIncrement,则扩容两倍
           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);
       }

    // ArrayList
    /**
        * Increases the capacity to ensure that it can hold at least the
        * number of elements specified by the minimum capacity argument.
        *
        * @param minCapacity the desired minimum capacity
        */
       private void grow(int minCapacity) {
           // overflow-conscious code
           int oldCapacity = elementData.length;
           // 采用右移运算,就是原来的一般,所以是扩容1.5倍.
           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);
       }

Array和ArrayList有何区别？什么时候更适合用Array？

• Array可以容纳基本类型和对象,而ArrayList只能容纳对象;
• Array是指定大小的,而ArrayList大小是固定的;
• Array没有提供ArrayList那么多功能,比如addAll、removeAll和Iterator等;
• 如果列表的大小已经指定,大部分情况下是存储和遍历它们.
• 对于遍历基本数据类型,尽管Collections使用自动装箱来减轻编码任务,在指定大小的基本类型的列表上工作也会变得很慢.
• 如果你要使用多维数组,使用[][]比List<List<>>更容易.

Collection和Collections的区别

• Collection是java.util下的接口,它是各种集合的父接口,继承与它的接口主要有List和Set;
• Collections是java.util下的类,是针对集合的帮助类,提供一系列静态方法实现,对各种集合的搜索,排序,线程安全等操作;

ArrayList和LinkedList的区别?使用场景上有什么区别?

• 数据结构：ArrayList底层是基于数组实现的,而LinkedList底层是基于链表实现的。
• 插入和删除：ArrayList在插入和删除元素时,需要移动数组中的其他元素,因为数组的大小是固定的,所以它的插入和删除操作比较耗时。而LinkedList在插入和删除元素时,只需要改变链表中的指针即可,因为链表的大小是可以动态改变的,所以它的插入和删除操作比较快。
• 随机访问：ArrayList支持随机访问,可以通过索引值快速访问元素,而LinkedList不支持随机访问,需要从头开始遍历链表才能访问指定位置的元素。
• 内存占用：ArrayList在存储大量数据时,由于需要预先分配数组的大小,可能会浪费一定的内存空间。而LinkedList在存储大量数据时,由于是动态链表,可以根据实际情况动态地分配内存空间,所以内存占用比较小。
• ArrayList适合于随机访问、读取操作比较多的场景,而LinkedList适合于插入和删除操作比较多的场景,尤其是在数据量较大的情况下。

转换

• List to int Array

  int[] example1 = list.stream().mapToInt(i->i).toArray();
  // OR
  int[] example2 = list.stream().mapToInt(Integer::intValue).toArray();