Java集合¶

约 5668 个字 960 行代码 7 张图片预计阅读时间 31 分钟

集合介绍¶

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

Java集合分为两种：

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

Java集合有以下三个特点：

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

单列集合分类¶

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

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

ArrayList类
LinkedList类
Vector类（现不常用）

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

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

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

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

HashSet类
LinkedHashSet类
TreeSet类

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

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

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

总结如下图所示：

`Collection`接口¶

创建`Collection`实现类对象¶

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

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

Note

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

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

常用方法¶

Note

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

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

基本使用如下：

Java
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中的方法：

Java
Iterator<E> iterator()

常用的方法有两种：

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

基本使用如下：

Java
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方法时，对应的源码如下：

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

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

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

Java
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的长度，所以两个分支语句均不执行

Note

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

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

Note

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

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

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

迭代器底层原理¶

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

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

对应的源码如下：

Java
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的源码

Java
// 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中的迭代器

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

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

Note

以ArrayList为例，其余集合类似

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

报错信息：

Java
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)

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

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

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

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

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

Java
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接口的子接口，常见的实现类一共有三种：

ArrayList类
LinkedList类
Vector类（现不常用）

`ArrayList`类¶

介绍¶

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

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

常用方法¶

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

基本使用如下：

Java
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循环+下标遍历，例如下面的代码：

Java
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的空间，源码如下：

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

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

第一次调用add方法时：

Java
// 默认容量
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

数组扩容¶

Java
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的指向，但是不论是否原数组长度小于新长度还是其他情况，都会对原数据进行拷贝

Note

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

`LinkedList`类¶

介绍¶

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

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

常用方法¶

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

基本使用如下：

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

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

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

Java
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循环+下标

Note

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

Java
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来说：

Java
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的内部类）来说：

Java
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`方法源码分析¶

Java
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`方法源码分析¶

Java
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循环对于集合来说，本质是使用到了迭代器，而对于数组来说，本质是数组的下标遍历

使用格式如下：

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

基本使用如下：

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

反编译查看底层：

`Collections`集合工具类¶

不同于Collection，Collections是一个工具类，所以其构造方法为私有方法，成员方法为静态

常用方法：

static <T> boolean addAll(Collection<? super T> c, T... elements)：批量向指定集合添加数据，第二个参数为一个可变参数列表，表示可以一次性添加多个元素
static void shuffle(List<?> list)：随机打乱单列集合中的元素（每一次运行结果都不一样）
static <T> void sort(List<T> list)：使用单列集合中的泛型实现的Comparable接口中的方法对集合中的数据进行排序。如果泛型对应的类没有实现Comparable接口，则编译报错
static <T> void sort(List<T> list, Comparator<? super T> c)：使用自定义实现Comparator接口中的方法对指定集合中的数据进行排序

基本使用如下：

Java
public class Test {
    public static void main(String[] args) {
        ArrayList<String> strings = new ArrayList<>();

        // 1. static <T> boolean addAll(Collection<? super T> c, T... elements)
        Collections.addAll(strings,"abc","sac","bsd");
        for (String string : strings) {
            System.out.println(string);
        }
        System.out.println();

        // 2. static void shuffle(List<?> list)
        Collections.shuffle(strings);
        for (String string : strings) {
            System.out.println(string);
        }
        System.out.println();

        // 3. static <T> void sort(List<T> list)
        Collections.sort(strings); // String 实现了 Comparable接口
        for (String string : strings) {
            System.out.println(string);
        }
        System.out.println();

        // 4. static <T> void sort(List<T> list, Comparator<? super T> c)
        ArrayList<Person> people = new ArrayList<>();
        people.add(new Person(23,"张三"));
        people.add(new Person(12,"李四"));
        people.add(new Person(45,"王五"));
        Collections.sort(people, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                return o1.getAge() - o2.getAge();
            }
        });

        for (Person person : people) {
            System.out.println(person);
        }
    }
}

泛型¶

泛型介绍¶

泛型：不明确具体类型，直到接收到具体类型再进行推导

使用泛型有两个原因：

统一数据类型，防止使用时出现的数据类型转换异常
定义带泛型的类，方法等，使用的时候给泛型确定什么类型，泛型就会自动推导为对应类型，使代码更灵活

定义泛型¶

定义泛型一共有三个位置：

定义泛型的类：在类名后面添加<T>，其中<>表示泛型，T为泛型名，类似于变量名，对于类泛型来说，当该类实例化出对象时，泛型就会被替代为指定类型，格式如下：

Java
public class 类名 <T> {
    // 成员
}

基本使用如下：

Java
public class MyArrayList <E> {
    //定义一个数组，充当ArrayList底层的数组,长度直接规定为10
    Object[] obj = new Object[10];
    //定义size,代表集合元素个数
    int size;

    /**
    * 定义一个add方法，参数类型需要和泛型类型保持一致
    *
    * 数据类型为E  变量名随便取
    */
    public boolean add(E e) {
        obj[size] = e;
        size++;
        return true;
    }

    /**
    * 定义一个get方法,根据索引获取元素
    */
    public E get(int index) {
        return (E) obj[index];
    }

    @Override
    public String toString() {
        return Arrays.toString(obj);
    }
}

// 测试
public class Test {
    public static void main(String[] args) {
        MyArrayList<String> list1 = new MyArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        System.out.println(list1); //直接输出对象名,默认调用toString

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

        MyArrayList<Integer> list2 = new MyArrayList<>();
        list2.add(1);
        list2.add(2);
        Integer element = list2.get(0);
        System.out.println(element);
        System.out.println(list2);
    }
}

需要注意，之所以定义元素Object类型的数组是为了便于做强制类型转换，因为泛型不是具体类型，对于get方法来说，当泛型作为一个方法的返回值时，返回值需要进行强制转换，此时因为Object是所有类的父类，所以此时可以强制转换，例如源码迭代器中的next方法返回值

Java
public E next() {
    // ...
    return (E) elementData[lastRet = i];
}

定义泛型方法：泛型方法在方法被调用时泛型被推导为具体类型。基本格式如下：

Java
权限修饰符 其他修饰符 <T> 方法返回值 方法名(泛型形参列表) {
    // 方法体
}

基本使用如下：

Java
public class ListUtils {
    //定义一个静态方法addAll,添加多个集合的元素
    public static <E> void addAll(ArrayList<E> list,E...e){
        for (E element : e) {
            list.add(element);
        }
    }

}

// 测试
public class Test01 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        ListUtils.addAll(list1,"a","b","c");
        // 也可以写成如下形式
        // ListUtils.<String>addAll(list1,"a","b","c");
        System.out.println(list1);

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

        ArrayList<Integer> list2 = new ArrayList<>();
        ListUtils.addAll(list2,1,2,3,4,5);
        System.out.println(list2);
    }
}

定义泛型接口：泛型接口在实现类实例化对象时或者实现类本身指定了具体类型，泛型才会被推导为具体类型。基本格式如下，与定义泛型类基本一致：

Java
public interface 接口名 <T> {
    // 成员
}

基本使用如下：

实现类实例化对象时确定类型

Java
// 泛型接口
public interface MyList <E> {
    public boolean add(E e);
}

// 接口实现类
public class MyArrayList1<E> implements MyList<E> {
    //定义一个数组,充当ArrayList底层的数组,长度直接规定为10
    Object[] obj = new Object[10];
    //定义size,代表集合元素个数
    int size;

    /**
    * 定义一个add方法,参数类型需要和泛型类型保持一致
    *
    * 数据类型为E  变量名随便取
    */
    public boolean add(E e) {
        obj[size] = e;
        size++;
        return true;
    }

    /**
    * 定义一个get方法,根据索引获取元素
    */
    public E get(int index) {
        return (E) obj[index];
    }

    @Override
    public String toString() {
        return Arrays.toString(obj);
    }
}

// 测试
public class Test02 {
    public static void main(String[] args) {
        MyArrayList1<String> list1 = new MyArrayList1<>();
        list1.add("张三");
        list1.add("李四");
        System.out.println(list1.get(0));

    }
}

实现类已经指定了具体的类型

Java
// 接口
public interface MyIterator <E> {
    E next();
}

// 实现类指定了具体类型为String
public class MyScanner implements MyIterator<String> {
    @Override
    public String next() {
        return "实现类指定具体类型时推导泛型";
    }
}

// 测试
public class Test03 {
    public static void main(String[] args) {
        MyScanner myScanner = new MyScanner();
        String result = myScanner.next();
        System.out.println("result = " + result);
    }
}

类型限定符¶

在Java中，可以通过两个关键字限制方法或类时传递给泛型的类型

extends：限制传递给模版的具体类型为extends后的本类或者子类类型，基本语法如下：

Java
模版参数类型 extends 具体类型

// 例如
// 类
public class Test04 <T extends String>{
}

// 方法
public <T extends String> void test(T t) {
    System.out.println(t);
}

super：限制传递给模版的具体类型为super后的本类或者父类类型
Java
1 2 3
模版参数类型 super 具体类型 // 使用方式同extends

泛型通配符¶

如果需要确保传递给泛型的具体类型为任意引用数据类型，可以在<>中使用?占位，表示泛型通配符，例如：

Java
public class Test05 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("张三");
        list1.add("李四");

        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(1);
        list2.add(2);

        method(list1);
        method(list2);
    }

    public static void method(ArrayList<?> list){
        for (Object o : list) {
            System.out.println(o);
        }
    }

}

泛型通配符与类型限定符结合¶

例如下面的代码：

Java
public class Test06 {
    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<String> list2 = new ArrayList<>();
        ArrayList<Number> list3 = new ArrayList<>();
        ArrayList<Object> list4 = new ArrayList<>();

        get1(list1);
        //get1(list2);错误
        get1(list3);
        //get1(list4);错误

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

        //get2(list1);错误
        //get2(list2);错误
        get2(list3);
        get2(list4);
    }

    //上限  ?只能接收extends后面的本类类型以及子类类型
    public static void get1(Collection<? extends Number> collection){

    }

    //下限  ?只能接收super后面的本类类型以及父类类型
    public static void get2(Collection<? super Number> collection){

    }
}

斗地主案例¶

案例介绍：

按照斗地主的规则，完成洗牌发牌的动作。具体规则：

使用54张牌打乱顺序，三个玩家参与游戏，三人交替摸牌，每人17张牌，最后三张留作底牌

案例分析：

准备牌：

牌可以设计为一个ArrayList<String>，每个字符串为一张牌。每张牌由花色数字两部分组成，我们可以使用花色集合与数字集合嵌套迭代完成每张牌的组装。牌由Collections类的shuffle方法进行随机排序。
发牌

将每个人以及底牌设计为ArrayList<String>，将最后3张牌直接存放于底牌，剩余牌通过对3取模依次发牌。
看牌

直接打印每个集合

Java
public class Test_Poker {
    public static void main(String[] args) {
        // 创建花色
        ArrayList<String> color = new ArrayList<>();
        Collections.addAll(color, "黑桃", "红心", "梅花", "方块");
        // 创建号牌
        ArrayList<String> number = new ArrayList<>();
        Collections.addAll(number, "2", "A", "K", "Q", "J", "10", "9", "8", "7", "6", "5", "4", "3");
        // 创建牌盒
        ArrayList<String> pokerBox = new ArrayList<>();
        // 大小王
        pokerBox.add("大王");
        pokerBox.add("小王");
        // 发牌
        for (String s : color) {
            for (String string : number) {
                pokerBox.add(s + string);
            }
        }

        // 打乱牌盒
        Collections.shuffle(pokerBox);

        // 创建玩家
        ArrayList<String> player1 = new ArrayList<>();
        ArrayList<String> player2 = new ArrayList<>();
        ArrayList<String> player3 = new ArrayList<>();
        ArrayList<String> last = new ArrayList<>();

        System.out.println(pokerBox.size());
        // 发牌，留三张底牌
        for (int i = 0; i < pokerBox.size(); i++) {
            if (i >= 51) {
                last.add(pokerBox.get(i));
            } else if (i % 3 == 0) {
                player1.add(pokerBox.get(i));
            } else if (i % 3 == 1) {
                player2.add(pokerBox.get(i));
            } else {
                player3.add(pokerBox.get(i));
            }
        }

        // 查看
        System.out.println("player1: " + player1);
        System.out.println("player2: " + player2);
        System.out.println("player3: " + player3);
        System.out.println("last: " + last);
    }
}

也可以使用字符分割方法对创建花色和创建号牌进行优化

Java
public class Test_Poker01 {
    public static void main(String[] args) {
        // 创建花色
        String[] color = "黑桃-红心-梅花-方块".split("-");
        // 创建号牌
        String[] number = "2-3-4-5-6-7-8-9-10-J-Q-K-A".split("-");

        // 创建牌盒
        ArrayList<String> pokerBox = new ArrayList<>();
        // 添加大小王
        pokerBox.add("大王");
        pokerBox.add("小王");

        // 组合其他牌
        for (String s : color) {
            for (String n : number) {
                pokerBox.add(s+n);
            }
        }

        // 创建玩家并发牌
        ArrayList<String> player1 = new ArrayList<>();
        ArrayList<String> player2 = new ArrayList<>();
        ArrayList<String> player3 = new ArrayList<>();
        // 底牌
        ArrayList<String> last = new ArrayList<>();

        for (int i = 0; i < pokerBox.size(); i++) {
            if(i >= 51) {
                last.add(pokerBox.get(i));
            } else if(i % 3 == 0) {
                player1.add(pokerBox.get(i));
            } else if(i % 3 == 1) {
                player2.add(pokerBox.get(i));
            } else {
                player3.add(pokerBox.get(i));
            }
        }

        // 查看
        System.out.println("player1: " + player1);
        System.out.println("player2: " + player2);
        System.out.println("player3: " + player3);
        System.out.println("last: " + last);
    }
}

`Set`接口¶

`Set`接口介绍¶

Set接口实际上并没有对Collection接口进行功能上的扩充，而且所有的Set集合底层都是依靠Map实现，部分内容将在Map中具体介绍

Set和Map密切相关的

Map的遍历需要先变成单列集合，只能变成set集合

`HashSet`类¶

HashSet是Set接口的实现类，下面是HashSet的特点：

元素不允许重复
元素插入顺序与存储顺序不一定相同
没有索引的方式操作元素
线程不安全
底层数据结构：
1. JDK8之前：哈希表（数组+链表实现）
2. JDK8之后：哈希表（数组+链表+红黑树实现）
方法：与Collection接口中的方法基本一致，但是因为HashSet是实现类，所以HashSet存在具体的方法体
遍历方式：
1. 增强for
2. 迭代器

基本使用实例：

Java
public class Test {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("张三");
        set.add("李四");
        set.add("王五");
        set.add("赵六");
        set.add("田七");
        set.add("张三");
        System.out.println(set);

        //迭代器
        Iterator<String> iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
        System.out.println();
        //增强for
        for (String s : set) {
            System.out.println(s);
        }
    }
}

`LinkedHashSet`类¶

LinkedHashSet是Set接口的实现类，并且继承自HashSet类，下面是LinkedHashSet的特点：

元素唯一
元素插入顺序与存储顺序相同
没有索引的方式操作元素
线程不安全
底层数据结构：哈希表+双向链表
方法：与HashSet基本一致

基本使用如下：

Java
public class Test01 {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        set.add("张三");
        set.add("李四");
        set.add("王五");
        set.add("赵六");
        set.add("田七");
        set.add("张三");
        System.out.println(set);

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

        System.out.println();

        //增强for
        for (String s : set) {
            System.out.println(s);
        }
    }
}

哈希值介绍¶

在Java中，哈希值是由计算机算出来的一个十进制数，可以看做是对象的地址值

需要获取对象的哈希值可以通过Object类中的本地方法：public native int hashCode()

例如查看Person类的两个对象的hashCode

Java
public class Test {
    public static void main(String[] args) {
        Person person1 = new Person();
        Person person2 = new Person();

        System.out.println(person1.hashCode());
        System.out.println(person2.hashCode());
    }
}

输出结果：
1163157884
1956725890

实际上，在Person类中没有重写toString方法时打印的数据后面数字对应的就是对象的hashCode，只是显示的是对应的16进制，例如下面的代码

Java
public class Test {
    public static void main(String[] args) {
        Person person1 = new Person();
        Person person2 = new Person();

        System.out.println(person1);
        System.out.println(person2);
    }
}

输出结果：
com.epsda.advanced.test_HashCode.Person@4554617c
com.epsda.advanced.test_HashCode.Person@74a14482

如果将前面直接打印的hashCode值以16进制形式打印，则此时会发现对应的数值与默认打印对象名的数据的hashCode一致，例如下面的代码：

Java
public class Test {
    public static void main(String[] args) {
        Person person1 = new Person();
        Person person2 = new Person();

        System.out.println(Integer.toHexString(person1.hashCode()));
        System.out.println(Integer.toHexString(person2.hashCode()));

        System.out.println(person1);
        System.out.println(person2);
    }
}

输出结果：
4554617c
74a14482
com.epsda.advanced.test_HashCode.Person@4554617c
com.epsda.advanced.test_HashCode.Person@74a14482

所以，当对象重写了toString方法，此时就不会打印对象的地址，实际上就是不打印对应的hashCode

如果在类中重写hashcode，此时打印对象的hashCode值就会根据内容进行计算，例如下面的代码：

Java
// Person类
public class Person {
    // ...

    // 重写hashCode
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}


public class Test {
    public static void main(String[] args) {
        Person person1 = new Person("张三", 23);
        Person person2 = new Person("张三", 23);

        System.out.println(person1.hashCode());
        System.out.println(person2.hashCode());
    }
}

输出结果：
24022543
24022543

在上面的代码中，因为Person类的两个对象内容一致，并且因为Person类重写了hashCode方法，方法中是根据成员内容进行hashCode计算的，所以打印的hashcode是相同的

但是，有些特殊情况，内容不同时，hashCode可能相同，这个现象被称为哈希冲突或哈希碰撞，例如下面的代码：

Java
public class Test {
    public static void main(String[] args) {
        String s1 = "通话";
        String s2 = "重地";

        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());
    }
}

输出结果：
1179395
1179395

总结：

当内容相同时，hashCode一定相同；但是内容不同时，hashCode不一定相同

Java中计算哈希值的方法¶

以下面的代码为例：

Java
public class Test01 {
    public static void main(String[] args) {
        String s = "abc";
        System.out.println(s.hashCode());
    }
}

对应的hashCode源码如下：

Java
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

上面的代码中，value是String底层的byte类型数组，使用char类型的val数组接受，根据val数组中的字符依次进行h = h * 31 + val[i]进行计算直到循环结束，此时h即为对应的hash值

Note

计算hashCode时，之所以使用31可以简单理解为31是一个质数，31这个数通过大量的计算和统计，认为用31，可以尽量降低内容不一样但是哈希值一样的情况

`HashSet`去重的方式¶

Note

本部分简单介绍，在Map部分会进行详细介绍

先计算元素的哈希值（重写hashCode方法），再比较内容（重写equals方法）
先比较哈希值，如果哈希值不一样，存入集合中
如果哈希值一样,再比较内容
1. 如果哈希值一样，内容不一样，直接存入集合
2. 如果哈希值一样，内容也一样，去重复内容，留一个存入集合

所以前面之所以重写了equals方法的同时还需要重写hashCode就是为了尽可能保证内容比较和去重的可靠性

总结：

对于自定义类型来说，如果不需要打印对象的地址而是打印对象的内容就重写toString方法，而需要比较对象是否相同除了内容比较还需要进行hashCode比较，所以需要重写equals和hashCode方法

Java集合¶

集合介绍¶

单列集合分类¶

Collection接口¶

创建Collection实现类对象¶

常用方法¶

迭代器¶

基本使用¶

迭代器的执行过程¶

迭代器底层原理¶

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

List接口¶

ArrayList类¶

介绍¶

常用方法¶

遍历集合¶

ArrayList底层源码分析¶

初始容量¶

数组扩容¶

LinkedList类¶

介绍¶

常用方法¶

遍历集合¶

LinkedList底层源码分析¶

LinkedList成员分析¶

LinkedList中add方法源码分析¶

LinkedList中get方法源码分析¶

增强for循环¶

Collections集合工具类¶

泛型¶

泛型介绍¶

定义泛型¶

类型限定符¶

泛型通配符¶

泛型通配符与类型限定符结合¶

斗地主案例¶

Set接口¶

Set接口介绍¶

HashSet类¶

LinkedHashSet类¶

哈希值介绍¶

Java中计算哈希值的方法¶

HashSet去重的方式¶

`Collection`接口¶

创建`Collection`实现类对象¶

`List`接口¶

`ArrayList`类¶

`ArrayList`底层源码分析¶

`LinkedList`类¶

`LinkedList`底层源码分析¶

`LinkedList`成员分析¶

`LinkedList`中`add`方法源码分析¶

`LinkedList`中`get`方法源码分析¶

增强`for`循环¶

`Collections`集合工具类¶

`Set`接口¶

`Set`接口介绍¶

`HashSet`类¶

`LinkedHashSet`类¶

`HashSet`去重的方式¶