Java集合类API详解
单列集合
一次添加一个数据的集合。它们的根接口是Collection，具体体系如图：
List系列集合的特点：添加的元素是有序、可重复、有索引的。也即存和取的顺序是一致的；包含的元素是可以有重复的；包含的元素是有索引的，可以通过索引对元素进行操作。
Set系列集合的特点：添加的元素是无序、不重复、无索引。也即存和取的顺序有可能是不一样的；包含的元素是不能也不会有重复，也即元素是唯一的；包含的元素是无索引的，不能通过索引对元素进行操作。
祖宗接口Collection
Collection是单列集合的祖宗接口（顶层接口），它的功能是全部单列集合都可以继承使用的。
方法名称 | 说明 |
public booleanadd(E e) | 把给定的对象添加到当前集合中 |
public void clear() | 清空集合中所有的元素 |
public boolean remove(E e) | 把给定的对象在当前集合中删除 |
public boolean contains(Object obj) | 判断当前集合中是否包含给定的对象 |
public boolean isEmpty() | 判断当前集合是否为空 |
public int size() | 返回集合中元素的个数/集合的长度 |
add方法
add方法的返回值是一个boolean，如果是往List对象中添加数据，由于List允许重复，所以永远返回true；而对于Set对象，如果添加的元素不存在，返回true，表示添加成功，否则返回false，表示添加失败。
clear方法
清空集合中所有的元素。
remove方法
删除一个元素。返回布尔类型，删除成功返回true，删除失败返回false。如果要删除的元素不存在，那么就会删除失败。
contains方法
判断是否包含某个元素。该方法底层是依赖equals方法进行判断是否存在，所以，如果集合中存储的是自定义对象，也想通过contains方法来判断是否包含，那么再JavaBean类中，需要重写equals方法。
Idea中查看具体实现类的源码，比如点击contains()方法，右击 - Goto - Implementation即可。
isEmpty方法
判断集合是否为空，如果长度为0则返回true，否则返回false。
size方法
获取集合的长度。
基本方法演示代码
import java.util.ArrayList;
import java.util.Collection;
public class CollectionDemo {
public static void main(String[] args) {
// Collection是个接口，不能直接实例化
Collection<String> collection = new ArrayList<>();
// 1.添加元素
collection.add("Hi!Collection.");
collection.add("aaa");
collection.add("bbb");
collection.add("ccc");
System.out.println(collection); // [Hi!Collection., aaa, bbb, ccc]
// 2. 清空集合
//collection.clear();
//System.out.println(collection); // []
// 3. 删除
// 如果是Collection的对象，那么不能通过索引操作元素，只能通过元素的对象进行删除
collection.remove("Hi!Collection.");
System.out.println(collection); // [aaa, bbb, ccc]
// 4. 判断集合是否包含某个元素
boolean isContained1 = collection.contains("Hi!Collection.");
boolean isContained2 = collection.contains("aaa");
System.out.println(isContained1); // false
System.out.println(isContained2); // true
// 5. 判断集合是否为空
boolean isEmpty = collection.isEmpty();
System.out.println(isEmpty); // flase
// 6.获取集合的长度
int size = collection.size();
System.out.println(size); // 3
}
}
Collection的遍历方式
有三种通用的遍历方法：迭代器遍历，增强for遍历，Lambda表达式遍历。
迭代器遍历
迭代器用于获取集合里的每一个元素，它不依赖与索引。迭代器在Java中的类是Iterator,迭代器是集合专用的遍历方式。
Collection集合获取迭代器
方法名称 | 说明 |
Iterator<E>iterator() | 返回迭代器对象，默认指向当前集合的0索引 |
Iterator中的常用方法
方法名称 | 说明 |
boolean hasNext() | 判断当前位置是否有元素，有元素返回true,没有元素返回false |
Enext() | 获取当前位置的元素，并将迭代器对象移向下一个位置。 |
迭代器使用示例：
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class IteratorTest {
public static void main(String[] args) {
// 1.创建集合并添加元素
Collection<String> collection = new ArrayList<>();
collection.add("aaa");
collection.add("bbb");
collection.add("ccc");
collection.add("ddd");
collection.add("eee");
// 2.获取迭代器
Iterator<String> iter = collection.iterator();
// 3.利用迭代器循环遍历集合中的每一个元素
while (iter.hasNext()){
// next方法，获取元素并移动指针
String str = iter.next();
System.out.println(str);
}
}
}
迭代器注意事项
- 迭代器到达末尾会报错NoSuchElementException
- 迭代器遍历完毕，指针不会复位（如果我们需要第二次遍历集合，只能再次获取一个新的迭代器）
- 循环中只能用一次next方法（循环中可以多次调用next方法，但是指针会停留在非预期的位置上，从而造成异常）
- 迭代器遍历的过程中，不能用集合的方法进行增加或者删除（在迭代时不能使用集合的删除方法，需要用迭代器里的remove方法删除元素）
小结
1.迭代器在遍历集合的时候是不依赖索引的
2.迭代器需要掌握三个方法：
Iterator<String> iter =list.iterator();
while(iter.hasNext()){
String str =iter.next();System.out.println(str);
}
3.迭代器的四个细节：
●如果当前位置没有元素，还要强行获取，会报NoSuchElementException
●迭代器遍历完毕，指针不会复位
●循环中只能用一次next方法
●迭代器遍历时，不能用集合的方法进行增加或者删除
增强for遍历
- 增强for的底层就是迭代器，为了简化迭代器的代码书写的。
- 它是JDK5之后出现的，其内部原理就是一个lterator迭代器
- 所有的单列集合和数组才能用增强for进行遍历。
格式：
for(元素的数据类型 变量名：数组或者集合){
}
for(String s : list){
System.out.println(s);
}
例如：
import java.util.ArrayList;
import java.util.Collection;
public class ForeachTest {
public static void main(String[] args) {
// 1.创建集合并添加元素
Collection<String> collection = new ArrayList<>();
collection.add("aaa");
collection.add("bbb");
collection.add("ccc");
collection.add("ddd");
collection.add("eee");
// 2.利用增强for遍历
for (String s : collection) {
System.out.println(s);
}
}
}
注意点：修改增强for中的变量，不会改变集合中原本的数据。上例中的变量s只是个第三方变量，更改它的值并不会修改集合元素的值。
Labmda表达式遍历
lambda表达式遍历，也即使用Collection类的forEach方法，并使用匿名类或lambda实现参数的功能接口Consumer。
default void forEach(Consumer<? super T> action);
代码如下：
import java.util.ArrayList;
import java.util.Collection;
import java.util.function.Consumer;
public class LambdaTest {
public static void main(String[] args) {
// 1.创建集合并添加元素
Collection<String> collection = new ArrayList<>();
collection.add("aaa");
collection.add("bbb");
collection.add("ccc");
collection.add("ddd");
collection.add("eee");
// 2-1. 利用匿名内部类遍历
collection.forEach(new Consumer<String>() {
@Override
public void accept(String s) {
System.out.println(s);
}
});
System.out.println("-----------");
// 2-2. 利用lambda遍历
collection.forEach((String s) -> {
System.out.println(s);
}
);
System.out.println("-----------");
// 2-3. 利用lambda遍历（简化代码）
collection.forEach(s -> System.out.println(s));
}
}
List系列集合
List集合是单列集合一类。具有如下特点：
- 有序：存和取的元素顺序一致
- 有索引：可以通过索引操作元素
- 可重复：存储的元素可以重复
List集合继承了Colletion接口，但是List接口的类型都有索引，因此List集合会有多一些索引操作的方法：
方法名称 | 说明 |
void add(int index,E element) | 在此集合中的指定位置插入指定的元素 |
E remove(int index) | 删除指定索引处的元素，返回被删除的元素 |
E set(int index,E element) | 修改指定索引处的元素，返回被修改的元素 |
E get(int index) | 返回指定索引处的元素 |
add方法
在指定位置上添加元素，原来索引及后面的元素依次往后移。
remove方法
删除指定位置上的元素，并返回被删除的元素。
set方法
修改指定索引处的元素，并返回被修改的元素（老元素）
例程如下：
import java.util.ArrayList;
import java.util.List;
public class ListDemo {
public static void main(String[] args) {
// 1. 创建一个list
List<String> list = new ArrayList<>();
// 2. 添加元素
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");
// 3. add方法添加
list.add(1, "gg");
// 4. remove方法删除：删除指定位置上的元素，并返回被删除的元素
String removed = list.remove(0);
System.out.println(removed);
// 5.set方法
String setted = list.set(0, "xxx");
System.out.println(setted);
// 6. get方法
String i2 = list.get(2);
System.out.println(i2);
// 打印集合
System.out.println(list);
}
}
// 输出结果：
// aaa
// gg
// ccc
// [xxx, bbb, ccc, ddd]
List集合的遍历方式
List集合共有5中遍历方式。分别是
- 迭代器遍历
- 列表迭代器遍历
- 增强for遍历
- Lambda表达式遍历
- 普通for循环(因为List集合存在索引)
列表迭代器ListIterator
ListIterator接口继承于Iterator接口，提供了基于索引的更多的方法，并可以在遍历的同时进行添加和删除操作。
五种遍历方式的对比
遍历方法 | 特点 |
迭代器遍历 | 在遍历的过程中需要删除元素，请使用迭代器。 |
列表迭代器 | 在遍历的过程中需要添加元素，请使用列表迭代器。 |
增强for遍历 | 仅仅想遍历，那么使用增强for或Lambda表达式。 |
Lambda表达式 | |
普通for | 如果遍历的时候想操作索引，可以用普通for |
ArrayList类
ArrayList集合底层原理
- 利用空参创建的集合，在底层创建一个默认长度为0的数组
- 添加第一个元素时，底层会创建一个新的长度为10的数组
- 存满时，会扩容1.5倍
- 如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度以实际为准
在Idea中查看类的方法，Ctrl + N打开搜索框，搜索相应的内容，在打开的类中，按Alt+7打开侧边栏的大纲视图，同时也可以按Ctrl+F12弹出相应的大纲对话框。
transient关键字（补充知识点）
在ArrayList类中，实际存储数据的属性数组elementData在声明时是被transient关键字修饰的：
transient Object[] elementData; // non-private to simplify nested class access
// 非私有以简化嵌套类访问
简单说，transient修饰的变量表明其在类序列化时会被忽略，被transient的字段称为“瞬态字段（transient field）”。序列化是指将对象转换为字节流的过程（比如将对象序列化后存入文件或通过网络传输等；另外，可以被序列化的类必须实现Serializable标志性接口），反序列化与之相反（从文件或网络流中读取后并重建对象）。当我们将任何变量标记为transient时，该变量不会被序列化。由于对象的序列化形式中不存在瞬态字段（也即被transient修饰的字段不会被序列化，在保存后的文件里也不会存在瞬态字段的值），因此在从序列化形式创建对象时，反序列化过程将使用此类字段的默认值（为null或0）。
瞬态关键字在以下几种情况中有用：
- 可以用它来表示派生字段
- 对于不代表对象状态的字段，瞬态关键字非常有用
- 对于任何不可序列化的引用，我们可以使用瞬态关键字
- 当我们想存储敏感信息，且不想通过网络发送时，可以使用瞬态关键字
在final和transient共同修饰的成员变量时，是会被序列化的，但是如果被final和transient共同修饰的变量值在赋值时使用new操作的，那么将不会被序列化。
参考资料：https://www.baeldung.com/java-transient-keyword
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() | 从此列表中删除并返回最后一个元素 |
每个节点的真实数据存储在内部类Node<E>中。
数据结构知识
二叉树
树节点的内部结构
二叉树的相关知识
度：每一个节点的子节点数量
树高：树的总层数
根节点：最顶层的节点
左子节点：左下方的节点
右子节点：右下方的节点
根节点的左子树：蓝色虚线
根节点的右子树：绿色虚线
二叉查找树
二叉查找树，又称二叉排序树或者二叉搜索树。它有如下特点：
- 每一个节点上最多有两个子节点
- 任意节点左子树上的值都小于当前节点
- 任意节点右子树上的值都大于当前节点
添加节点的规则
小的存左边，大的存右边，一样的不存。
数据结构(二叉树)前序遍历
从根结点开始，然后按照当前结点，左子结点，右子结点的顺序遍历
数据结构(二叉树)后序遍历
从最左边的子节点开始，然后按照左子结点，右子结点，当前结点的顺序遍历
数据结构(二叉树)遍历方式小结
①前序遍历：当前节点，左子节点，右子结点公
②中序遍历：左子节点，当前节点，右子结点
③后序遍历：左子节点，右子结点，当前节点
④层序遍历：一层一层的去遍历
平衡二叉树
任意节点左右子树高度差不超过1。
如何保持二叉树平衡？
通过旋转机制。旋转分为左旋和右旋，当添加一个节点之后，该树不再是一颗平衡二叉树时触发。
左旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点，该不平衡节点即为支点。
方式一：
- 以不平衡的点作为支点
- 把支点左旋降级，变成左子节点
- 晋升原来的右子节点方式二：
- 以不平衡的点作为支点
- 将根节点的右侧往左拉
- 原先的右子节点变成新的父节点，并把原根节点多余的左子节点出让，给已经降级的根节点当右子节点
右旋
方式一：
- 以不平衡的点作为支点
- 把支点右旋降级，变成右子节点
- 晋升原来的左子节点
①左左 一次右旋
②左右 先局部左旋，再整体右旋
③右右 一次左旋
④右左 先局部右旋，再整体左旋
红黑树
红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。1972年出现，当时被称之为平衡二叉B树。后来，1978年被修改为如今的"红黑树"。
●它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色，
●每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的
红黑树：
- 是一个二叉查找树：
- 但是不是高度平衡的
- 条件：特有的红黑规则
数据结构(红黑树)红黑规则
- 每一个节点或是红色的，或者是黑色的
- 根节点必须是黑色
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil,这些Nil视为叶节点，每个叶节点(Nil)是黑色的
- 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；
添加节点的规则
红黑树在添加节点的时候，添加的节点默认是红色的
Set系列集合
Set系列集合
- 无序：存取顺序不一致
- 不重复：可以去除重复
- 无索引：没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素
Set集合的实现类
- HashSet:无序、不重复、无索引
- LinkedHashSet:有序、不重复、无索引
- TreeSet:可排序、不重复、无索引
Set接口中的方法上基本上与Collection的API一致。
练习1：利用Set系列的集合，添加字符串，并使用多种方式遍历。迭代器、增强for、Lambda表达式
HashSet类
HashSet底层原理
● HashSet集合底层采取哈希表存储数据
●哈希表是一种对于增删改查数据性能都较好的结构
哈希表组成
- JDK8之前：数组+链表
- JDK8开始：数组+链表+红黑树
哈希值
●根据hashCode方法算出来的int类型的整数
●该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
●一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
对象的哈希值特点
●如果没有重写hashCode方法，不同对象计算出的哈希值是不同的
●如果已经重写hashcode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
●在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。 (哈希碰撞)
HashSet底层原理
①创建一个默认长度16,默认加载因子为0.75的数组，数组名table
②根据元素的哈希值跟数组的长度计算出应存入的位置
③判断当前位置是否为null,如果是null直接存入
④如果位置不为null,表示有元素，则调用equals方法比较属性值
⑤一样：不存不一样：存入数组，形成链表
JDK8前后对比
- JDK8以前：新元素存入数组，老元素挂在新元素下面
- JDK8以后：新元素直接挂在老元素下面
- JDK8以后，当链表长度超过8,而且数组长度大于等于64时，自动转换为红黑树
- 如果集合中存储的是自定义对象，必须要重写hashCode和equals方法
问题1:HashSet为什么存和取的顺序不一样?
问题2:HashSet为什么没有索引?
问题3:HashSet是利用什么机制保证数据去重的?
小结
1.HashSet集合的底层数据结构是什么样的?
2.HashSet添加元素的过程?
3.HashSet为什么存和取的顺序不一样?
4.HashSet为什么没有索引?
5.HashSet是利用什么机制保证去重的?
练习利用HashSet集合去重
需求：创建一个存储学生对象的集合，存储舞个学生对象。使用程序实现在控制台遍历该集合。
要求：学生对象的成员变量值相同，我们就认为是同一个对象
需要重写hashCode和equals方法
LinkedHashSet类
●有序、不重复、无索引。
●这里的有序指的是保证存储和取出的元素顺序一致
●原理：底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序。
LinkedHashSet集合小结
LinkedHashSet集合的特点和原理是怎么样的?
●有序、不重复、无索引
●底层基于哈希表，使用双链表记录添加顺序
在以后如果要数据去重，我们使用哪个?
默认使用HashSet
如果要求去重且存取有序，才使用LinkedHashSet
TreeSet类
●不重复、无索引、可排序
●可排序：按照元素的默认规则(有小到大)排序。
● TreeSet集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好。
注意：TreeSet底层是红黑树，所以不需要重写hashCode和equals方法，但是必须重写排序规则。
需求：利用TreeSet存储整数并进行排序
TreeSet实现比较的方法
方式一：
默认排序/自然排序：Javabean类实现Comparable接口指定比较规则
方式二：
比较器排序：创建TreeSet对象时候，传递比较器Comparator接口匿名对象指定规则
//o1:表示当前要添加的元素
//o2:表示已经在红黑树存在的元素//返回值规则跟之前是一样的
TreeSet<String>ts =new TreeSet<>(new Comparator<String>(){@override
public int compare(String o1,String o2){
//按照长度排序
int i=01.length()-o2.length();//如果一样长则按照首字母排序
i=i==0?o1.compareTo(o2):i;return i;
工
});
练习：需求：创建5个学生对象
属性：(姓名，年龄，语文成绩，数学成绩，英语成绩),
按照总分从高到低输出到控制台
如果总分一样，按照语文成绩排
如果语文一样，按照数学成绩排
如果数学成绩一样，按照英语成绩排
如果英文成绩一样，按照年龄排
如果年龄一样，按照姓名的字母顺序排
如果都一样，认为是同一个学生，不存。
TreeSet小结
TreeSet集合的特点是怎么样的?
●可排序、不重复、无索引
●底层基于红黑树实现排序，增删改查性能较好
TreeSet集合自定义排序规则有几种方式
●方式一：Javabean类实现Comparable接口，指定比较规则
●方式二：创建集合时，自定义Comparator比较器对象，指定比较规则
方法返回值的特点
●负数：表示当前要添加的元素是小的，存左边
●正数：表示当前要添加的元素是大的，存右边
● 0:表示当前要添加的元素已经存在，舍弃
使用场景
1.如果想要集合中的元素可重复
●用ArrayList集合，基于数组的。(用的最多)
2.如果想要集合中的元素可重复，而且当前的增删操作明显多于查询
●用LinkedList集合，基于链表的。
3.如果想对集合中的元素去重
●用HashSet集合，基于哈希表的。 (用的最多)
4.如果想对集合中的元素去重，而且保证存取顺序
●用LinkedHashSet集合，基于哈希表和双链表，效率低于HashSet。
5.如果想对集合中的元素进行排序
●用TreeSet集合，基于红黑树。后续也可以用List集合实现排序。