Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。本文将详细介绍这些接口及其实现类，并通过源码解读和实例来帮助你更好地理解它们。

Collection 接口

Collection 是 Java 集合框架的根接口，抽象了集合对象的基本操作。常用的方法有：

• add(E e)：添加元素到集合中。
• remove(Object o)：从集合中移除指定元素。
• size()：返回集合中元素的数量。
• contains(Object o)：判断集合中是否包含指定元素。
• iterator()：返回集合的迭代器。

java

public interface Collection<E> extends Iterable<E> {    boolean add(E e);    boolean remove(Object o);    int size();    boolean contains(Object o);    Iterator<E> iterator();    // 其他方法省略}

List 接口

List 接口继承自 Collection 接口，表示一个有序的元素集合。常用的实现类有 ArrayList、LinkedList、Vector 和 Stack。

java

public interface List<E> extends Collection<E> {    void add(int index, E element);    E get(int index);    E remove(int index);    int indexOf(Object o);    // 其他方法省略}

ArrayList

ArrayList 是基于动态数组实现的 List，支持快速随机访问。它的内部实现是一个数组，当数组容量不足时，自动扩容为原来的1.5倍。

java

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {    private transient Object[] elementData; // 存放元素的数组    private int size; // 元素数量        public ArrayList() {        this.elementData = new Object[10]; // 默认初始容量为10    }    public boolean add(E e) {        ensureCapacity(size + 1); // 检查容量        elementData[size++] = e;        return true;    }    private void ensureCapacity(int minCapacity) {        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }    private void grow(int minCapacity) {        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为1.5倍        if (newCapacity - minCapacity < 0)            newCapacity = minCapacity;        elementData = Arrays.copyOf(elementData, newCapacity);    }    public E get(int index) {        rangeCheck(index);        return elementData(index);    }    private void rangeCheck(int index) {        if (index >= size)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }        // 其他方法省略}

LinkedList

LinkedList 是基于双向链表实现的 List，适合频繁的插入和删除操作。

java

public class LinkedList<E> extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {        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;        }    }        private transient Node<E> first;    private transient Node<E> last;    private int size;        public LinkedList() {    }        public boolean add(E e) {        linkLast(e);        return true;    }    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++;    }        public E get(int index) {        checkElementIndex(index);        return node(index).item;    }        Node<E> node(int 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;        }    }        private void checkElementIndex(int index) {        if (!isElementIndex(index))            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }    private boolean isElementIndex(int index) {        return index >= 0 && index < size;    }        // 其他方法省略}

Set 接口

Set 接口继承自 Collection 接口，表示一个不包含重复元素的集合。常用的实现类有 HashSet、LinkedHashSet 和 TreeSet。

java

public interface Set<E> extends Collection<E> {    // 继承了 Collection 的所有方法}

HashSet

HashSet 是基于哈希表实现的 Set，不保证元素的顺序。

java

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {    private transient HashMap<E, Object> map;    // Dummy value to associate with an Object in the backing Map    private static final Object PRESENT = new Object();    public HashSet() {        map = new HashMap<>();    }    public boolean add(E e) {        return map.put(e, PRESENT) == null;    }    public boolean contains(Object o) {        return map.containsKey(o);    }    public boolean remove(Object o) {        return map.remove(o) == PRESENT;    }    public int size() {        return map.size();    }        // 其他方法省略}

Queue 接口

Queue 接口继承自 Collection 接口，表示一个先进先出的队列。常用的实现类有 LinkedList 和 PriorityQueue。

java

public interface Queue<E> extends Collection<E> {    boolean offer(E e);    E poll();    E peek();    // 其他方法省略}

PriorityQueue

PriorityQueue 是一个基于优先级堆实现的队列，元素按优先级顺序进行排序。

java

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {    private transient Object[] queue;    private int size;    private final Comparator<? super E> comparator;    public PriorityQueue() {        this.queue = new Object[11];        this.comparator = null;    }    public boolean offer(E e) {        if (e == null)            throw new NullPointerException();        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;    }    private void siftUp(int k, E x) {        if (comparator != null)            siftUpUsingComparator(k, x);        else            siftUpComparable(k, x);    }    private void siftUpComparable(int k, E x) {        Comparable<? super E> key = (Comparable<? super E>) x;        while (k > 0) {            int parent = (k - 1) >>> 1;            Object e = queue[parent];            if (key.compareTo((E) e) >= 0)                break;            queue[k] = e;            k = parent;        }        queue[k] = key;    }    private void grow(int minCapacity) {        int oldCapacity = queue.length;        int newCapacity = oldCapacity + (oldCapacity >> 1);        if (newCapacity - minCapacity < 0)            newCapacity = minCapacity;        queue = Arrays.copyOf(queue, newCapacity);    }    public E poll() {        if (size == 0)            return null;        int s = --size;        E result = (E) queue[0];        E x = (E) queue[s];        queue[s] = null;        if (s != 0)            siftDown(0, x);        return result;    }    private void siftDown(int k, E x) {        if (comparator != null)            siftDownUsingComparator(k, x);        else            siftDownComparable(k, x);    }    private void siftDownComparable(int k, E x) {        Comparable<? super E> key = (Comparable<? super E>) x;        int half = size >>> 1;        while (k < half) {            int child = (k << 1) + 1;            Object c = queue[child];            int right = child + 1;            if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)                c = queue[child = right];            if (key.compareTo((E) c) <= 0)                break;            queue[k] = c;            k = child;        }        queue[k] = key;    }        public E peek() {        return (size == 0) ? null : (E) queue[0];    }        // 其他方法省略}

Map 接口

Map 接口表示一个键值对集合，每个键最多只能映射到一个值。常用的实现类有 HashMap、LinkedHashMap 和 TreeMap。

java

public interface Map<K, V> {    V put(K key, V value);    V get(Object key);    V remove(Object key);    boolean containsKey(Object key);    int size();    Set<K> keySet();    Collection<V> values();    // 其他方法省略}

HashMap

HashMap 是基于哈希表实现的 Map，允许使用 null 键和 null 值，不保证元素的顺序。

java

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {    static final int DEFAULT_INITIAL_CAPACITY = 16;    static final float DEFAULT_LOAD_FACTOR = 0.75f;    transient Node<K, V>[] table;    transient int size;    int threshold;    final float loadFactor;    static class Node<K, V> implements Map.Entry<K, V> {        final int hash;        final K key;        V value;        Node<K, V> next;        Node(int hash, K key, V value, Node<K, V> next) {            this.hash = hash;            this.key = key;            this.value = value;            this.next = next;        }        public final K getKey()        { return key; }        public final V getValue()      { return value; }        public final String toString() { return key + "=" + value; }    }    public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        this.loadFactor = loadFactor;        this.threshold = tableSizeFor(initialCapacity);    }    public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);    }    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node<K, V>[] tab; Node<K, V> p; int n, i;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        else {            Node<K, V> e; K k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                e = ((TreeNode<K, V>)p).putTreeVal(this, tab, hash, key, value);            else {                for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        if (binCount >= TREEIFY_THRESHOLD - 1)                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            if (e != null) {                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;        if (++size > threshold)            resize();        afterNodeInsertion(evict);        return null;    }    static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }    final Node<K, V>[] resize() {        Node<K, V>[] oldTab = table;        int oldCap = (oldTab == null) ? 0 : oldTab.length;        int oldThr = threshold;        int newCap, newThr = 0;        if (oldCap > 0) {            if (oldCap >= MAXIMUM_CAPACITY) {                threshold = Integer.MAX_VALUE;                return oldTab;            }            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)                newThr = oldThr << 1;        }        else if (oldThr > 0)            newCap = oldThr;        else {            newCap = DEFAULT_INITIAL_CAPACITY;            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }        if (newThr == 0) {            float ft = (float)newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                      (int)ft : Integer.MAX_VALUE);        }        threshold = newThr;        @SuppressWarnings({"rawtypes","unchecked"})            Node<K, V>[] newTab = (Node<K, V>[])new Node[newCap];        table = newTab;        if (oldTab != null) {            for (int j = 0; j < oldCap; ++j) {                Node<K, V> e;                if ((e = oldTab[j]) != null) {                    oldTab[j] = null;                    if (e.next == null)                        newTab[e.hash & (newCap - 1)] = e;                    else if (e instanceof TreeNode)                        ((TreeNode<K, V>)e).split(this, newTab, j, oldCap);                    else {                        Node<K, V> loHead = null, loTail = null;                        Node<K, V> hiHead = null, hiTail = null;                        Node<K, V> next;                        do {                            next = e.next;                            if ((e.hash & oldCap) == 0) {                                if (loTail == null)                                    loHead = e;                                else                                    loTail.next = e;                                loTail = e;                            }                            else {                                if (hiTail == null)                                    hiHead = e;                                else                                    hiTail.next = e;                                hiTail = e;                            }                        } while ((e = next) != null);                        if (loTail != null) {                            loTail.next = null;                            newTab[j] = loHead;                        }                        if (hiTail != null) {                            hiTail.next = null;                            newTab[j + oldCap] = hiHead;                        }                    }                }            }        }        return newTab;    }    final Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {        return new Node<>(hash, key, value, next);    }        // 其他方法省略}

Java 集合框架提供了丰富的数据结构和算法，能够满足各种常见的编程需求。在实际开发中，选择合适的集合类型可以显著提高程序的性能和可读性。

​