Java集合（一）

目录

Java集合（一）

集合介绍

单列集合分类

Collection接口

创建Collection实现类对象

常用方法

迭代器

基本使用

迭代器的执行过程

迭代器底层原理

集合中的并发修改异常及原因分析

List接口

ArrayList类

介绍

常用方法

遍历集合

ArrayList底层源码分析

初始容量

数组扩容

LinkedList类

介绍

常用方法

遍历集合

LinkedList底层源码分析

LinkedList成员分析

LinkedList中add方法源码分析

LinkedList中get方法源码分析

增强for循环

Java集合（一）

集合介绍

在前面已经使用了一个最基本的数据结构：数组，但是数组的缺点很明显：定长，这个缺点导致数组的增删不够方便，为了解决这个问题，可以使用Java的相关集合

Java集合分为两种：

1. 单列集合：集合中每一个元素只有一种元素类型
2. 多列集合：集合中每一个元素包括两种数据类型，第一个数据类型对应的元素被称为key，第二个数据类型对应的元素被称为value，二者组成的共同体被称为键值对

Java集合有以下三个特点：

1. 只能存储引用数据类型的数据，而不能存储基本数据类型的数据
2. 每一种集合长度均是可变的
3. 集合中有很多使用的方法，便于调用

单列集合分类

在Java中，单列集合最大的接口是Collection接口，该接口下有两个子接口，分别是list接口和set接口

对于list接口来说，一共有三个实现类：

1. ArrayList类
2. LinkedList类
3. Vector类（现不常用）

三个实现类都具有以下特点：

1. 元素存储顺序与插入顺序一致
2. 集合中元素可重复
3. 可以使用索引方式操作

三个实现类中，ArrayList类和Vector类底层的数据结构是数组，LinkedList类底层的数据结构是不带头双向不循环链表，并且只有Vector类是线程安全的类，但是Vector类的效率低

对于set接口来说，一共有三个实现类：

1. HashSet类
2. LinkedHashSet类
3. TreeSet类

三个实现类都具有以下特点：

1. 不可以添加重复的数据，即元素唯一
2. 不可以使用索引方式操作
3. 线程不安全

三个实现类中，HashSet类底层数据结构是哈希表，LinkedHashSet类底层数据结构是哈希表+双向链表，TreeSet类底层数据结构是红黑树，并且对于HashSet来说，其插入的数据在结构中的顺序与插入时的顺序不一定相同，对于LinkedHashSet类来说，插入的数据在结构中的顺序与插入时的顺序相同，对于TreeSet类来说，因为红黑树会按照一定比较方式对插入顺序进行排序，所以数据在结构中都是在一定规则下有序的

总结如下图所示：

Collection接口

创建Collection实现类对象

Collection接口是单列集合的顶级接口，创建对象时使用对应的实现类创建，但是可以使用Collection接口的引用接收，即多态，基本格式如下：

Collection<E> 对象名 = new 实现类对象<E>()

其中 <E>表示泛型，Java中的泛型只可以写引用数据类型，所以导致集合只能存储引用数据类型的数据

使用泛型时，赋值符号左侧的部分必须写具体类型，但是赋值符号右侧的部分可以省略，JVM会自动根据左侧泛型的具体类型推导右侧部分

常用方法

注意，下面的方法本质使用的还是实现类中重写的方法

1. boolean add(E e)：向集合中插入元素，返回值表示插入成功（true）或者失败（false），一般情况下可以不用接收
2. boolean addAll(Collection<? extends E> c)：将另一个集合元素添加到当前集合中（相当于集合的合并）
3. void clear()：清除当前集合中所有的元素
4. boolean contains(Object o)：查找对应集合中是否含有指定元素，存在返回true，否则返回false
5. boolean isEmpty()：判断集合是否为空，为空返回true，否则返回false
6. boolean remove(Object o)：从当前集合中移除指定元素，返回值代表删除成功或者失败
7. int size()：返回集合中的元素个数
8. Object[] toArray()：将集合中的数据存储到数组中

基本使用如下：

public class Test {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        //boolean add(E e)
        collection.add("萧炎");
        collection.add("萧薰儿");
        collection.add("彩鳞");
        collection.add("小医仙");
        collection.add("云韵");
        collection.add("涛哥");
        System.out.println(collection);
        //boolean addAll(Collection<? extends E> c)
        Collection<String> collection1 = new ArrayList<>();
        collection1.add("张无忌");
        collection1.add("小昭");
        collection1.add("赵敏");
        collection1.add("周芷若");
        collection1.addAll(collection);
        System.out.println(collection1);

        //void clear()
        collection1.clear();
        System.out.println(collection1);
        //boolean contains(Object o)
        boolean result01 = collection.contains("涛哥");
        System.out.println("result01 = " + result01);
        //boolean isEmpty()
        System.out.println(collection1.isEmpty());
        //boolean remove(Object o)
        collection.remove("涛哥");
        System.out.println(collection);
        //int size() ：返回集合中的元素个数。
        System.out.println(collection.size());
        //Object[] toArray()
        Object[] arr = collection.toArray();
        System.out.println(Arrays.toString(arr));
    }
}

迭代器

基本使用

当需要遍历一个集合时，最常用的就是迭代器，在Java中，迭代器是Iterator<E>接口，获取当前集合的迭代器可以使用Collection中的方法：

Iterator<E> iterator()

常用的方法有两种：

1. boolean hasNext()：判断集合中的下一个元素是否存在
2. E next()：获取下一个元素，其中E由创建集合时的数据类型决定

基本使用如下：

public class Test01 {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();

        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");

        // 使用迭代器遍历
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            // 存在下一个元素就更新
            String next = iterator.next();
            System.out.println(next);
        }
    }
}

需要注意，尽量不要在遍历过程中使用多次next()方法，不同情况下可能结果不一样，当next()方法没有访问到指定的数据，此时就会抛出异常：NoSuchElementException

迭代器的执行过程

以前面的代码为例，当前size为4：

当执行hasNext方法时，对应的源码如下：

public boolean hasNext() {
    return cursor != size;
}

int cursor; // 下一个元素的下标
int lastRet = 1; // 上一个元素的下标

满足条件进入循环，执行next方法，对应源码如下：

public E next() {
    // ...
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();

    Object[] elementData = ArrayList.this.elementData;

    if (i >= elementData.length)
        throw new ConcurrentModificationException();

    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

因为cursor既不大于size，也不大于新建数组elementData的长度，所以两个分支语句均不执行

因为 ArrayList实现的 Iterator是一个 Iterator<E>的内部实现类，所以访问 ArrayList中的 elementData成员相当于内部类访问外部类的成员，而 ArrayList中的 elementData数组存储的是当前集合中的数据，因为 ArrayList底层是数组，所以直接将对应的 elementData的地址给新数组引用即可实现数组数据共享

接下来，cursor=i+1使cursor走到下一个元素的位置，因为前面已经判断cursor!=size表示一定存在下一个元素，所以此处不会出现越界问题，接着返回elementData数组中的元素，但是因为新数组引用是Object类型，所以此处需要进行强制类型转换，以确保返回的数据类型与泛型对应的数据类型一致

此处返回的 elementData数组元素下标使用到了赋值符号的返回值，赋值符号的返回值为赋值符号左侧变量的值，因为取下标需要先计算内部 lastRet=i表达式，所以此处既让 lastRet向后移动，又拿到了 lastRet向后移动对应位置的值

所以本过程运行结果如下图：

其余情况以此类推，直到cursor!=size返回false，代表已经没有下一个元素，循环结束

迭代器底层原理

在获取迭代器时，调用到了对应集合的成员方法，例如前面ArrayList获取其迭代器对象时使用的代码：

Iterator<String> iterator = list.iterator();

对应的源码如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 返回迭代器对象
    public Iterator<E> iterator() {
        return new Itr();
    }
    // ...
    private class Itr implements Iterator<E> {
            int cursor;       // index of next element to return
            int lastRet = 1; // index of last element returned; 1 if no such
            int expectedModCount = modCount;
    
            Itr() {}
            // ...
    }
    
    // ...
}

实际上获取到的迭代器就是Collection<E>实现类的ArrayList类中内部实现Iterator<E>的对象

需要注意，并不是所有的集合都是new Itr()，例如HashSet的源码

// HashSet中
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

// HashMap中
public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

final class KeySet extends AbstractSet<K> {
        // ...
        public final Iterator<K> iterator()     { return new KeyIterator(); }
        // ...
}

在HashSet中，iterator()方法返回的是HashMap中的内部类KeySet中的迭代器

集合中的并发修改异常及原因分析

并发修改异常出现于使用迭代器遍历集合的过程中修改集合中的内容，例如下面的代码：

以 ArrayList为例，其余集合类似

public class Test02 {
    public static void main(String[] args) {
        //需求：定义一个集合,存储 唐僧,孙悟空,猪八戒,沙僧,遍历集合,如果遍历到猪八戒,往集合中添加一个白龙马
        ArrayList<String> list = new ArrayList<>();
        list.add("唐僧");
        list.add("孙悟空");
        list.add("猪八戒");
        list.add("沙僧");

        Iterator<String> iterator = list.iterator();
        while(iterator.hasNext()){
            String element = iterator.next();
            // 使用迭代器遍历过程中修改集合中的内容
            if ("猪八戒".equals(element)){
                list.add("白龙马");
            }
        }
        System.out.println(list);
    }
}

报错信息：

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java：911)
    at java.util.ArrayList$Itr.next(ArrayList.java：861)
    at com.epsda.advanced.test_Collection.Test02.main(Test02.java：24)

查看源码分析出现这个异常的原因：

public E next() {
    checkForComodification();
    // ...
}

// 迭代器内部类
int expectedModCount = modCount;

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

在执行next方法时，第一行先调用checkForComodification()方法，该方法用于检测modCount和expectedModCount是否一致，其作用是在多线程环境下检测集合是否被其他线程修改过。而在对应的add函数中，代码如下：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflowconscious code
    if (minCapacity  elementData.length > 0)
        grow(minCapacity);
}

如果在使用迭代器遍历时修改集合元素就会因为迭代器对象已经创建完毕，而此时的expectedModCount与modCount初始值相等，因为每一次添加数据都会导致modCount改变，导致此时的modCount和expectedCount不对应，从而在checkForComodification()方法中抛出异常，具体流程如下：

总结：不要在使用迭代器遍历集合的同时修改集合中的内容

List接口

根据前面的单列集合图可以看出，List接口是Collection接口的子接口，常见的实现类一共有三种：

1. ArrayList类
2. LinkedList类
3. Vector类（现不常用）

ArrayList类

介绍

ArrayList类是List接口的实现类，其特点如下：

1. 存储顺序与插入顺序相同
2. 元素可重复
3. 可以使用索引方式操作
4. 线程不安全
5. 底层数据结构是数组（可扩容）

常用方法

1. boolean add(E e)：向集合尾部插入元素，返回值表示插入成功（true）或者失败（false），一般情况下可以不用接收
2. void add(int index, E element)：在指定位置添加元素，如果指定位置有元素，则在该元素前插入元素
3. boolean remove(Object o)：从当前集合中移除指定元素，返回值代表删除成功或者失败
4. E remove(int index)：根据索引删除元素，返回被删除的元素
5. E set(int index, E element)：修改指定索引的元素，返回被修改的元素
6. E set(int index)：根据索引获取元素
7. int size()：返回集合中的元素个数

基本使用如下：

public class Test03 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        //boolean add(E e)
        list.add("铁胆火车侠");
        list.add("喜洋洋");
        list.add("火影忍者");
        list.add("灌篮高手");
        list.add("网球王子");
        System.out.println(list);
        //void add(int index, E element)
        list.add(2,"猪猪侠");
        System.out.println(list);
        //boolean remove(Object o)
        list.remove("猪猪侠");
        System.out.println(list);
        //E remove(int index)
        String element = list.remove(0);
        System.out.println(element);
        System.out.println(list);
        //E set(int index, E element)
        String element2 = list.set(0, "金莲");
        System.out.println(element2);
        System.out.println(list);
        //E get(int index)
        System.out.println(list.get(0));
        //int size()
        System.out.println(list.size());
    }
}

遍历集合

既可以使用迭代器遍历集合，也可以使用for循环+下标遍历，例如下面的代码：

public class Test03 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("铁胆火车侠");
        list.add("喜洋洋");
        list.add("火影忍者");
        list.add("灌篮高手");
        list.add("网球王子");

        // 迭代器遍历集合
        Iterator<String> iterator = list.iterator();
        while(iterator.hasNext()) {
            String next = iterator.next();
            System.out.println(next);
        }

        // for循环+下标遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

ArrayList底层源码分析

初始容量

实际上ArrayList还有一种构造方法：ArrayList(int initialCapacity)，根据给定的数值初始化ArrayList的容量

如果使用空参构造，则默认情况下ArrayList的容量为10，但是需要注意，ArrayList在使用无参构造并且之后不添加任何元素时，其初始容量依旧是0，只有在第一次添加数据时才会开辟容量为10的空间，源码如下：

// 默认容量为0的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// ArrayList的数据结构
transient Object[] elementData;
// 无参构造方法开始时直接使用空数组构造
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

第一次调用add方法时：

// 默认容量
private static final int DEFAULT_CAPACITY = 10;

// add方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// 确保内部数组容量方法
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 修改内部数组大小
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflowconscious code
    if (minCapacity  elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflowconscious 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);
}

因为此时底层数组的容量大小为0，所以在calculateCapacity方法中进入分支语句，此时判断默认容量大小成员DEFAULT_CAPACITY和minCapacity哪一个大，而minCapacity在add方法中是size成员加1的结果，此时因为数组长度为0，所以size也为0，所以minCapacity此时就是1，很明显DEFAULT_CAPACITY和minCapacity，DEFAULT_CAPACITY会更大，所以calculateCapacity方法返回DEFAULT_CAPACITY给ensureExplicitCapacity方法，在该方法中的分支语句判断时，因为minCapacity为1，elementData.length为0，所以此时需要扩容，进入grow方法，传递minCapacity，在grow方法中，oldCapacity为0，newCapacity此时也为0，所以newCapacityminCapacity（此时是DEFAULT_CAPACITY）满足小于0的条件，newCapacity就被更新为DEFAULT_CAPACITY的值，开辟空间后拷贝原数组的数据即可

综上所述：使用ArrayList的无参构造时，默认情况下不会开辟一个容量为10的数组，只有在第一次添加数据时，该数组容量才会变为10

数组扩容

private void grow(int minCapacity) {
    // overflowconscious 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);
}

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        ： (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

从这个源码可以看出，当newCapacity大于minCapacity时，两个分支if都不会执行，并且扩容大小为原数组大小的1.5倍，传递newCapacity和当前数组，调用copyOf方法，进入该方法后底层调用系统数组拷贝方法arraycopy，在拷贝时，使用了min方法控制是否要改变数组长度，将原数组的数据拷贝到新数组中，再改变成员elementData的指向，但是不论是否原数组长度小于新长度还是其他情况，都会对原数据进行拷贝

需要注意，尽管在某些情况下不需要扩容，但为了简化代码逻辑和保证数据一致性，通常会统一处理，即总是创建一个新数组并拷贝原有内容。这样做虽然在某些场景下可能有些许性能开销，但在整体上更加安全可靠。

LinkedList类

介绍

LinkedList类是List接口的实现类，其特点如下：

1. 存储顺序与插入顺序相同
2. 元素可重复
3. 可以使用索引方式操作
4. 线程不安全
5. 底层数据结构是不带头双向不循环链表

常用方法

1. public void addFirst(E e)：将指定元素插入此列表的开头
2. public void addLast(E e)：将指定元素添加到此列表的结尾
3. public E getFirst()：返回此列表的第一个元素
4. public E getLast()：返回此列表的最后一个元素
5. public E get(int index)：获取索引位置的元素
6. public E removeFirst()：移除并返回此列表的第一个元素，返回被删除的元素
7. public E removeLast()：移除并返回此列表的最后一个元素，返回被删除的元素
8. public boolean isEmpty()：如果列表没有元素，则返回true，否则返回false

基本使用如下：

public class Test05 {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("吕布");
        linkedList.add("刘备");
        linkedList.add("关羽");
        linkedList.add("张飞");
        linkedList.add("貂蝉");
        System.out.println(linkedList);

        linkedList.addFirst("孙尚香");
        System.out.println(linkedList);

        linkedList.addLast("董卓");
        System.out.println(linkedList);

        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());

        linkedList.removeFirst();
        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);
    }
}

需要注意两个比较特殊的方法

1. public E pop()：删除链表头数据，返回被删除的元素
2. public void push(E e)：在链表头插入数据

public class Test06 {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("吕布");
        linkedList.add("刘备");
        linkedList.add("关羽");
        linkedList.add("张飞");
        linkedList.add("貂蝉");

        linkedList.pop();
        System.out.println(linkedList);
        linkedList.push("孙尚香");
        System.out.println(linkedList);
    }
}

遍历集合

与ArrayList一样，可以使用迭代器，也可以使用for循环+下标

需要注意，默认情况下 LinkedList不支持下标访问，因为链表没有下标的概念，但是因为 LinkedList提供了类似于下标访问的方法，所以可以使用下标

public class Test06 {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("吕布");
        linkedList.add("刘备");
        linkedList.add("关羽");
        linkedList.add("张飞");
        linkedList.add("貂蝉");

        // 迭代器遍历
        Iterator<String> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            System.out.println(next);
        }

        // for循环+下标
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
    }
}

LinkedList底层源码分析

LinkedList成员分析

对于LinkedList来说：

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

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    // ...
}

对于其中的Node<E>类型（LinkedList的内部类）来说：

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

下图是一种情况，对于每一个成员的作用进行解释：

LinkedList中add方法源码分析

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++;
    modCount++;
}

调用add方法，相当于调用linkLast方法，当last节点为空节点时，说明当前不存在任何一个节点，此时将头结点指向新插入的节点，否则让最后一个节点的next引用新插入的节点

LinkedList中get方法源码分析

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

对于LinkedList中的get方法，采用了一种二分的思想，但不完全是二分查找算法的思想，其基本思想是将链表的长度切一半，如果查找的下标小于链表大小的一半，说明需要在前一半中顺序遍历查找，否则在后一半中顺序遍历查找

增强for循环

增强for循环对于集合来说，本质是使用到了迭代器，而对于数组来说，本质是数组的下标遍历

使用格式如下：

for(集合/数组元素的类型 存储元素的变量名 : 集合/数组名) {
    // 遍历操作
}

基本使用如下：

public class Test07 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("张三");
        list.add("李四");
        list.add("王五");
        list.add("赵六");
        for (String s : list) {
            System.out.println(s);
        }

        System.out.println("=====================");

        int[] arr = {1,2,3,4,5};
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

反编译查看底层：