【Java基础】集合（Collection、List、Set）

集合分类

1. 单列集合（Collection）。元素是一个一个的。
2. 双列集合（Map）。元素是一对一的。

单列集合（Collection）

Collection集合体系

1. 子接口List。
   1. 实现类ArrayList。
   2. 实现类LinkedList。
2. 子接口Set。
   1. 实现类HashSet。
      1. LinkedHashSet。
   2. 实现类TreeSet。

学习时要掌握的：

1. 有什么特点？
2. 是否有特有功能？
3. 适合什么业务场景？

Collection集合特点

List系列

添加的元素有序、可重复、有索引。

1. ArrayList、LinkedList有序、可重复、有索引。

Set系列

添加的元素无序、不重复、无索引。

1. HashSet。无序、不重复、无索引。
2. LinkedHashSet。有序、不重复、无索引。
3. TreeSet。按照大小默认升序排序、不重复、无索引。

Collection常用方法

为什么要学？

• 因为Collection是单列集合的祖宗，它规定的方法（功能）是全部单列集合都会继承的。

常用方法：

1. public boolean add(E e)。把给定的对象添加到当前集合中 。由于允许数据重复，所以一定返回true。
2. public void clear() 。清空集合中所有的元素。
3. public boolean remove(E e)。把给定的对象在当前集合中删除。如果有多个重复元素只能删除第一个。
4. public boolean contains(Object obj)。判断当前集合中是否包含给定的对象。是精确匹配。
5. public boolean isEmpty()。判断当前集合是否为空。
6. public int size()。返回集合中元素的个数。
7. public Object[] toArray()。把集合中的元素，存储到数组中。Object类型是为了兼容各种类型的数据。
8. addAll(Collection<? extends String> c)。把另一个集合中的全部数据倒入，数据类型要一样。

Collection遍历方式

1. 迭代器

迭代器是用来遍历集合的专用方式(数组没有迭代器)，在Java中迭代器的代表是Iterator。

Collection集合获取迭代器的方法：

• **Iterator iterator()**。返回集合中的迭代器对象，该迭代器对象默认指向当前集合的第一个元素。
  1. 从集合对象中获取迭代器对象。
  2. 判断当前位置是否有元素可以获取。不判断的话可能出现NoSuchElementException异常。
  3. 获取当前位置的元素，然后自动指向下一个元素。

Collection<String> c = new ArrayList<>();
c.add("赵敏");
c.add("小昭");
c.add("素素");
c.add("灭绝");
System.out.println(c); //[赵敏, 小昭, 素素, 灭绝]
Iterator<String> it = c.iterator();
while(it.hasNext()){
    String e = it.next();
    System.out.println(s);
} //判断一次，取一次

Iterator迭代器中的常用方法：

• boolean hasNext()。询问当前位置是否有元素存在，存在返回true ,不存在返回false。
• E next()。获取当前位置的元素，并同时将迭代器对象指向下一个元素处。

2. 增强for

为什么用增强的？因为Collection中没有规定集合的索引，只有List集合才支持索引。

• 格式：for (元素的数据类型 变量名 : 数组或者集合) { }。变量名相当于游标。（类似于Python中的for img in imgs这种写法。）
• 可以遍历集合或者数组。
• 遍历集合本质是迭代器遍历集合的简化写法。
• 简化写法：数组或集合**.for再回车**。

3. lambda表达式

得益于JDK 8开始的新技术Lambda表达式，提供了一种更简单、更直接的方式来遍历集合。

方法：default void forEach(Consumer<? super T> action) 。结合lambda遍历集合。

举例：

Collection<String> c = new ArrayList<>();
c.add("赵敏");
c.add("小昭");
c.add("素素");
c.add("灭绝");

//调用forEach方法
//由于参数是一个Consumer接口，所以可以传递匿名内部类
c.forEach(new Consumer<String>{
    @Override
    public void accept(String s){
        System.out.println(s);
    }
});

//也可以使用lambda表达式对匿名内部类进行简化
c.forEach((String s) ->
        System.out.println(s);
});

c.forEach(s ->
        System.out.println(s);
);

c.forEach(s -> System.out.println(s));

c.forEach(System.out::println); //[赵敏, 小昭, 素素, 灭绝]

lambda表达式遍历Collection集合不算简洁，之后遍历Map才是简洁。

(一)List集合

ArrayList、LinkedList有序、可重复、有索引。但是底层数据结构不同（数据结构：存储、组织数据的方式），应用场景也不同。继承了Collection的功能。

创建（List是接口，所以需要指定具体的类）：

List<String> list = new ArrayList<>();//经典代码，多态

常用方法

List集合因为支持索引，所以多了很多索引相关的方法：

1. void add(int index,E element)。在此集合中的指定位置插入指定的元素。不写索引的话，默认是插入到最后。
2. E remove(int index)。删除指定索引处的元素，返回被删除的元素。
3. E set(int index,E element)。修改指定索引处的元素，返回被修改的元素。
4. E get(int index)。返回指定索引处的元素。

List集合支持的遍历方式

1. 普通for循环（只因为List有索引）。集合名.fori自动完成。
2. 增强for/foreach遍历。集合名.for自动完成。
3. 迭代器。先创建迭代器，再判断并遍历。
4. Lambda表达式。forEach方法。

List<String> list = new ArrayList<>();
list.add("蜘蛛精");
list.add("至尊宝");
list.add("糖宝宝");

//1.普通for循环
for(int i = 0; i< list.size(); i++){
    //i = 0, 1, 2
    String e = list.get(i);
    System.out.println(e);
}

//2.增强for遍历
for(String s : list){
    System.out.println(s);
}

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

//4.lambda表达式遍历
list.forEach(s->System.out.println(s));

(1)ArrayList集合的底层原理

基于数组实现的。

特点（查询快、增删慢）：

1. 查询速度快（根据索引查询数据快）。查询数据通过地址值和索引定位，查询任意数据耗时相同。
2. 删除效率低。可能需要把后面很多的数据进行前移。
3. 添加效率极低。可能需要把后面很多的数据后移，再添加元素；或者也可能需要进行数组的扩容。

底层原理：

1. 利用无参构造器创建的集合，会在底层创建一个默认查高难度为0的数组。
2. 添加第一个元素时，底层会创建一个新的长度为10的数组。
3. 存满时（添加第11个元素时），扩容1.5倍。
4. 如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度以实际为准。

应用场景：

1. 适合：根据索引查询数据，比如根据随机索引取数据（高效），或者数据量不是很大时。
2. 不适合：数据量大的同时，又要频繁地进行增删操作。

(2)LinkedList集合的底层原理

基于双链表实现的（Java中大多数情况都使用双向链表）。

什么是链表？

• 链表结构是由一个一个的节点组成，一个节点由数据值、下一个元素的地址组成。
• 链表中的结点是独立的对象，在内存中是不连续的，每个节点包含数据值和下一个节点的地址。
• 特点1：查询慢，无论查询哪个数据都要从头开始。
• 特点2：增删相对较快。但是对于首尾元素进行增删改查的速度是极快的。

LinkedList新增了一些可以针对头尾进行操作的方法：

1. public void addFirst(E e)。在该列表开头插入指定的元素。
2. public void addLast(E e)。将指定的元素追加到此列表的末尾。
3. public E getFirst()。返回此列表中的第一个元素。
4. public E getLast()。返回此列表中的最后一个元素。
5. public E removeFirst()。从此列表中删除并返回第一个元素。
6. public E removeLast()。从此列表中删除并返回最后一个元素。

应用场景：

1. 设计队列（特点：先进先出，后进后出）。队列只是在首尾增删元素。
   1. 入队。addLast方法。
   2. 出队。removeFirst方法。
2. 设计栈（特点：先进后出，后进先出）。
   1. 进栈（压栈）。push方法（其实就是调用的addFirst方法）。
   2. 出站（弹栈）。pop方法（其实就是调用的removeFirst方法）。

(二)Set集合

添加的元素无序、不重复、无索引。

1. HashSet。无序、不重复、无索引。
2. LinkedHashSet。有序、不重复、无索引。（是HashSet的子孙类。）
3. TreeSet。按照大小默认升序排序、不重复、无索引。

创建（Set是接口，所以需要指定具体的类）：

//一行经典代码
Set<Integer> set = new HashSet<>();	//无序、无索引、不重复（无序是指和添加元素的顺序无关）
Set<Integer> set = new LinkedHashSet<>(); //有序、无索引、不重复（有序是指和添加元素的顺序有关）
Set<Integer> set = new TreeSet<>(); //可排序(升序)、无索引、不重复

常用方法

要用的常用方法，基本上都是其父类Collection提供的。

(1)HashSet集合

需要掌握的：

1. 为什么添加的元素无序、不重复、无索引？
2. 增删改查数据有什么特点，适合什么场景？

哈希值：

• 一个int类型的数值，Java中每个对象都有一个哈希值。
• Java中的所有对象，都可以调用Object类提供的hashCode方法，返回该对象自己的哈希值。

对象哈希值的特点：

• 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
• 不同的对象，哈希值一般不同，但也有可能相同（哈希碰撞）。

HashSet集合的底层原理

• 基于哈希表实现。
• 是一种增删改查性能都较好的数据结构。
• JDK8以前：哈希表 = 数组+链表
• JDK8以后：哈希表 = 数组+链表+红黑树

JDK8以前HashSet集合的底层原理：

1. 创建一个默认长度为16的数组，默认加载因子为0.75，数组名table；
2. 使用元素的哈希值对数组的长度求余计算出应存入的位置；
3. 判断当前位置是否为null，如果是null直接存入；
4. 如果不为null，表示有元素，则调用equals方法比较相等，则不存；不相等，则存入数据。
   • JDK8以前，新元素存入数组，占用老元素的位置，老元素挂下面；
   • JDK8以后，新元素挂在老元素下面。

往HashSet集合中存储元素时，底层调用了元素的两个方法：一个是hashCode方法获取元素的hashCode值（哈希值）；另一个是调用了元素的equals方法，用来比较新添加的元素和集合中已有的元素是否相同。

• 只有新添加元素的hashCode值和集合中以后元素的hashCode值相同、新添加的元素调用equals方法和集合中已有元素比较结果为true, 才认为元素重复。
• 如果hashCode值相同，equals比较不同，则以链表的形式连接在数组的同一个索引为位置。–>导致的问题：如果数组快占满了，链表过长，导致查询性能降低。–>哈希表的扩容机制（占满加载因子0.75*长度就会扩容，扩容成原来数组的两倍）。

在JDK8以后的优化：

• 当链表的长度超过8，且数组长度超过64时，就会自动把链表转换为红黑树。

深入理解HashSet集合去重的机制

注意：HashSet集合默认不能对内容一样的两个不同对象去重复！（因为不同对象哈希值不一样，因此存储位置不同，就会被认为不是重复的。）

如何让HashSet集合能够实现对内容一样的两个不同对象也能去重复？？？

• 如果希望Set集合认为2个内容一样的对象是重复的，
  必须重写对象的hashCode()和equals()方法。
• 在类中**右键-generate-euqals() and hashCode()**，一路next。这里euqals方法只要两个对象内容一样就返回true，hashCode方法只要两个对象内容一样，返回的哈希值就是一样的。

(2)LinkedHashSet集合

• 有序、不重复、无索引。
• 基于哈希表（数组+链表+红黑树）实现的。
• 每个元素都额外的多了一个双链表的机制记录它前后元素的位置。增删改查比较快，但是也更占内存。

(3)TreeSet集合

• 排序、不重复、无索引。
• 基于红黑树实现的排序。增删改查性能较好。
• 对于数值类型：Integer , Double，默认按照数值本身的大小进行升序排序。
• 对于字符串类型：默认按照首字符的编号升序排序。
• 对于自定义类型如Student对象，TreeSet默认是无法直接排序的。

自定义排序规则

• TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方式来指定比较规则。

排序方式1：让自定义的类（如学生类）实现Comparable接口，重写里面的compareTo方法来指定比较规则。但是要注意，如果值相等，就认为是重复的，只会保存一个对象！

//第一步：先让Student类，实现Comparable接口
//注意：Student类的对象是作为TreeSet集合的元素的
public class Student implements Comparable<Student>{
    private String name;
    private int age;
    private double height;
	//无参数构造方法
    public Student(){}
    //全参数构造方法
    public Student(String name, int age, double height){
        this.name=name;
        this.age=age;
        this.height=height;
    }
    //...get、set、toString()方法自己补上..
    
    //第二步：重写compareTo方法
    //按照年龄进行比较，只需要在方法中让this.age和o.age相减就可以。
    /*
    原理：
    在往TreeSet集合中添加元素时，add方法底层会调用compareTo方法，根据该方法的
    结果是正数、负数、还是零，决定元素放在后面、前面还是不存。
    */
    @Override
    public int compareTo(Student o) {
        //this：表示将要添加进去的Student对象
        //o: 表示集合中已有的Student对象
        return this.age-o.age;
    }
}

排序方式2：通过调用TreeSet集合有参数构造器，可以设置Comparator对象（比较器对象，用于指定比较规则）。TreeSet自动选择自己自带的比较器对象进行排序。

//创建TreeSet集合时，传递比较器对象排序
/*
原理：当调用add方法时，底层会先用比较器，根据Comparator的compare方是正数、负数、还是零，决定谁在后，谁在前，谁不存。
*/
//下面代码中是按照学生的年龄升序排序
Set<Student> students = new TreeSet<>(new Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2){
        //需求：按照学生的身高排序
        return Double.compare(o1,o2); 
    }
});

//可以用lambda表达式简化
//Set<Student> students = new TreeSet<>(o1,o2)->Double.compare(o1.getHeight(), o2.getHeight()));

//创建4个Student对象
Student s1 = new Student("至尊宝",20, 169.6);
Student s2 = new Student("紫霞",23, 169.8);
Student s3 = new Student("蜘蛛精",23, 169.6);
Student s4 = new Student("牛魔王",48, 169.6);

//添加Studnet对象到集合
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
System.out.println(students); 

总结

1. 如果希望记住元素的添加顺序，需要存储重复的元素，又要频繁的根据索引查询数据？
   • 用ArrayList集合（有序、可重复、有索引），底层基于数组的。（常用）
2. 如果希望记住元素的添加顺序，且增删首尾数据的情况较多？
   • 用LinkedList集合（有序、可重复、有索引），底层基于双链表实现的。
3. 如果不在意元素顺序，也没有重复元素需要存储，只希望增删改查都快？
   • 用HashSet集合（无序，不重复，无索引），底层基于哈希表实现的。 （常用）
4. 如果希望记住元素的添加顺序，也没有重复元素需要存储，且希望增删改查都快？
   • 用LinkedHashSet集合（有序，不重复，无索引）， 底层基于哈希表和双链表。
5. 如果要对元素进行排序，也没有重复元素需要存储？且希望增删改查都快？
   • 用TreeSet集合，基于红黑树实现。

注意事项：集合的并发修改异常问题

集合的并发修改异常

并发：多件事正在进行。

• 使用迭代器遍历集合时，又同时在删除集合中的数据，程序就会出现并发修改异常的错误。
  • 原因：其实和之前用for循环的时候差不多，索引没有减1的话会导致有些元素没被删掉，但是迭代器知道程序员有可能出现这个错误，所以报了一个善意的提醒。
  • 解决方法：不能用集合对象自己去删除数据。使用迭代器的remove方法。（现在一共学了3种方法：1. 每次减1，2. 倒着遍历，3. 用迭代器去删。）
• 由于增强for循环遍历集合就是迭代器遍历集合的简化写法，因此，使用增强for循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误。
  • 原因：增强for循环相当于迭代器简化写法，但是又拿不到迭代器。类似地，使用lambda表达式也会出现这个问题，因为其内部使用的是增强for循环。

怎么保证遍历集合同时删除数据时不出bug？

• 使用迭代器遍历集合，但用迭代器自己的删除方法删除数据即可。
• 如果能用for循环遍历时：可以倒着遍历并删除；或者从前往后遍历，但删除元素后做i–操作。

Collection集合其他知识

可变参数

就是一种特殊形参，定义在方法、构造器的形参列表里，格式是：数据类型…参数名称。

可变参数的特点和好处

• 特点：可以不传数据给它；可以传一个或者同时传多个数据给它；也可以传一个数组给它。
• 好处：常常用来灵活的接收数据。

可变参数的注意事项

• 可变参数在方法内部就是一个数组。
• 一个形参列表中可变参数只能有一个。
• 可变参数必须放在形参列表的最后面。

Collections

一个用来操作集合的工具类。

提供的静态方法

1. public static boolean addAll(Collection<? super T> c, T… elements)。给集合批量添加元素。
2. public static void shuffle(List<?> list) 。打乱List集合中的元素顺序。
3. public static void sort(List list)。对List集合中的元素进行升序排序。
4. public static void sort(List list，Comparator<? super T> c)。对List集合中元素，按照比较器对象指定的规则进行排序。

后两个是排序方法，3可以直接对自定义类型的List集合排序，但自定义类型必须实现了Comlarable接口，指定了比较规则才可以。

综合案例

斗地主。