笔记五：Collection集合

集合

集合包含Collection集合和Map集合，Collection是单列集合，每个元素（数据）只包含一个值。Map是双列集合，每个元素包含两个值（键值对）。这里我们主要掌握Collection集合体系的使用。

与数组之间的比较

• 不像数组一样，集合的类型和长度都不固定
• 适合元素个数不确定，且需要做元素的增删操作的场景
• 集合提供的种类特别丰富，功能也是十分强大，开发中集合用的更多

Collection集合特点

• List系列集合：添加的元素是有序、可重复、有索引。

  • 如ArrayList、LinekdList ：有序、可重复、有索引。

• Set系列集合：添加的元素是无序、不重复、无索引。

  • HashSet: 无序、不重复、无索引
  • LinkedHashSet: 有序、不重复、无索引。
  • TreeSet：按照大小默认升序排序、不重复、无索引。

注意：

• 集合都是泛型的形式，可以在编译阶段约束集合只能操作某种数据类型

Collection<String> lists = new ArrayList<String>();
Collection<String> lists = new ArrayList<>(); // JDK 1.7开始后面的泛型类型申明可以省略不写

• 集合和泛型都只能支持引用数据类型，不支持基本数据类型，所以集合中存储的元素都认为是对象，如果集合中要存储基本数据类型，就必须使用包装类，也就是基本数据类型对应的引用数据类型

Collection常用API

方法名称	说明
public boolean add(E e)	把给定的对象添加到当前集合中
public void clear()	清空集合中所有的元素
public boolean remove(E e)	把给定的对象在当前集合中删除
public boolean contains(Object obj)	判断当前集合中是否包含给定的对象
public boolean isEmpty()	判断当前集合是否为空
public int size()	返回集合中元素的个数。
public Object[] toArray()	把集合中的元素，存储到数组中

Collection集合的遍历方式

①迭代器遍历

• 遍历就是一个一个的把容器中的元素访问一遍
• 迭代器在Java中的代表是Iterator，迭代器是集合的专用的遍历方式

获取迭代器：Iterator<\E> iterator() ， 返回集合中的迭代器对象，该迭代器对象默认指向当前集合的0索引

Iterator中的常用方法：boolean hasNext()，询问当前位置是否有元素存在，存在返回true ，不存在返回false；E next()，获取当前位置的元素，并同时将迭代器对象移向下一个位置，注意防止取出越界，否则会出现NoSuchElementException异常

②增强for循环：既可以遍历集合也可以遍历数组

使用格式如下：

for(元素数据类型 变量名 : 数组或者Collection集合) {
         //在此处使用变量即可，该变量就是元素
}

// 举例：
Collection<String> list = new ArrayList<>();
...
for(String str : list) {
    System.out.println(str);
}

③Lambda表达式遍历集合

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

Collection<String> lists = new ArrayList<>();
...
lists.forEach(new Consumer<String>() {
    @Override
    public void accept(String s) {
        System.out.println(s);
    }
});

// 上面可以用Lambda表达式简化为：
lists.forEach(s -> {
    System.out.println(s);
});
// 进一步可以简化为： 
lists.forEach(s -> System.out.println(s));

Collection集合存储自定义类型的对象

以一个电影对象为例子，代码如下：

①定义一个Movie类

public class Movie {
    private String name;
    private double score;
    private String acotr;
    public Movie(String name, double score, String acotr) {
        this.name = name;
        this.score = score;
        this.acotr = acotr;
    }
    // ... getter + setter}

②定义一个Movie类型的Collection集合，调用遍历方法

public class Demo {
    public static void main(String[] args) {
        Collection <Movie> movies = new ArrayList<>();
        movies.add(new Movie(“《肖生克的救赎》”, 9.7 ,  “罗宾斯”));
        movies.add(new Movie(“《霸王别姬》”, 9.6 ,  “张国荣、张丰毅”));
        movies.add(new Movie(“《阿甘正传》”, 9.5 ,  “汤姆、汉克斯”));
        for (Movie movie : movies) {
            System.out.println("片名：" + movie.getName());
            System.out.println("评分：" + movie.getScore());
            System.out.println("主演：" + movie.getAcotr());
        }
    }
}

数据结构

定义：数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率

常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树……

• 队列：先进先出，后进后出
• 栈：后进先出，先进后出
• 数组：内存连续区域，查询快，增删慢
• 链表：元素是游离的，查询慢，首尾操作极快
• 二叉树：永远只有一个根节点, 每个结点不超过2个子节点的树
• 查找二叉树：小的左边，大的右边，但是可能树很高，查询性能变差
• 平衡查找二叉树：让树的高度差不大于1，增删改查都提高了
• 红黑树（就是基于红黑规则实现了自平衡的排序二叉树）

List系列集合

特点：ArrayList、LinekdList ：有序，可重复，有索引

• ArrayList底层是基于数组实现的，查询元素快，增删相对慢
• LinkedList底层基于双链表实现的，查询元素慢，增删首尾元素是非常快的

特有方法：List集合因为支持索引，所以多了很多索引操作的独特API，其他Collection的功能List也都继承了

方法名称	说明
void add(int index,E element)	在此集合中的指定位置插入指定的元素
E remove(int index)	删除指定索引处的元素，返回被删除的元素
E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
E get(int index)	返回指定索引处的元素

注意：

• 由于List集合存在索引，因此List集合的遍历方式在Collection集合遍历方式的基础上多了for循环
• 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集合

Set集合功能上基本与Collection的API一致，它的特点是添加的元素是无序、不重复、无索引。

• HashSet: 无序、不重复、无索引
• LinkedHashSet: 有序、不重复、无索引，这里的有序指的是保证存储和取出的元素顺序一致
• TreeSet：按照大小默认升序排序、不重复、无索引

HashSet

底层原理：HashSet集合底层采取哈希表存储的数据，哈希表是一种对于增删改查数据性能都较好的结构。

哈希表的组成：JDK8之前的，底层使用数组+链表组成；JDK8开始后，底层采用数组+链表+红黑树组成。

在了解哈希表之前需要先理解哈希值的概念，哈希值是JDK根据对象的地址，按照某种规则算出来的int类型的数值。对应Object类的API：public int hashCode()，返回对象的哈希值

对象哈希值的特点：同一个对象对此调用hashCode()方法返回的哈希值是相同的。默认情况下，不同对象的哈希值是不同的

哈希表的详细流程：

①创建一个默认长度16，默认加载因为0.75的数组，数组名table

② 根据元素的哈希值跟数组的长度计算出应存入的位置（哈希算法）

③ 判断当前位置是否为null，如果是null直接存入，如果位置不为null，表示有元素， 则调用equals方法比较属性值，如果一样，则不存，如果不一样，则存入数组。

④ 当数组存满到16*0.75=12时，就自动扩容，每次扩容原先的两倍

注意：哈希表是一种对于增删改查数据性能都较好的结构。从JDK8开始后，当链表长度超过8的时候，自动转换为红黑树，红黑树的引入进一步提高了操作数据的性能。

LinkedHashSet

底层原理：底层数据结构依然是哈希表，只是每个元素又额外多了一个双链表的机制记录存储的顺序

TreeSet

底层原理：底层是基于红黑树的数据结构实现排序的，增删改查性能都较好。TreeSet集合是一定要排序的，可以将元素按照指定的规则进行排序

默认的规则：

• 对于数值类型：Integer , Double，官方默认按照大小进行升序排序

• 对于字符串类型：默认按照首字符的编号升序排序

• 对于自定义类型如Student对象，TreeSet无法直接排序。想要存储自定义类型，必须自己制定排序规则

TreeSet集合存储对象的的时候有2种方式可以设计自定义比较规则

①让自定义的类实现Comparable接口重写里面的compareTo方法来定制比较规则

②TreeSet集合有参数构造器，可以设置Comparator接口对应的比较器对象，来定制比较规则

以上两种方式关于返回值的规则如下：

• 如果认为第一个元素大于第二个元素返回正整数即可。

• 如果认为第一个元素小于第二个元素返回负整数即可。

• 如果认为第一个元素等于第二个元素返回0即可，此时Treeset集合只会保留一个元素，认为两者重复

• 如果TreeSet集合存储的对象有实现比较规则，集合也自带比较器，默认使用集合自带的比较器排序

Collections集合工具类

作用：Collections并不属于集合，是用来操作集合的工具类

常用API：

方法名称	说明
public static <T> boolean addAll(Collection<? super T> c, T… elements)	给集合对象批量添加元素
public static void shuffle(List<?> list)	打乱List集合元素的顺序

排序相关API：只能对List集合进行排序

• 排序方式1：public static <T> void sort(List<T> list)，将集合中元素按照默认规则排序。该方式不可以直接对自定义类型的List集合排序，除非自定义类型实现了比较规则Comparable接口
• 排序方式2：public static <T> void sort(List<T> list，Comparator<? super T> c)，将集合中的元素按照指定规则排序