集合

单列集合

单列集合的特点

List集合系列元素：有序，可重复，有索引
Set集合系列元素：无序，不重复，无索引

集合和数组的对比

数组长度固定，既可以存基本数据类型，又可以存引用数据类型
集合长度可变，可以存引用数据类型，基本数据类型需要转为其包装类

泛型

不指定泛型

如果在创建集合的时候不指定泛型，默认认为所有的数据都是object类型，这意味着可以往该集合中添加任意类型的数据，但是这使得在获取数据的时候，无法使用该数据类型的特有方法（多态的弊端）

作用

1.统一数据类型
2.把运行时期的问题提前到了编译期间，避免了强制类型转换可能出现的异常，因为在编译期间类型就能确定

细节

1.泛型中不能写基本数据类型
2.指定泛型的基本类型后，传递数据时，可以传入该类类型或其子类类型
3.不写泛型，类型默认是Object

使用位置

泛型类

当一个类中，某个变量的数据类型不确定时，可以定义带有泛型的类,但在使用时，应该给泛型一个确定的数据类型

public class ArrayList<E> {

}

泛型方法

方法中形参不确定时，可以使用类名后面定义的泛型，所有方法都能使用；
也可以在方法申明上定义自己的泛型，只有本方法可以使用

public class MyArrayList {
	publid <E> boolean add(E e){
		obj[size] = e;
		size++;
		return true;
	}
}

泛型接口

public interface List<E> {

}

使用方法：
1.实现类给出具体类型
2.实现类延续泛型，创建对象时再确定

泛型通配符

在使用泛型时，虽然不确定类型，但是有时会希望只能传递某一个继承链中的数据类型，此时可以使用泛型通配符
? 表示不确定的类型
? extends E 表示可以传递E或E的所有子类类型
? super E 表示可以传递E或E的所有父类类型

Collection的常见API

Collection是一个接口，不能直接创建其对象

部分方法的细节

1.添加元素 add()
如果我们要往List系列集合中添加数据，那么方法永远返回true，因为List系列的是允许元素重复的。
如果我们受往Set系列集合中添加数据，如果当前要添加元素不存在，方法返回true，表示添加成功。
如果当前要添加的元素已经存在。方法返回false。表示添加失败。因为Set系列的集合不允许重复。
2…删除元素 remove()
因为Collection里面定义的是共性的方法，所以此时不能通过索引进行剧除。只能通过元素的对象进行删除。
方法会有一个布尔类型的返回值。删除成功返回true，删除失败返回false；如果要剧除的元素不存在，剧除失败。
3.判断集合是否包含 contains（）
底层是依赖equals方法进行刘断是否存在的。所以，如果集合中存储的是自定义对象，也想通过contains方法来判断是否包含，那么在javabean类中，一定要重写equals方法。

集合的遍历

迭代器遍历

迭代器的三个方法

Iterator< E > iterator() : 获取一个迭代器对象
boolean hasNext() : 判断当前指向的位置是否有元素
E next() : 获取当前指向的元素并移动指针

Iterator<String> it = coll.iterator();
while(it.hasNext()){
	string str = it.next();
	System.out.println(str);
}

报错NoSuchElementException指针已经指向集合最后没有元素的位置
迭代器遍历完毕，指针不会复位（要第二次遍历，只能获取新的迭代器对象）
循环中只能用一次next方法（元素数目为奇数时报错NoSuchElementException）
迭代器遍历时，不能用集合的方法进行增加或者删除（迭代器有remove方法删除指向的元素）

增强for遍历

其本质是迭代器遍历，更便于书写,单列集合和数组才可以使用

//idea中的快速生成方法，集合名字.for
for(string s: list) {//s是一个第三方变量，在循环的过程中依次表示集合中的每一个数据
	system.out.println(s);
}

在for中修改变量的值，修改的是第三方变量的值，不会影响原来的值

lambda表达式

匿名内部类方式：

//遍历集合依次得到每一个元素,把得到的每一个元素,传递给下面的accept方法
//s依次表示集合中的每一个数据
coll.forEach(new consumer<String>(){
@override
	public void accept(String s) {
		System.out.println(s);
	}
}

lambda表达式方式：

删除格式部分，加上箭头，数据类型省略，只有一个变量时小括号省略，方法体只有一行代码时大括号省略

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

总结：在遍历过程中想要删除元素，用迭代器，仅仅想要遍历，用增强for或lambda表达式

List

特有方法（索引相关）

1.添加元素 add（）
在指定位置插入元素，原来位置上的元素后移
2.删除元素 remove（）
删除指定索引处的元素，返回被删除的元素
重载方法remove（object o）；删除指定元素，返回是否删除成功
3.修改元素 set（）
修改指定索引处的元素，返回被修改的元素
4.获取元素 get（）
返回指定索引处的元素

遍历方法

1.迭代器遍历
2.增强for遍历
3.lambda表达式
4.普通for遍历
5.列表迭代器遍历
获取一个列表迭代器对象，里面的指针默认指向0
add，next，hasnext，remove
添加和修改时要用迭代器的方法

五种遍历方式对比

迭代器遍历 在遍历的过程中需要删除元素，请使用迭代器。
列表迭代器 在遍历的过程中需要添加元素，请使用列表迭代器。
增强for遍历、Lambda表达式 仅仅想遍历，那么使用增强for或Lambda表达式。
普通for 如果遍历的时候想操作索引，可以用普通for。

ArrayList

创建

ArrayList<?> list = new ArrayList<String>();

打印ArrayList中的数据时，由于java底层对其进行了处理
打印出的不是地址值，而是集合中存储的数据，展示时会用[ ]把所有的数据进行包裹，并在数据间加上”，“

常用方法

底层原理

1.利用空参创建的集合，在底层创建一个默认长度为0的数组
2.添加第一个元素时，底层会创建一个新的长度为10的数组
3.存满时，会扩容1.5倍
4.如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度以实际为准
集合进阶-06-ArrayList源码分析_哔哩哔哩_bilibili

LinkedList

常用方法

底层原理

底层是双链表，查询慢，增删快，如果操作的是首尾元素，速度也是极快的
集合进阶07-LinkedList和迭代器的源码分析_哔哩哔哩_bilibili

数据结构：树

二叉树

度:每一个节点的子节点数量
树高:树的总层数
根节点:最顶层的节点
左子节点:左下方的节点
右子节点:右下方的节点
根节点的左子树:蓝色虚线
根节点的右子树:绿色虚线

二叉查找树

每一个节点上最多有两个子节点
任意节点左子树上的值都小于当前节点
任意节点右子树上的值都大于当前节点

二叉树的遍历

前序遍历：当前->左->右
中序遍历：左->当前->右
后序遍历：左->右->当前
层序遍历：从根节点开始一层一层遍历

平衡二叉树

任意节点的左右子树高度差不超过1

左旋和右旋

触发时机，当添加一个节点后，该树不再是一棵平衡二叉树
左旋：
1.从添加的节点开始，不断的往父节点找不平衡的节点，以不平衡的点作为支点
2.把支点左旋降级，变成左子节点
3.原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
右旋：
1.从添加的节点开始，不断的往父节点找不平衡的节点，以不平衡的点作为支点
2.把支点右旋降级，变成右子节点
3.原先的左子节点变成新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点

红黑树

1.红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
2.它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色
3.每一个节点可以是红或者黑;红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的

红黑规则

1.每一个节点或是红色的，或者是黑色的
2.根节点必须是黑色
3.如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的
4.如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
5.对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点;

添加节点的规则

Set

特点：
1.无序：存取顺序不一致
2.不重复：可以去除重复
3.无索引：没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引获取元素
Set接口中的方法基本与collection中的API一致（没有自己的方法）

HashSet

无序、不重复、无索引

底层原理

1.HashSet集合底层采取哈希表存储数据
2.哈希表是一种对于增删改查数据性能都较好的结构
在JDK8之前，采用数组+链表
从JDK8开始，采用数组+链表+红黑树

创建过程

1.创建一个默认长度16，默认加载因子为0.75的数组，数组名table
2.根据元素的哈希值跟数组的长度计算出应存入的位置
3.判断当前位置是否为null，如果是null直接存入
如果位置不为null，表示有元素，则调用equals方法比较属性值
一样:不存；不一样:存入数组，形成链表
JDK8以前:新元素存入数组，老元素挂在新元素下面
JDK8以后:新元素直接挂在老元素下面

哈希值

1.根据hashcode方法算出来的int类型的整数
2.该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
3.一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
如果没有重写hashCode方法，不同对象计算出的哈希值是不同的
如果已经重写hashcode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。(哈希碰撞)

一些问题

1.HashSet集合的底层数据结构是什么样的?
数组+链表（+红黑树）
2.HashSet添加元素的过程?
数组->链表->红黑树
3.HashSet为什么存和取的顺序不一样?
哈希值计算出来的数组序号不是按顺序排列的
4.HashSet为什么没有索引?
数组每个索引下都有链表，链表中每个数据在数组中的索引是相同的
5.HashSet是利用什么机制保证去重的?
利用hashcode和equals方法
因此如果向HashSet中存储自定义对象时，必须要重写这两个方法以达到去重的目的

LinkedHashSet

有序、不重复、无索引

底层原理

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

TreeSet

可排序、不重复、无索引

底层原理

底层是基于红黑树的数据结构实现排序的，增删改查性能都较好

排序方式

默认排序方式

使用TreeSet存储数据后读取时，如果不指定排序方式，java会按照默认的顺序排序后输出
对于数值类型: Integer , Double，默认按照从小到大的顺序进行排序。对于字符、字符串类型:按照字符在ASCII码表中的数字升序进行排序。

实现Comparable接口

对于自定义对象或者想要指定排序方式的数值、字符类型的对象，可以通过实现Comparable接口来指定排序方式

@Override
public int compareTo(Student o) {
//指定排序的规则
//只看年龄，我想要按照年龄的升序进行排列
//this表示当前要添加的元素；o表示已经在红黑树中存在的元素
//返回值为负数，认为当前添加的元素是小的，存左边
//返回值为正数，认为当前添加的元素是大的，存右边
//0，当前元素已经存在，舍弃
	return this.getAge() - o.getAge();
)

传递比较器Comparator

当实现Comparable接口无法满足需求时，可以在创建TreeSet对象的时候，传递比较器Comparator(匿名内部类对象)指定规则

//后续可以简化为Lambda表达式
TreeSet<string> ts = new Treeset<>(new comparator<String>() {
	@Override
	public int compare(string o1，string o2){
		//按照长度排序
		int i = o1.length() - o2.length();
		//如果一样长则按照首字母排序
		i = i == 0 ? o1.compareTo(o2) : i;
		return i;
	}
});

对比选择

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

双列集合

双列集合的特点

1.双列集合一次需要存一对数据,分别为键和值
2.键不能重复，值可以重复
3.键和值是一一对应的，每一个键只能找到自己对应的值
4.键＋值这个整体我们称之为“键值对”或者“键值对对象”，在Java中叫做“Entry对象”

Map的常见API

部分方法的细节

put() 添加或覆盖
在添加数据的时候，如果键不存在，那么直接把键值对对象添加到map集合当中,方法返回null
在添加数据的时候，如果键是存在的，那么会把原有的键值对对象覆盖，会把被覆盖的值进行返回。

Map的遍历

键找值

先通过keySet()方法获取每一个键，再通过键寻找到每一个值，从而遍历
可以采用增强for，迭代器和lambda表达式的方法

键值对

通过entrySet()方法获取所有的键值对对象，返回一个Set集合
可以采用增强for，迭代器和lambda表达式的方法

Lambda表达式

//forEach的底层就是利用键值对的方法遍历的
map.forEach(new BiC onsumer<String,String>(){
	@Override
	public void accept(String key,String value){
		System.out.println(key + "=” + value);
	}
});	
//可以简化为Lambda表达式
map.forEach((key,value)->System.out.println(key+ "=" +value));

HashMap

1.HashMap是Map里面的一个实现类。
2.没有额外需要学习的特有方法，直接使用Map里面的方法就可以了。
3.特点都是由键决定的:无序、不重复、无索引
4.HashMap跟HashSet底层原理是一模一样的，都是哈希表结构
链表长度超过8且数组长度超过64时，会自动转为红黑树
5.依赖hashcode方法和equals方法保证键的唯一
如果键存储的是自定义对象，需要重写hashCode和equals方法
如果值存储的是自定义对象,，不需要重写hashCode和equals方法

LinkedHashMap

1.由键决定:有序、不重复、无索引
2.这里的有序指的是保证存储和取出的元素顺序一致
3.原理︰底层数据结构是依然哈希表，只是每个键值对元素又额外的多了一个双链表的机制记录存储的顺序。

TreeMap

1.TreeMap跟TreeSet底层原理一样，都是红黑树结构的，增删改查性能好
2.由键决定特性:不重复、无索引、可排序
3.可排序:对键进行排序
默认按照键的从小到大进行排序，也可以自己规定键的排序规则（实现Comparable接口、传递比较器Comparator）

可变参数

方法形参的个数可以发生变化
格式：属性类型…名字（int…args）
它的底层就是一个数组，只不过不用我们自己创建
注意：
1.方法的形参中最多只能写一个可变参数
2.在方法参数中，如果除了可变参数还有其他参数，可变参数要作为最后一个参数

Collections

不是集合，是一个工具类

常用API：