- List系列集合：有序，可重复，有索引
- Set系列集合：无序，不重复，无索引
Collection
- contains对象一定要重写equals方法
Collection遍历方式
迭代器遍历: Iterator
迭代器遍历完毕，指针不会复位
迭代器遍历时，不能用集合的方法进行增加或删除
增强for遍历：底层为Iterator迭代器
lambda表达式遍历: forEach()方法
List集合
- 遍历方式
ArrayList底层原理
- 利用空参创建的集合，在底层创建一个默认长度为0的数组
- 添加第一个元素时，底层会创建一个新的长度为10的数组
- 存满时，会扩充为1.5倍
- 如果一次添加多个元素，1.5倍还放不下，则创建数组的长度以实际为准
LinkedList底层原理
- 双向链表，查询慢，增删快
- 多个首尾元素API
泛型
泛型类
泛型方法: 方法中形参类型不确定时，使用类名后面定义的泛型；在方法声明上加上自己的泛型；
泛型接口：实现类给出具体的泛型；实现类延续泛型
泛型不具备继承，通配符：?，有两种用法：? extends E; ? super E: 可以限定类型的范围
树
- 度：每个节点的子节点数量
- 树高：树的总层数
二叉查找树
- 每个节点至多有两个子节点
- 任意节点的左子树一定小于该节点
- 任意节点的右子树一定大于该节点
- 遍历方式：前序：根左右，中序：左根右，后序：左右根，层次：一层一层遍历
平衡二叉树
- 任意节点左右子树高度差不超过1
- 左旋：以不平衡点为支点，把支点左旋降级，变成左子节点，并晋升原来的右子节点；原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
- 右旋：以不平衡的点作为支点，把支点右旋降级，变成右子节点，晋升原来的左子节点；原先的左子节点变成新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点
- 左左：一次右旋；左右：先局部左旋，后整体右旋；右右：一次左旋；右左：先局部右旋，后整体左旋
红黑树
- 一种特殊的二叉查找树，每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过”红黑规则”进行实现的
- 红黑规则：每一个节点或是红色的，或者是黑色的；根节点必须是黑色；如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的；如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）；对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；
- 添加的节点默认是红色（效率高）
Set集合
- set实现类的特点：HashSet：无序、不重复、无索引；LinkedHashSet：有序、不重复、无索引；TreeSet：可排序、不重复、无索引；
HashSet底层原理
- HashSet集合底层采取哈希表存储数据
- 哈希表是一种对于增删改查数据性能都较好的结构 JDK8以前：数组+链表；JDK8以后：数组+链表+红黑树
哈希值
- 根据hashCode方法算出来的int类型的整数
- 该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
- 一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
- 如果没有重写hashCode方法，不同对象计算出的哈希值是不同的
- 如果已经重写hashcode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
- 在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。（哈希碰撞）
- 当链表长度大于8而且数组长度大于等于64 链表转成红黑树
- 如果集合中存储的是自定义对象，必须要重写hashCode和equals方法
LinkedHashSet底层原理
- 有序，不重复，无索引
- 底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序
TreeSet底层原理
- 不重复，无索引，可排序
- 底层：红黑树
Map常用API
- Map是双列集合的顶层接口，它的功能是全部双列集合都可以继承使用的
- Map遍历方式：键找值，获取所有的键，用get方法进行遍历；键值对：entrySet方法；Lambda表达式：forEach()方法
HashMap
- HashMap是Map里面的一个实现类
- HashMap跟HashSet底层原理是一模一样的，都是哈希表结构
- 如果键的值是一样的，就覆盖；否则直接挂在到旧元素下面
- 当链表长度大于8而且数组长度大于等于64 链表转成红黑树
- 如果键存储的是自定义对象，需要重写hashCode和equals方法
- 如果值存储自定义对象，不需要重写hashCode和equals方法
TreeMap
- 有序，不重复，无索引
- 用双链表机制记录存储
- TreeMap跟TreeSet底层原理一样，都是红黑树结构
- 由键决定特性：不重复、无索引、可排序
- 可排序：对键进行排序
- 排序方式：实现Comparable接口，指定比较规则；创建集合时传递Comparator比较器对象，指定比较规则；
不可变集合
- 不能增删改
- Map.of最多只能接受10个键值对，ofEntries可以接受多个
