集合和数组的对比小结
- 数组的长度是不可变的，集合的长度是可变的。
- 数组可以存基本数据类型和引用数据类型，集合只能存引用数据类型，如果要存基本数据类型，需要存对应的包装类。
集合类体系结构
Collection集合常用方法
| 方法名 | 说明 | | —- | —- | |boolean add(E e)| 添加元素 | |boolean remove(Object o)| 从集合中移除指定元素 | |boolean removeIf(Lambda表达式)| 根据条件进行删除 | |void clear()| 清空集合 | |boolean contains(Object o)| 判断集合中是否存在指定的元素 | |boolean isEmpty()| 判断集合是否为空 | |int size()| 集合的长度，也就是集合中元素的个数 |
Collection集合的遍历
Iterator：迭代器，集合的专用遍历方式
Iterator<E> iterator():返回集合中的迭代器对象，该迭代器对象默认指向当前集合的0索引
Iterator中的常用方法
boolean hasNext():判断当前位置是有有元素可以被取出E next():获取当前位置的元素，将迭代器对象移向下一个索引位置增强for循环
增强for：简化数组和Collection集合的遍历
它是JDK5之后出现的，其内部原理是一个Iterator迭代器
- 实现Iterator接口的类才可以使用迭代器和增强for
增强for的格式
for(元素数据类型 变量名 : 数组或者Collection集合){//在此处使用变量即可，该变量就是元素}
注意事项：修改第三方变量的值不会影响到集合中的元素
快捷生成方式：需要遍历的数组和集合.for
三种循环的使用场景
- 如果需要操作索引，使用普通for循环
- 如果在遍历的过程中需要删除元素，请使用迭代器
-
List集合
List集合概述
有序集合，这里的有序指的是存取顺序
- 用户可以精确控制列表中每个元素的插入位置，用户可以通过整数索引访问元素，并搜索列表中的元素
- 与Set集合不同，列表通常运行重复的元素
List集合特点
- 有序：存储和去除的元素顺序一致
- 有索引：可以通过索引操作元素
- 可重复：存储的元素可以重复
List集合特有方法
| 方法名 | 说明 | | —- | —- | |void add(int index,E element)| 在此集合中的指定位置插入指定的元素 | |E remove(int index)| 删除指定索引处的元素，返回被删除的元素 | |E set(int index,E element)| 修改指定索引处的元素，返回被修改的元素 | |E get(int index)| 返回指定索引处的元素 |
数据结构
数据结构是计算机存储，组织数据的方式。是指相互之间存在的一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率
- 栈
- 队列
- 数组
- 列表
栈：
数据进入栈模型的过程称为：压/进栈。
数据离开栈模型的过程称为：弹/出栈。
先进后出
队列：
数据从后端进入队列模型的过程称为：入队列
数据从前段离开队列模型的过程称为：出队列
先进先出
数组：
查询数据通过地址值和索引定位，查询任意数据耗时相同，查询速度快
删除数据时，要将原始数据删除，同时后面每个数据前移，删除效率低
添加数据时，添加位置后的每个数据后移，再添加元素，添加效率极低
链表
链表是一种增删快的模型（对比数组）
链表是一种查询慢的模型（对比数组）
单向链表和双向链表
List集合常用实现类
List集合常用子类：ArrayList，LinkedList
- ArrayList：底层数据结构是数组，查询快，增删慢
- LinkedList：底层数据结构是链表，查询慢，增删快
LinkedList集合的特有功能
| 方法名 | 说明 | | —- | —- | |public void addFirst(E e)| 在该列表开头插入指定的元素 | |public void addLast(E e)| 将指定的元素追加到此列表的末尾 | |public E getFirst()| 返回此列表中的第一个元素 | |public E getLast()| 返回此列表中的最后一个元素 | |public E removeFirst()| 从此列表中删除并返回第一个元素 | |public E removeLast()| 从此列表中删除并返回最后一个元素 |
Set集合
特点
- 可以去除重复
- 存取顺序不一致
没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取，删除Set集合里面的元素
TreeSet集合概述和特点
TreeSet集合特点
不包含重复元素的集合
- 没有带索引的方法
- 可以将元素按照规则进行排序
自然排序Comparable的使用
- 使用空参构造创建TreeSet集合
- 自定义的Student类实现Comparable接口
- 重写里面的compareTo方法
简单原理：
- 如果返回值为负数，表示当前存入的元素是较小值，存左边
- 如果返回值为0，表示当前存入的元素跟集合中元素重复了，不存
-
比较器排序Comparator的使用
TreeSet的带参构造方法使用的是比较器排序对元素进行排序的
- 比较器排序，就是让集合构造方法接收Comparator的实现类对象，重写
compare(T o1, T o2)方法 - 重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写
之间可以给TreeSet构造方法传入一个匿名内部类，或者Lambda表达式来实现Comparator。
两种比较方式小结
- 自然排序：自定义类实现Comparable接口，重写compareTo方法，根据返回值进行排序。
- 比较器排序：创建TreeSet对象的时候传递Comparator的实现类对象，重写compare方法，根据返回值进行排序。
- 在使用的时候，默认使用自然排序，当自然排序不满足现在的需求时，使用比较器排序。
数据结构-树
二叉树
二叉查找树
二叉查找树，又称为二叉排序树或者二叉搜索树
特点：
- 每个节点上最多有两个子节点
- 每个节点的左子节点都是小于自己的
- 每个节点的右子节点都是大于自己的
平衡二叉树
二叉树左右两个子树的高度差不超过1
任意节点的左右两个子树都是一颗平衡二叉树
平衡二叉树-左旋-右旋
左旋：就是将根节点的右侧往左侧拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点。
右旋：将根节点的左侧往右拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级根节点当左子节点。
小结
二叉查找树需要利用左旋和右旋机制保证树的平衡
注意点：
- 判断添加元素与当前节点的关系
- 成功添加之后，判断是否破坏了二叉树的平衡
旋转的四种情况
左左：当根节点左子树有节点插入，导致二叉树不平衡
左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡
右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡
右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡
红黑树
- 平衡二叉B树
- 每一个节点可以是红或者黑
- 红黑树不是高度平衡的，它的平衡是通过“自己的红黑规则”进行实现的
红黑规则
- 每一个节点或者是红色的，或者是黑色的
- 根节点必须是黑色
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性为Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的
- 如果一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
- 对每一个节点，从该节点到其他所有后代叶节点的简单路径上，均包含相同数目的黑色节点
简单路径：只能向下，不能回头
添加节点
- 添加的节点的颜色可以是红色的，也可以是黑色的
如果添加三个黑色节点，需要调整两次。
如果添加三个红色节点，需要调整一次。
所以，添加节点时，默认为红色，效率高。
红黑树在添加节点的时候：
添加的节点默认时红色的。
HashSet集合
HashSet集合特点
- 底层数据结构是哈希表
- 不能保证存储和取出的顺序完全一致
- 没有带索引的方法，所以不能使用普通for循环遍历
-
哈希值
哈希值（哈希码值）：是JDK根据对象的地址或者属性值，算出来的int类型的整数
Object类中有一个方法可以获取对象的哈希值 public int hashCode()：根据对象的地址值计算出来的哈希值
对象的哈希值特点
- 如果没有重写hashCode方法，那么是根据对象的地址值计算出来的哈希值。
同一个对象多次调用hashCode()方法返回的哈希值是相同的
不同对象的哈希值是不一样的。 - 如果重写了hashCode方法，一般都是通过对象的属性值计算出哈希值。
如果不同的对象属性值是一样的，那么计算出来的哈希值也是一样的。HashSet1.7版本原理
底层结构：哈希表（数组 + 链表）
- 创建一个默认长度16，默认加载因数为0.75的数组，数组名table
- 根据元素的哈希值根数组的长度计算出应存入的位置
- 判断当前位置是否为null，如果是null直接存入
- 如果存入的位置不为null，表示有元素，则调用equals方法比较属性值
- 如果一样，则不存，如果不一样，则存入数组，老元素挂在新元素下面
- 当数组里面存了16*0.75=12个元素的时候，数组就会扩容为原先的两倍
HashSet1.8版本
底层结构：哈希表。（数组、链表、红黑树的结合体）。
当挂在下面的元素过多，那么不利于添加，也不利于查询，所以在JDK8以后
当链表长度超过8的时候，自动转换为红黑树
如果HashSet集合要存储自定义对象，那么必须重写hashCode和equals方法。Set集合小结
Map集合
- Interface Map
- 键不能重复，值可以重复
- 键和值是一一对应的，每一个键只能找到自己对应的值
- （键 + 值）这个整体 我们称之为“键值对”或者“键值对对象”，在Java中叫做“Entry对象”
Map集合的基本功能
| 方法名 | 说明 | | —- | —- | |V put(K key,V value)| 添加元素 | |V remove(Object key)| 根据键删除键值对元素 | |void clear()| 移除所有的键值对元素 | |boolean containsKey(Object key)| 判断集合是否包含指定的键 | |boolean containsValue(Object value)| 判断集合是否包含指定的值 | |boolean isEmpty()| 判断集合是否为空 | |int size()| 集合的长度，也就是集合中键值对的个数 |
第一种遍历方式
- 获取到所有的键
- 遍历Set集合的到每一个键
- 通过每一个键key，来获取到对应的值
| 方法名 | 说明 |
| —- | —- |
|
Set<K> keySet()| 获取所有的键的集合 | |V get(Object key)| 根据键获取值 |
第二种遍历方式
- 要获取到所有的键值对对象
- Set集合中装的是键值对对象（Entry对象）
- Entry里装的是键和值
| 方法名 | 说明 |
| —- | —- |
|
Set<Map.Entry<K,V>> entrySet()| 获取所有的键值对对象的集合 | |K getKey()| 获得键 | |V getValue()| 获得值 |
第三种遍历方式forEach(Lambda表达式)
map.forEach(
(String key,String value) ->{
System.out.println(key + value + "");
}
);
HashMap小结
- HashMap底层是哈希表结构的，以键值对的形式存储
- 依赖hashCode方法和equals方法保证键的唯一
如果键要存储的是自定义对象，需要重写hashCode和equals方法
TreeMap小结
TreeMap底层是红黑树结构的
- 依赖自然排序或者比较器排序，对键进行排序
如果键存储的是自定义对象，需要实现Comparable接口或者在创建TreeMap对象时候给出比较器排序规则
可变参数
可变参数：就是形参的个数是可以变化的
格式：
修饰符 返回值类型 方法名(数据类型...变量名){}- 范例：
public static int sum(int...a){}
注意事项：
若有收获，就点个赞吧
0 人点赞
