前言
前面学习过了 ArrayList 的基本使用，但依旧有许多需要学习。
由于这一部分许多知识我现阶段并不会用到，所以直接略过。
集合分类
分为单列集合 Collection 与双列 Map 集合。
字面意思即可理解。单列集合一次添加一个数据，而双列集合一次添加两个相对应的数据。
集合体系结构
Collection 分为 List 和 Set，都是接口。
List 系添加元素有序、可重复、可索引；Set 无序、不重复、不索引。
Collection 系集合
Collection 基本操作
如下示例：
package test;
import java.util.ArrayList;
import java.util.Collection;
public class test {
public static void main(String[] args) {
Collection<String> coll = new ArrayList<>();
coll.add("a");
coll.add("b");
coll.add("c");
System.out.println(coll);
coll.remove("a");
System.out.println(coll);
coll.clear();
System.out.println(coll);
}
}
应当输出：
*contain 方法依赖的 equals 方法默认继承自 Object 类的 equals，比较的是地址值，而不是属性值。
Collection 通用遍历方法
迭代器遍历
迭代器不依赖索引。依靠创建并移动指针来读出所有元素。
public class collection {
public static void main(String[] args) {
// 创建集合，添加元素
Collection<String> coll = new ArrayList<>();
coll.add("a");
coll.add("b");
coll.add("c");
coll.add("d");
//获取迭代器对象
Iterator<String> it = coll.iterator();
//循环
while (it.hasNext()) {
String str = it.next();
System.out.println(str);
}
}
}
其它注意事项：
- 指针不再指向任何元素时调用
next 方法，会报错 NoSuchElementException
- 遍历结束后，指针不会复位
- 循环中只能使用一次使用
next 方法
增强 for 循环（foreach）遍历
- 增强 for 底层就是迭代器，可以简化书写
- JDK5 后出现
- 单列集合和数组才可以增强 for 遍历
package com.CollctionForEach;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class Demo1 {
public static void main(String[] args) {
Collection<String> names = new ArrayList<>();
names.add("张三");
names.add("李四");
names.add("王五");
names.add("赵六");
for (String s : names) {
System.out.println(s);
}
}
}
lambda 表达式遍历
package com.CollctionForEach;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class Demo1 {
public static void main(String[] args) {
Collection<String> names = new ArrayList<>();
names.add("张三");
names.add("李四");
names.add("王五");
names.add("赵六");
names.forEach(name -> System.out.println(name));
}
}
List 系集合
继承了 Collection 方法。因为 Collection 是 List 的超级接口。
由于 List 集合拥有索引，所以多了很多索引操作。
List 常用方法：
- add() – 将元素添加到列表
- addAll() – 将一个列表的所有元素添加到另一个
- get() – 有助于从列表中随机访问元素
- iterator() – 返回迭代器对象，该对象可用于顺序访问列表的元素
- set() – 更改列表的元素
- remove() – 从列表中删除一个元素
- removeAll() – 从列表中删除所有元素
- clear() – 从列表中删除所有元素（比removeAll()效率更高）
- size() – 返回列表的长度
- toArray() – 将列表转换为数组
- contains() – 如果列表包含指定的元素，则返回true
add() 方法包含两个参数，一个 index，一个 element。如果索引上已存在数据，则后面所有元素都后移。
remove() 可以删除指定索引的元素，同时返回删除的元素。
List 遍历方式
由于继承了 Collection，所以可以使用上面提到的通用遍历方法。
多了个索引，就可以用普通 for 循环了：
for (int i = 0; i < list.size(); i++) {
String item = list.get(i);
sout(item);
}
数据结构（一）
栈
后进先出，先进后出。
队列
先进先出，后进后出。
数据从后端进队列的过程，叫作入队列。
数据从前端出队列的过程，叫作出队列。
数组
由于添加、删除元素都需要移动一批元素，所以增删速度慢。
但是查询速度快，因为元素在内存中是连续存储的。
链表
链表种的每一个元素，成为结点，每个结点都是一个独立的对象，拥有自己的地址值。每个结点中，不仅会存储自己的数据，还会存储下一个结点的地址值。与链条结构很相似。
创建的第一个结点，叫作头结点。
添加数据：创建新结点，在头节点存储新结点的地址值，即可将结点串联起来。“^”表示空地址值。
所以，链表的查找速度较慢。数组在内存中是一篇连续的空间，本质上只需要一个数组的地址值，随后就可以使用索引找到元素。链表查找数据则必须从头结点开始查找，一个个向后。
不过，链表插入数据并不需要像数组那样将一大批的元素后后移，直接修改地址值就可以完成数据的插入。因此，链表的增删速度较快。
我们可以像每个结点中塞入两个地址值，这样它就可以完成双向查找，效率大幅提升，称为双向链表。
泛型
概述
JDK5 引入的新特性，可以在编译阶段约束操作数据的类型，并进行检查。
格式：<数据类型>。
泛型只支持引用数据类型。
如果不设定泛型，集合中所有数据类型都是 Object 类。
泛型的好处：
- 统一数据类型
- 将运行时会出现的问题提前至编译阶段检查，可以规避一系列数据类型错误
Java 中的泛型，是伪泛型。意思就是，这个泛型，只在编译时期有效。
泛型类
例如：
public class ArrayList<E>{
}
不确定成员数据类型时，可以使用泛型。
任意字母都可以，比如 Type，Element，Key，Value。
泛型方法
一个方法的形参不确定的话，可以在类添加泛型，也可以单独给一个方法加上泛型。例如 public static<E> void method(E e){}。
其它
泛型本身不可继承，但数据具备继承性。
数据结构（二）
二叉树
由父节点、左/右子节点构成。
每个节点都是独立的对象，不仅存储当前数据，还会按需存储父节点、左/右子节点的地址值。
一些术语
度
每个节点的子节点数量，叫作度。任意节点度 <= 2 的，叫作二叉树。
二叉搜索树树的数据规律
遵守一个规则：小在左，大在右，一样就跳过。
二叉树的遍历方式
前序遍历：根结点 —> 左子树 —> 右子树
中序遍历：左子树—> 根结点 —> 右子树
后序遍历：左子树 —> 右子树 —> 根结点
层次遍历：只需按层次遍历即可
平衡二叉树
任意节点的左右子树高度差不超过一。
平衡二叉树的旋转机制
确定支点：不断向父节点寻找不平衡的节点。
- 以不平衡的点为支点
- 将支点左旋降级，使其成为左子节点
- 晋升原本的右子节点
右旋同理。
二叉树需要旋转的四种情况
一、左左
当根节点左子树的左子树点有节点插入，导致二叉树不平衡时。
右旋一次可以保持平衡。
二、左右
根节点的左子树的右子树有节点插入。
先将左子树局部左旋使其成为“左左”的情况，然后右旋即可恢复平衡。
三、右右
与“左左相反”。左旋一次恢复平衡。
四、右左
同理，局部右旋，随后左旋。
红黑树
概述
- 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
- 1972 年出现，当时被称之为平衡二叉B树。后来，1978 年被修改为如今的“红黑树”
- 它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色
- 每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过”红黑规则”进行实现的
是一个二叉查找树。
并不高度平衡，平衡靠红黑规则保证，比二叉树的“任意节点的左右子树高度差不超过一”的要求宽松一些。
红黑规则
- 每一个节点或是红色的，或者是黑色的
- 根节点必须是黑色
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil)是黑色的
- 如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
红黑树的节点中，会多存储一个颜色属性，即黑或红。
添加的节点默认为红色。因为如果添加黑色的话，会违反第五条规则，还需要更换一下颜色。
Set 类集合
概述
- 无序：存取顺序不一致
- 不重复：可以去除重复
- 无索引：没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素
Set 类集合的实现类
- HashSet：无序、不重复、无索引
- LinkedHashSet：有序、不重复、无索引
- TreeSet:可排序、不重复、无索引
Set 集合的方法与 Collection 方法基本一致。
HashSet 概述
没有什么新方法，直接了解一下原理即可。
不从 0 索引开始向后存储，而是依据一定计算得到整数索引。
int index = (数组长度 - 1) & HashCode;
哈希值
对象的整数表现形式。
- 根据hashCode方法算出来的int类型的整数
- 该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
- 一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
对象的哈希值属性：
- 如果没有重写 hashCode 方法，不同对象计算出的哈希值是不同的
- 如果已经重写 hashCode 方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
- 在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。（哈希碰撞——概率极小，但确有可能）
我们来演示一下，这里创建两个对象并获取其哈希值。
public class demo {
public static void main(String[] args) {
Student s1 = new Student("zhangsan",23);
Student s2 = new Student("zhangsan",23);
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
}
}
输出：
对于哈希碰撞，我们也可以模拟：
public class demo {
public static void main(String[] args) {
System.out.println("abc".hashCode());
System.out.println("acD".hashCode());
}
}
输出：
HashSet 底层原理
- HashSet集合底层采取哈希表存储数据
- 哈希表是一种对于增删改查数据性能都较好的结构
Hash 表的组成
- JDK8之前：数组+链表
- JDK8开始：数组+链表+红黑树
模拟一下：
- 创建一个默认长度16，默认加载因为0.75的数组，数组名table
- 根据元素的哈希值跟数组的长度计算出应存入的位置
- 判断当前位置是否为null，如果是null直接存入
- 如果位置不为null，表示有元素，则调用equals方法比较属性值
- 一样：不存
- 不一样：存入数组，形成链表——JDK8以前：新元素存入数组，老元素挂在新元素下面；JDK8以后：新元素直接挂在老元素下面
同时，当链表长度大于 8 且数组长度大于 64 时，该链表自动转换为红黑树以提高查改效率。
这时，就会出现三种数据结构：table[] 数组，链表，还有转换后的红黑树。也就是上面说的”数组+链表+红黑树“。
如果集合中存储的是自定义对象，必须要重写 hashcode 和 equals 方法。
关于 HashSet 的三个问题
问题一：为什么 HashSet 的存取的顺序不一样？
既然索引是计算而来，就有可能出现后添加的数据存储在前边的情况了。
问题二：为什么 HashSet 没有索引？
首先，HashSet 是不重复的（HashCode 与 equals 方法）。
而且，有索引的是数组，链表会挂许多元素。我们不能够根据链表头结点所在的索引去找到链表里的元素。所以，是不索引的。
问题三：如何保证去重？
HashCode 与 equals 方法。
一样的会跳过不存。不存在重复数据的情况。
综上，我们书写如下代码：
import java.util.HashSet;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("zhangsan",23);
Student s2 = new Student("lisi",24);
Student s3 = new Student("wangwu",25);
Student s4 = new Student("zhangsan",23);
HashSet<Student> hs = new HashSet<>();
System.out.println(hs.add(s1));
System.out.println(hs.add(s2));
System.out.println(hs.add(s3));
System.out.println(hs.add(s4));
System.out.println(hs);
}
}
// 输出：
// true
// true
// true
// false
// [Student@42ca5bd9, Student@62365a6, Student@a8e9e1e4]
// 打印地址值是因为没有重写 toString
并且在 Student 类中重写 hashCode() 和 equals()，基于 name 和 age 来定义相等的逻辑。不然会返回四个 true：
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Student student = (Student) obj;
return age == student.age && Objects.equals(name, student.name);
}
LinkedHashSet 概述
- 有序、不重复、无索引。
- 这里的有序指的是保证存储和取出的元素顺序一致
- 原理：底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序。
每一个结点都会同相邻存储的数据建立一个双向链表。这样，取出时，顺序就是一样的了。
由于我们需要观察去除顺序，这里顺手重写一下 Student 类的 toString 方法：
public String toString () { return "Student{name =" + name + ", age =" + age + "}"; }
import java.util.LinkedHashSet;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("zhangsan",23);
Student s2 = new Student("lisi",24);
Student s3 = new Student("wangwu",25);
Student s4 = new Student("zhangsan",23);
LinkedHashSet<Student> hs = new LinkedHashSet<>();
System.out.println(hs.add(s1));
System.out.println(hs.add(s2));
System.out.println(hs.add(s3));
System.out.println(hs.add(s4));
System.out.println(hs);
}
}
// input：
// true
// true
// true
// false
// [Student{name =zhangsan, age =23}, Student{name =lisi, age =24}, Student{name =wangwu, age =25}]
可以观察到，数据的取出确实是有序的。
TreeSet 概述
- 不重复、无索引、可排序
- 可排序：按照元素的默认规则（有小到大）排序
- TreeSet集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好
// import java.util.LinkedHashSet;
import java.util.TreeSet;
public class demo {
public static void main(String[] args) {
// Student s1 = new Student("zhangsan",23);
// Student s2 = new Student("lisi",24);
// Student s3 = new Student("wangwu",25);
// Student s4 = new Student("zhangsan",23);
TreeSet<Integer> hs = new TreeSet<>();
hs.add(5);
hs.add(2);
hs.add(3);
hs.add(4);
hs.add(1);
System.out.println(hs);
}
}
// 输出：
// [1, 2, 3, 4, 5]
// 这是因为 TreeSet 默认从小到大自动排序
TreeSet 集合默认的规则
- 对于数值类型：
Integer，Double，默认按照从小到大的顺序进行排序。
- 对于字符、字符串类型：按照字符在ASCII码表中的数字升序进行排序。
TreeSet 比较器排序
Student 类：
public class Student {
private String name;
private int age;
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student [name=" + name + ", age=" + age + "]";
}
}
测试类：
public class DemoTreeSet {
public static void main(String[] args) {
TreeSet<Student> ts = new TreeSet<>();
ts.add(new Student("张廷玉",43));
ts.add(new Student("纳兰明珠",80));
ts.add(new Student("索额图",79));
System.out.println(ts);
}
}
如果没有自定义比较器，TreeSet 集合存储的对象元素必须实现 Comparable 接口。这里我们的 Student 类既没有定义比较器，没有实现 Comparable 接口，所以会报 java.lang.ClassCastException 异常，意思就是这里存的元素不是 Comparable 类型的。
实现 Comparable 接口：
@Override
public int compareTo(Student o) {
return this.age - o.age;
}
按照这个规则，就可以实现依照 age 属性进行升序排序了。