单列集合

单列集合图解

注意点：

1. List系列集合：有序、可重复、有索引
2. Set系列集合：无序、不重复、无索引
3. Vector集合已经被淘汰，了解即可
4. Collection接口是单列集合的祖先（最顶层），它的功能所有单列集合都可以使用
5. 切记：泛型只允许指定“引用数据类型”，当集合需要存储基本数据类型时，我们可以在泛型中指定基本数据类型对应的包装类

   // 集合指定基本数据类型的包装类
   Collection<Integer> collection = new ArrayList<>();

Collection接口

常用方法

public boolean add(E e)                 把给定的对象添加到当前集合中
public void clear()                     清空集合中所有的元素
public boolean remove(Object e)         把给定的对象在当前集合中删除
public boolean contains(Object obj)     判断当前集合中是否包含给定的对象
public boolean isEmpty()                判断当前集合是否为空
public int size()                       返回集合中元素的个数/集合的长度

例题：

1. add()：将给定的对象添加到当前集合中

   // 定义集合
   Collection<String> collection = new ArrayList<>();
   // 添加元素
   boolean success = collection.add("张三");

   注意：
   a. add()的返回值：true，表示添加成功，false，表示添加失败
   b. 如果当前集合是List系列的，则返回值一定是true（一定会添加成功）
   c. 如果当前集合是Set系列的，则返回值有可能是true，也有可能是false
   原因：Set集合是不重复的，当指定添加的元素在集合中存在，则添加失败，add()的返回值就是false
2. clear()：清空集合

   // 定义集合
   Collection<String> collection = new ArrayList<>();
   // 添加元素
   boolean success = collection.add("张三");
   boolean success = collection.add("李四");
   // 清空集合
   collection.clear()

3. remove(E e)：删除集合中指定的元素

   // 定义集合
   Collection<String> collection = new ArrayList<>();
   // 添加元素
   boolean success = collection.add("张三");
   // 删除集合中指定的元素
   boolean resultRemove = collection.remove("张三");

   注意：
   a. 如果当前集合中没有指定删除的元素，则删除失败，返回值为：false
   b. 如果当前集合中有指定删除的元素，则删除成功，返回值为：true
   c. remove()的实参一定是对象（不能是索引）

   原因：Collection接口中的方法声明的是单列集合（Set + List）中共性的方法，>Set系列集合是没有索引的，所以如果在Collection中声明有索引的方法是不合适的

   补充说明：List集合有索引、Set集合无索引，所以有索引的方法是List集合的特有方法，会被声明在List接口中

4. contains()：判断当前集合中是否包含给定的对象
   注意点： 如果当前集合存储的数据是自定义类，此时使用contains()判断集合中是否包含给定的对象，自定义类需要重写equals()

import java.util.Objects;

public class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student() {
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
    // 不用手写，直接在IDEA中，按快捷键 alt + insert，然后选择重写equals即可
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }
}

// 集合存储自定义对象
Collection<Student> collection02 = new ArrayList<>();
// 创建自定义对象（准备数据测试）
Student student01 = new Student("张飞",18);
Student student02 = new Student("曹操",20);
Student student03 = new Student("张飞",18);
// 将元素添加到集合中
collection02.add(student01);
collection02.add(student02);
// Student未重写equals方法，返回子：fasle
boolean result01 =  collection02.contains(student03);
// Student重写了equals方法，返回子：true
boolean result01 =  collection02.contains(student03);

为什么要重写equals()？

1. Object是所有类的父类，equals()方法是声明定义在Object中的
2. Object中的equals比较的是栈内存中的值，即：基本数据类型比较其值，引用数据类型比较的是地址值
3. String类中的equals重写了，所以字符串调用equals比较的是 堆内存 中 存储的具体值，而不是栈内存中的地址值
4. 自定义类，如果想要比较其属性中存储的值是否相等，则需要重写equals，否则equals()是Object继承下来的方法，比较的是地址值
5. 技巧：重写的代码不用书写，IDEA可以自动生成（alt + insert，然后选择重写的方法equals即可）

isEmpty()：判断当前集合是否是空集合

Collection<String> collection = new ArrayList<>();
// 当前集合是空集合，则返回：true
// 不是空集合，返回：false
boolean issuccess = collection.isEmpty();

size()：获取集合中的元素个数

Collection<String> collection = new ArrayList<>();
// 获取集合元素个数
int len = collection.size();

Collection遍历（单列集合通用遍历方式）

Collection集合的遍历方式有三种：迭代器遍历，增强for、lambda
注意：这三种方式的遍历，都不允许在集合遍历时，使用集合中的方法对集合进行添加、删除等操作

1. 迭代器遍历集合
   迭代器是Java中专门用来遍历集合的

   public Iterator<E> iterator()       // Collection接口中的方法，用来获取迭代器对象
   
   // Iterator中的方法
   // 判断当前指针所在位置是否有元素，有元素，返回true，没有，返回false
   public boolean hasNext();  
   // 获取迭代器指针所在位置的元素，并且将指针向后移动一个位置
   public E next();

   注意：
   a. 当我们获取一个新的迭代器对象时，迭代器指针此时的位置是在第一个元素上
   b. 当指针所在的位置，没有元素，此时使用next()，程序会抛出错误（所以在使用next获取元素之前一定要，判断指针所在位置是否有元素）
   c. 迭代器遍历完成后，指针不会复位（遍历开始时的初始位置）
   d. 迭代器遍历时，不能使用集合中的方法，对集合进行添加、删除操作（可以使用迭代器方法删除、添加）
   技巧：由于迭代器遍历完成后，指针不会复位，如果此时还想再次遍历集合，可以创新创建一个新的迭代器对象，再进行遍历
   例题：

   // 创建集合对象
   Collection<String> collection = new ArrayList<>();
   // 添加数据
   collection.add("张三");
   collection.add("李四");
   
   // 获取迭代器对象
   Iterator<String> iterator = collection.iterator();
   // 迭代器遍历集合
   while(iterator.hasNext()){
       String item = iterator.next();
       System.out.println(item);
   }

   迭代器遍历集合时，不能使用集合中的方法删除、添加元素，但可以使用迭代器中的方法添加、删除元素

   // 创建集合对象
   Collection<String> collection = new ArrayList<>();
   // 添加数据
   collection.add("张三");
   collection.add("李四");
   Iterator<String> iterator = collection.iterator();
   while(iterator.hasNext()){
       String item = iterator.next();
       if(item.equals("张三")) {
           // 从底层集合中删除此迭代器 返回的最后一个元素
           iterator.remove();
       }
       System.out.println(item);
   }

2. 增强for遍历

   a. 增强for是JDK5出现的语法
   b. 增强for的底层实现就是一个迭代器
   c. 增强for遍历时，也是不能使用集合中的方法对集合进行添加、删除操作（原因：底层是迭代器）
   d. 所有的 “单列集合” 以及 “数组” 才可以使用增强for遍历
   格式：for(元素类型 变量名 : 集合/数组) {}
   例题：

   Collection<String> collection = new ArrayList<>();
   collection.add("张三");
   collection.add("李四");
   for(String item : collection) {
       System.out.println(item);
   }

3. lambda
   lambda是为了简化匿名内部类而出现的新语法（JDK8）
   例题：
   准备数据

   Collection<String> collection = new ArrayList<>();
   collection.add("张飞");
   collection.add("孙权");
   collection.add("诸葛亮");

   匿名内部类的方式遍历（forEach + 匿名内部类）

   // Consumer：函数式接口
   collection.forEach(new Consumer<String>() {
       @Override
       public void accept(String s) {
           System.out.println(s);
       }
   });

   lambda方式遍历（lambda + forEach）

   // forEach + Lambda 遍历集合
   collection.forEach((String s) -> {
       System.out.println(s);
   });
   
   // 简化：如果需要重写的方法只有一个参数，则可以将()去掉
   collection.forEach(s -> {
       System.out.println(s);
   });
   
   // 再次简化：如果方法体中只有一条语句，则可以将{}去掉
   collection.forEach(s -> System.out.println(s));

   注意：在遍历时，也是不能通过集合中的方法对集合中的元素进行添加、删除操作的

List集合

a. List是Collection接口的子接口
b. 特点：有序、有索引、可重复
c. List集合是有索引的，所以在List接口中声明了一系列操作索引的特有方法

List中的特有方法

void add(int index,E element)       集合指定位置插入元素
E remove(int index)                 删除指定索引处的元素，并返回删除的元素
E set(int index,E element)          修改指定索引处的元素，返回被修改的元素（修改前的值）
E get(int index)                    返回指定索引处的元素

注意：索引是从0开始的

例题：

List<String> list = new ArrayList<>();
list.add("赵四");
list.add("刘能");
list.add("谢广坤");
// 删除索引0处的元素
list.remove(0);

remove()的特殊用例(重要)：

boolean remove(Object object)       继承自Collection接口
E remove(int index)                 List接口中定义的方法

remove(int index)和remove(Object object)属于重载方法

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
// 当List集合中存储的数据是Integer类型的数据时，此时我们我们传入一个整数
// 为什么调用的是remove(int index)，而不是remove(Object object)呢？
Integer removeElement = list.remove(1);

// remove的执行机制：据传入的 参数的类型 进行判断选择哪种remove方法
// 如：我们传入的参数是int类型，则是选择remove(int index)
// 当我们传入的参数是 Integer（引用数据类型），则选择remove(Object object)

// 手动装箱
Integer i = Integer.valueOf(1);
// 选择的是remove(Object object)
boolean success = list.remove(i);

简单理解：参数是基本数据类型，优先选择remove(int index)，参数是引用数据类型，优先选择remove(Object object)

List集合特有遍历方式

1. 列表迭代器
2. 普通for遍历

列表迭代器遍历

a. ListIterator：列表迭代器，是一个接口，继承Iterator
b. ListIterator接口在继承了Iterator接口中的方法继承上，还自定义了一些特有方法，如：add()

例题：

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
// 获取ListIterator对象
ListIterator<String> listIterator = list.listIterator();
while (listIterator.hasNext()) {
    String str = listIterator.next();
    if (str.equals("c")) listIterator.add("e"); // 添加元素
    System.out.println(str);
}
System.out.println(list);

普通for遍历

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
// 普通for遍历：
for (int i = 0; i < list.size(); i++) {
    // List集合是有索引的，所以可以通过索引获取对应值
    String str = list.get(i);
    System.out.println(str);
}

ArrayList

1. ArrayList是List接口的实现类
2. ArrayList的数据结构：数组结构
3. ArrayList的底层原理：
   a. 利用空参构造创建的集合，在底层创建一个默认长度为0的数组
   b. 当添加第一个元素时，底层会创建一个新的长度为10的数组
   c. 当数组存满时，会扩容当前数组长度1.5倍（创建长度为1.5倍的新数组，再将原本数组拷贝到新数组中）
   d. 依次类推，数组存满就扩容当前数组长度的1.5倍，再将原数组拷贝到新数组中
   e. 特殊情况：如果一次添加多个元素，且数组的1.5倍还是放不下，则创建的新数组的长度以实际元素个数为准

注意：size()：获取集合内元素的个数，并不是底层数组的长度
AraryList无特殊的API，与List接口中定义的基本一致

LinkedList

1. LinkedList是List接口的实现类
2. 底层数据结构是双链表，查询慢，增删快，但是如果是操作首尾元素，速度也很快
3. LinkedList无特殊的API，基本上都是实现List接口中的方法

LinkedList特有方法

由于LinkedList操作首尾元素的数据很快，所以在LinkedList中定义了自己特有的API操作首尾元素

public void addFirst(E e)   在列表开头插入指定元素
public void addLast(E e)    在列表末尾插入指定的元素
public E getFirst()         获取列表中的首元素
public E getLast()          获取列表中的尾元素
public E removeFirst()      删除列表中的首元素，并返回被删除的元素
public E removeLast()       删除列表中的尾元素，并返回被删除的元素

Set集合

1. Set是一个接口，Collection的子接口
2. Set集合：无序、不重复、无索引
3. Set集合没有特殊的API，基本上都是从Collection继承下来API
4. Set集合也没有特殊的遍历方式（迭代器、增强for、lambda）

由于Set集合是不重复的，所以当使用add()添加元素时，可能会添加失败

add()：当集合中存在指定的元素，则添加失败，返回false
       当集合中不存在指定的元素，则添加成功，返回true

Set<String> set = new HashSet<>();
boolean bool01 = set.add("张三");     // true
boolean bool02 = set.add("张三");     // false

HashSet

1. Set接口的实现类
2. 无特殊API，基本上与Set中的API一致
3. HashSet底层采取 哈希表 存储数据
4. 哈希表是一种对于 增删改查 数据性能都比较好的一种结构
5. 无序、不重复、无索引

哈希表

1. 哈希表的组成：
   JDK8之前：数组 + 链表
   JDK8开始：数组 + 链表 + 红黑树
2. 哈希值：
   根据hashCode方法算出来的int类型的整数
   该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
   一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
3. 对象的哈希值特点：
   如果没有重写hashCode方法，不同的对象（地址值）计算出来的哈希值是不同的
   如果已经重写hashCode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
   在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样（哈希碰撞）
4. 重写hasCode()：IDEA中快捷键 alt + insert，然后选择重写hasCode()即可（IDEA会生成重写代码）

HashSet底层原理：

1. JDK8以前底层原理：
   a. 创建一个默认长度16,默认加载因子为0.75的数组，数组名为tab的数组
       加载因子：当集合中存入的元素个数达到了 当前数组长度的 0.75倍时，此时数组的长度会扩容到当前数组的两倍
       如：当前数组长度为：16，加载因子为：0.75
       当集合中元素个数达到了 16 * 0.75 = 12 个时，数组扩容
       现在数组长度：16 * 2 = 32
   b. 根据元素的 哈希值 和 数组的长度 计算出该元素应存入的位置
   c. 判断当前位置是否为null
       如果是null直接存入
       如果位置不为null，表示该位置有元素了，则调用equals方法比较属性值
           一样：不存入
           不一样：存入数组，形成链表
           JDK8以前：新元素存入数组，老元素挂在新元素的下面
           JDK8以后，新元素直接挂在老元素下面
           当链表长度大于8，且数组长度大于等于64时，此时大于8的链表就会转成 红黑数 数据结构

注意：如果集合存储的是自定义对象，则自定义类中 要重写 hashCode 和 equals方法

原因：

1. HashSet集合在存储数据时，需要用hashCode()计算哈希值，如果没有重写hashCode()，则hashCode()根据地址值计算哈希值，无法根据对象的属性值计算哈希值
2. HashSet集合在存储数据时，需要使用equals()方法判断数组内的元素是否和当前存入元素是否相等，如果没有重写equals()，则根据地址值判断，重写了则是堆内存中的具体值比较

LinkedHashSet

特点：有序、不重复、无索引
底层结构：哈希表（与HashSet底层基本一致，区别：每个元素又额外的多了一个双链表的机制记录存储的顺序）

TreeSet

特点：可排序、不重复、无索引

1. 底层数据结构：红黑树
2. Java中，预定义类（String、Double、Integer等等）都是有实现Comparable接口的
3. 默认排序规则：
       a.数值型：默认按照从小到大的顺序排序
       b.字符、字符串：按照字符在ASCII表中的数字升序排序
4. 指定排序规则
       方式一：JavaBean类实现Comparable接口指定的比较规则
       方式二：创建TreeSet对象的时候，传递比较器Comparator指定规则
       注意：当类中实现了Comparable接口指定排序规则了，此时创建TreeSet对象时，又传入了Comparator指定排序规则，此时会优先使用创建对象时，传入的比较规则
       注意：Comparable与Comparator都是比较器：可以查阅资料，了解它们的区别

例题：
当集合存储的数据是自定义类，则自定义类要实现Comparable接口，指定排序规则

class Person implements Comparable<Person>{
    public String name;
    public int age;

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    // 重写比较规则的方法
    @Override
    public int compareTo(Person o) {
        // 一定要知道：TreeSet底层是 红黑数的数据结构，所以要知道红黑树是如何存数据和取数据的
        // 才能理解

        // 使用add 添加元素时，会调用 compareTo方法
        // 根据compareTo比较规则，将元素添加到对应的位置
        // 比较对象：
        //      当前添加的元素 与 集合中存在的元素 比较
        // compareTo的返回值：
        //  正数：表示当前添加的元素大，存在元素（集合中存在的）节点的右边
        //  负数：表示当前元素小，存在元素（集合中存在的）节点的左边
        //  0：表示在集合中已经存在该元素，添加失败


        /*
        * this：当前添加的元素
        * o：已经在集合中存在的元素
        * 返回值：
        *       负数：表示当前元素小，存在元素（集合中存在的）节点的左边
        *       正数：表示当前添加的元素大，存在元素（集合中存在的）节点的右边
        *        0：表示在集合中已经存在该元素，添加失败
        * 注意：
        *   在比较大小时，会多次调用该方法，直到找到 元素存储的位置（节点）
        * */
        // 按年龄比较
        int result = this.getAge() - o.getAge();
        return result;
    }
    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

TreeSet创建对象时，传入比较器指定比较规则

TreeSet<String> treeSet2 = new TreeSet<>(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            // o1：当前添加的元素
            // o2：集合中存在的元素
            // 根据字符串长度比较大小
            int result = o1.length() - o2.length();
            // 如果长度为0，则调用默认的比较方法比较
            if (result == 0) return o1.compareTo(o2);
            return result;
        }
    });

集合使用场景

1. 如果想要集合中的元素 可重复，建议使用ArrayList集合，基于数组的，ArrayList也是使用的最多的集合
2. 如果想要集合中的元素 可重复 且 当前的 增删 操作 明显多于 查询操作,用LinkedList集合，基于链表
3. 如果想对集合中的元素 去重,用HashSet集合，基于哈希表的，HashSet用的也比较多
4. 如果想对集合中的元素去重，而且保证 存取顺序,用LinkedHashSet集合，基于哈希表和双链表，效率低于HashSet
5. 如果想对集合中的元素进行 排序,用TreeSet集合，基于红黑树