从Java源码分析面试中经常出现的集合类问题

/* @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Set
 * @see     List
 * @see     Map
 * @see     SortedSet
 * @see     SortedMap
 * @see     HashSet
 * @see     TreeSet
 * @see     ArrayList
 * @see     LinkedList
 * @see     Vector
 * @see     Collections
 * @see     Arrays
 * @see     AbstractCollection
 * @since 1.2
    集合层次结构中的根接口。集合表示一组对象，称为其元素。
    一些集合允许重复的元素，而另一些则不允许。有些是有序的，而另一些则是无序的。 
    JDK不提供此接口的任何直接实现：它提供了更多特定子接口的实现
 */
public interface Collection<E> extends Iterable<E> {
    // Query Operations
    /**
    返回此集合中的元素数
     */
    int size();
    /**
   如果此集合不包含任何元素，则返回<tt> true </ tt>
     */
    boolean isEmpty();
    ...........
        .........

/* @see Collection
 * @see List
 * @see SortedSet
 * @see HashSet
 * @see TreeSet
 * @see AbstractSet
 * @see Collections#singleton(java.lang.Object)
 * @see Collections#EMPTY_SET
 * @since 1.2
     不包含重复元素的集合
 */
public interface Set<E> extends Collection<E> {
    // Query Operations
    /**
     返回此集合中的元素数（其基数）
     */
    int size();
    /**
    如果此集合不包含任何元素，则返回<tt> true </ tt>
     */
    boolean isEmpty();
    /**
    如果此集合包含指定的元素，则返回<tt> true </ tt>
     */
    boolean contains(Object o);
    /**
   返回此集合中元素的迭代器。 *元素以不特定的顺序返回（除非此集合是提供保证的某些*类的实例）。
     */
    Iterator<E> iterator();
    ...........
        .........

/* @see     Collection
 * @see     List
 * @see     LinkedList
 * @see     Vector
 * @since   1.2
  List接口的可调整大小的数组实现。实现所有可选的列表操作，并允许所有元素，包括null。除了实现 List接口之外，此类还提供了一些方法来操纵内部用于存储列表的数组的大小
 */

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    /**
       默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
    用于空实例的共享空数组实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
    共享的空数组实例，用于默认大小的空实例。我们将其与EMPTY_ELEMENTDATA区别开来，以了解添加第一个元素时需要充气多少
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
      /**
    用于存储ArrayList元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。添加第一个元素时，任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY,
    该elementData是真正存放元素的容器，可见ArrayList是基于数组实现的;
     */
    transient Object[] elementData; //非私有，以简化嵌套类的访问

/** *构造一个具有指定初始容量的空列表。 @param initialCapacity列表的初始容量@如果指定的初始容量为负，则抛出IllegalArgumentException */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
      /** *构造一个初始容量为10的空列表。 */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**构造一个包含指定集合的元素的列表，其顺序由集合的迭代器返回。 @param c 要将其元素放入此列表的集合如果指定的集合为null，则抛出NullPointerException */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

/** ArrayList扩容
    默认初始容量 DEFAULT_CAPACITY = 10
     */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

/** *返回此列表中指定位置的元素。@要返回的元素的索引索引 @返回此列表中指定位置的元素、@throws IndexOutOfBoundsException {@inheritDoc} */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    /**
     用指定的元素替换此列表中指定位置的元素。@param要替换元素的索引index @param要存储在指定位置的元素 @返回先前在指定位置的元素 @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    /**
   将指定的元素追加到此列表的末尾。@要附加到此列表的参数元素 @返回 true （由{@link Collection＃add}指定）
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1); // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

/** {@code List}和{@code Deque}接口的双链列表实现。实现所有可选的列表操作，
并允许所有元素（包括{@code null}）。
所有操作均按双链接列表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，
以更接近指定索引的位置为准。
*/

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     指向第一个节点的指针
     * Invariant: (first == null && last == null) ||
     * (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     指向最后一个节点的指针
     * Invariant: (first == null && last == null) ||
     * (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     构造一个空List
     */
    public LinkedList() {
    }

    /**
   构造一个包含指定集合的元素的List，其顺序由集合的迭代器返回。
   @param c 要将其元素放入此List的集合
   如果指定的集合为null，则抛出NullPointerException
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    /** Node节点*/
      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;
        }
    }
}

/**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

/**
    返回此列表中指定位置的元素,要遍历，找到节点才能拿到元素
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

/**返回指定元素索引处的（非空）节点 */  
Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
  向量分量存储在其中的数组缓冲区。
  向量的容量是此数组缓冲区的长度，
  并且至少足够大以包含所有向量的元素。
  Vector中最后一个元素之后的所有数组元素均为null
     */
    protected Object[] elementData;
    /**
    此Vector对象中有效组件的数量
     * @serial
     */
    protected int elementCount;

    /**
   向量的容量在其大小大于其容量时自动增加的量。如果容量增量小于或等于零，
   则向量的容量每次需要增长时都会加倍。
     * @serial
     */
    protected int capacityIncrement;

    /** 使用JDK 1.0.2中的serialVersionUID来实现互操作性 */
    private static final long serialVersionUID = -2767605614048989439L;

    /**
     使用指定的初始容量和容量增量构造一个空向量。 @param initialCapacity向量的初始容量
     @param Capacity增大向量溢出时容量增加的数量
     如果指定的初始容量为负，则抛出IllegalArgumentException
     */
    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
    /**
   构造一个具有指定初始容量和*容量增量等于零的空向量。
   @param initialCapacity向量的初始容量
   @如果指定的initialCapacity为负，则抛出IllegalArgumentException
     */
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
    /**
    构造一个空向量，以便其内部数据数组的大小为 10，并且其标准容量增量为零
     */
    public Vector() {
        this(10);
    }
    /**
   构造一个向量，该向量包含指定集合的元素，
   并按集合的迭代器返回它们的顺序。
   @param c 将元素放置在此向量中的集合
   如果指定的集合为null，则抛出NullPointerException
     */
    public Vector(Collection<? extends E> c) {
        elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }

..........
public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        return elementData(index);
    }
    public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
............

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    /**
     构造一个新的空集
     支持的HashMap实例具有默认初始容量（16）和负载因子（0.75）
     */
    public HashSet() {
        map = new HashMap<>();
    }
    /**
   构造一个新集合，其中包含指定集合中的元素。 
  HashMap是使用默认负载因子（0.75）和足以容纳指定集合中的元素的初始容量创建的。 
   @param c 要将其元素放入此集合的集合
   如果指定的集合为null，则抛出NullPointerException
     */
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
    /**
   构造一个新的空链接哈希集（此包private构造函数仅由LinkedHashSet使用）
   支持 HashMap实例是具有指定的初始容量和指定的负载因子的LinkedHashMap。
   @param initialCapacity 哈希图的初始容量
   @param loadFactor 哈希图的负载因子
   @param dummy（将此构造函数与其他int，float构造函数区分开。
   @throws IllegalArgumentException如果初始容量为小于零，或者负载因子为非正
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

public boolean add(E e) {
        return map.put(e, PRESENT)==null; //map元素是不重复的 后面见到HashMap
    }

//如果此集合已经包含元素，则调用将使该集合保持不变 
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
------------------------------------------------------
    public V put(K key, V value) { // HashMap中的put方法
        return putVal(hash(key), key, value, false, true);
    }
   /** 首先会使用 hash() 函数生成一个 int 类型的 hashCode 散列值，然后与已经存储的元素的 hashCode 值作比较，如果 hashCode 值不相等，则所存储的两个对象一定不相等，此时把这个新元素存储在它的 hashCode 位置上；如果 hashCode 相等*/

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    private transient NavigableMap<E,Object> m;
    private static final Object PRESENT = new Object();
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    /**
   构造一个新的空树集，并根据其元素的自然顺序进行排序。
   插入到集合中的所有元素都必须实现{@link Comparable}接口
     */
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    /**
   构造一个新的空树集，并根据指定的比较器进行排序。
   插入到集合中的所有元素都必须由指定的比较器进行相互比较：
   {@code比较器.compare（e1，* e2）}
     */
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
    /**
   *构造一个新的树集，其中包含指定集合中的元素，并根据其元素的自然顺序进行排序。
   插入集合中的所有元素都必须实现{@link Comparable}接口。
   此外，所有此类元素必须可相互比较：
   @param c集合，其元素将组成新集合
     */
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

public interface Map<K,V> {
    // Query Operations
    /**
    返回此映射中的键值映射数
     */
    int size();
    /**
  如果此映射不包含键值映射，则返回true
     */
    boolean isEmpty();
    /**
    如果此映射包含指定*键的映射，则返回true
     */
    boolean containsKey(Object key);
    /**
    如果此映射将一个或多个键映射到指定值，则返回 true 
     */
    boolean containsValue(Object value);
    /**
    返回指定键所映射到的值
    如果此映射不包含该键的映射，则返回 null
     */
    V get(Object key);

    // Modification Operations
    /**
    将指定值与此映射中的指定键关联（可选操作）
    如果该映射先前包含键的映射，则旧值将替换为指定值
     */
    V put(K key, V value);
    /**
    从该映射中删除键的映射（如果存在）
     */
    V remove(Object key);

//是hashMap的最小容量16，容量就是数组的大小也就是变量，
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大数量，该数组最大值为2^31一次方。
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //默认的加载因子，如果构造的时候不传则为0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //一个位置里存放的节点转化成树的阈值，也就是8，比如数组里有一个node，这个 
      // node链表的长度达到该值才会转化为红黑树。
    static final int TREEIFY_THRESHOLD = 8;
    //当一个反树化的阈值，当这个node长度减少到该值就会从树转化成链表
    static final int UNTREEIFY_THRESHOLD = 6;
    //满足节点变成树的另一个条件，就是存放node的数组长度要达到64
    static final int MIN_TREEIFY_CAPACITY = 64;
    //具体存放数据的数组
    transient Node<K,V>[] table;
    //entrySet，一个存放k-v缓冲区
    transient Set<Map.Entry<K,V>> entrySet;
    //size是指hashMap中存放了多少个键值对
    transient int size;
    //对map的修改次数
    transient int modCount;
    //加载因子
    final float loadFactor;

//只有容量，initialCapacity
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) // 容量不能为负数
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //当容量大于2^31就取最大值1<<31; 
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //当前数组table的大小，一定是是2的幂次方
    // tableSizeFor保证了数组一定是是2的幂次方，是大于initialCapacity最结进的值。
    this.threshold = tableSizeFor(initialCapacity);
}

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
--------------------------------------------
 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        addEntry(hash, key, value, index);
        return null;
    }

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    /**
    哈希表数据
     */
    private transient Entry<?,?>[] table;
    /**
    哈希表中的条目总数
     */
    private transient int count;
    /**
   当表的大小超过此阈值时，表将被重新映射。 
   （此字段的值为（int）（capacity loadFactor）。
     */
    private int threshold;
    /**
    哈希表的加载因子
     */
    private float loadFactor; 
    /**
    此哈希表经过结构修改的次数
     */
    private transient int modCount = 0;
    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1421746759512286392L;
    /**
    *使用指定的初始容量和指定的负载因子构造一个新的空哈希表
     */
    public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    /**
   使用指定的初始容量和默认的加载因子（0.75）构造一个新的空哈希表
     */
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
    /**
    构造一个新的空哈希表，其默认初始容量（11）*和负载因子（0.75）
     */
    public Hashtable() {
        this(11, 0.75f);
    }

    /**
    *构造一个新的哈希表，该哈希表具有与给定 Map相同的映射。
    创建哈希表时，其初始容量应足以将给定Map中的映射保存并具有默认的加载因子（0.75）
     */
    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        addEntry(hash, key, value, index);
        return null;
    }

static class Segment<K,V> extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        final float loadFactor;
        Segment(float lf) { this.loadFactor = lf; }
    }