为了面试而战--集合（上）
今天投了实习简历，想着巩固巩固Java基础，根据心情选择复习集合的知识，一边看黑马的视频，一遍看JavaGuide的集合文章，这里写一点集合中的小细节。
集合主要由两大接口派生而来，一个接口为Collection，另一个接口为Map。这篇文章就来先讲讲Collection接口
一.Collection
Collection接口中的方法中有一个方法为contains()，包含的意思，就是来查在某个元素是否存在于集合中，由于Collection是接口，没法创建对象，这里我就用ArrayList来创建对象。在集合中存入一些基本数据类型，再使用contains方法进行判断，这没什么好说的，但是如果存入的是自定义对象呢，比如存放Student对象。
Collection<Student> coll = new ArrayList<>();
Student s1 = new Student("zhangsan",23);
Student s2 = new Student("lisi",24);
Student s3 = new Student("wangwu",25);
//把学生对象添加到集合当中
coll.add(s1);
coll.add(s2);
coll.add(s3);
//判断集合中某一个学生对象是否包含
Student s4 = new Student("zhangsan",23);
System.out.println(coll.contains(s4));
根据多态的性质，运行看右边，所以coll使用的是ArrayList中的contains()。ArrayList的contains()底层使用equals()来判断对象是否一致，我们期待最后的输出语句应该是true，但实际上是false，这是为什么。因为如果我们在集合中存储的是自定义对象，没有重写equals()方法，默认就是用的Object类中的equals()，根据对象的地址进行判断，s4肯定和前面的地址不同，所以就是fasle。要是想根据Student的某个属性进行比较，就要在Student类中重写equals()。
Collection有三种遍历方式：
- 迭代器遍历
- 增强for遍历
- Lambda表达式遍历
那之前的普通for遍历哪去了呢?是因为普通for是根据索引遍历，但是Collection中有一个接口叫Set，Set没有索引，所以无法用for循环。普通for只能List来用，所以就有了通用的遍历方式。
迭代器（Iterator）不依赖索引，集合专用的遍历方式。简单来说就是指针+移动
Iterator it = list.iterator();//创建迭代器对象，相当于创建指针，默认指向集合的第一个元素
while(it.haxNext()){//判断指针下一个位置是否有元素
String str = it.next();//获得元素并移动指针，这是next()干的两件事
System.out.println(str);
}
细节：
- 指针已经指向空了，还要用next()，会报错，NoSuchElementException。按照以前的思想，指针已经到了集合的外面，报错也应该报索引异常的错误，为什么报的是没有元素错误呢，因为迭代器不依赖指针！
- 迭代器遍历完毕，指针不会复位，想要第二次遍历，就创建一个新的迭代器对象。
- 循环中只能出现一次next()，给个例子
Collection<String> coll = new ArrayList<>();
coll.add("aaa");
coll.add("bbb");
coll.add("ccc");
coll.add("ddd");
coll.add("eee");
//2.获取迭代器对象
//迭代器就好比是一个箭头，默认指向集合的0索引处
Iterator<String> it = coll.iterator();
//3.利用循环不断的去获取集合中的每一个元素
while(it.hasNext()){
//4.next方法的两件事情：获取元素并移动指针
System.out.println(it.next());
System.out.println(it.next());
}
这是会报NoSuchElementException错误，这里面一次循环移动两次，添加了奇数个元素，自己手写走一次，就会发现当指针在某一次循环到拿到了指针指向的ddd并且指针要后移指向eee的时候，再进入循环，第一个输出语句没问题，但第二个就出问题了，指针已经越界了但还要拿元素，肯定报错。
- 迭代器遍历的时候，不能用集合的方法进行增加或者删除（要分析源码）
什么叫用集合的方法进行增加或删除，如下：
//3.利用循环不断的去获取集合中的每一个元素
while(it.hasNext()){
//4.next方法的两件事情：获取元素,并移动指针
String str = it.next();
if("bbb".equals(str)){
//coll.remove("bbb");
it.remove("bbb");
}
}
会报错，ConcurrentModificationException，并发修改异常。如果实在要删除，可以用迭代器的方法删除。
增强for遍历，底层就是Iterator，为了简化迭代器而产生的。适用于所有单列集合和数组。
//1.创建集合并添加元素
Collection<String> coll = new ArrayList<>();
coll.add("zhangsan");
coll.add("lisi");
coll.add("wangwu");
//2.利用增强for进行遍历
//注意点：
//s其实就是一个第三方变量，在循环的过程中依次表示集合中的每一个数据
for(String s : coll){
s = "qqq";
}
System.out.println(coll);//zhangsan lisi wangwu
上面代码一个小小细节，我在遍历的过程改了s的值，那会影响原来的集合数据吗？答案是不会的，还是原来的集合。因为这里的s仅仅是第三方变量，和原本集合并没有关系，只起到记录集合数据的作用，就是值传递。
lambda表达式遍历
//1.创建集合并添加元素
Collection<String> coll = new ArrayList<>();
coll.add("zhangsan");
coll.add("lisi");
coll.add("wangwu");
//2.利用匿名内部类的形式
//底层原理：
//其实也会自己遍历集合，依次得到每一个元素
//把得到的每一个元素，传递给下面的accept方法
//s依次表示集合中的每一个数据，要对集合中的数据进行一些操作，对s进行操作即可
coll.forEach(new Consumer<String>() {
@Override
public void accept(String s) {
System.out.println(s);
}
});
foreach底层原理，先看一下代码。我们就看红框框的就行，这就是一个普通for遍历，获得元素之后把元素交给accept()去处理，这个方法就是上面重写的accpet()
写成Lambda表达式的形式
//lambda表达式 coll.forEach(s -> System.out.println(s));
以上就是Collection的基本内容，要记住的就一下几点：
- Collection是单列集合的顶层接口，它的方法List和Set都能用
- 遍历方式有三种
二.List
List是Collection的子接口，是Collection集合中的一种，特点就是有序、有索引、可重复，继承了Collection中的所有方法，并由于自身具有索引，因此多了一些索引操作。
List中的remove方法有些要注意，List中有两个remove()，发生了方法重载，一个是根据索引删除，一个是删除元素。
那如果我们要删除元素，现在写了remove(1)，结果删的是索引1上的元素还是元素1呢？这两个方法的形参分别是Object类和int类，我们传入remove()的实参为1,1默认是int，如果当成是Object类调用remove(Object o)还需要额外的装箱操作，所以会优先选择int，也就是删除索引为1的元素，可以概括为当方法出现重载现象时，优先调用实参和形参类型一致的那个方法。那要是真的想删除1这个元素呢，就需要我们提前手动装箱，把i转换成Integer类。
//List系列集合中的两个删除的方法 //1.直接删除元素 //2.通过索引进行删除 //1.创建集合并添加元素 List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); //2.删除元素 //请问：此时删除的是1这个元素，还是1索引上的元素？ //为什么？ //因为在调用方法的时候，如果方法出现了重载现象 //优先调用，实参跟形参类型一致的那个方法。 list.remove(1);
List集合一共有五种遍历方式，除了Collection具有的三种外，List还有列表迭代器遍历和普通for循环（因为List有索引），其中列表迭代器遍历是List集合独有的遍历方式。
列表迭代器（接口）：ListIterator<E> 是迭代器的子接口。这个迭代器具有add()和remove()方法。
//获取列表迭代器，指针默认指向0索引
ListIterator<String> it = list.listIteratior();
//比迭代器额外添加了一个方法：在遍历的过程中，可以添加元素的add()
while(it.hasNext){
String str = it.next();
if("bbb".equals(str)){
it.add("qqq");//用迭代器本身的方法添加
}
}
下面我们来学习一下List的实现类，ArrayList、LinkedList以及Vector。这个实现类有什么区别呢，这就涉及到底层的数据结构了。先来学习一下有关数据结构的知识。
三.数据结构（栈、队列、数组、链表）
我们先了解一些常用的数据结构，知道每种数据结构长什么样子、如何添加删除数据。
- 栈
- 队列
- 数组
- 链表
- 二叉树
- 二叉查找树
- 平衡二叉树
栈的特点：一端开口，从上面进从上面出，后进先出，先进后出。java的内存结构中有一块区域叫做栈内存，用的就是这种思想，方法运行的时候进栈，执行完毕出栈。
队列的特点：两端开口，先进先出，后进后出，从后端入，从前端出。
数组的特点：查询快，增删慢
- 查询速度快：查询数据可以根据数组的地址值和索引定位，查询任意数据耗时相同，数组元素在内存中是连续存储的
- 删除效率低：删一个元素既要把原始数据删除，还要把后面的元素前移
- 添加效率低：添加位置后的每个元素后移，再添加元素
链表的特点：和数组相反，查询慢，增删快。链表中每个元素被称为结点，链表中的结点是独立不连续的，结点里会存储数据以及下一个结点的地址值。多个结点组成链表。所以查询慢，每次都要从头开始查。
上述讲的这种链表，只能从前往后找，被称为单向链表，下面来说一下即能从前往后找，又能从后往前找的链表，能够提升查询效率，被称为双向链表。双向链表的节点还存储了前一个节点的地址值。那双向链表怎么就提高查找效率呢？适用于这种场景，我们要查第N个元素，如果N里头近，就从头开始查找，如果N离尾近，就从尾部开始查找。
四.Arraylist
了解一些数据结构之后，开始学习List的第一个实现类，ArrayList。ArrayList的原码分析很重要，我在之前的文章中写了，移步到爪哇基础题08。
五.LinkedList
第二个实现类为LinkedList，底层是双向链表，增删快，查找慢，首尾操作的速度极快，所以LinkedList多了很多首位操作的API。底层源码分析同样移动到爪哇基础题08。
接着我们来看一下迭代器的底层源码。iterator()这个方法就可以获得迭代器对象，主要就是看Itr是干什么的，就是ArrayList里的内部类，获取迭代器对象就相当于获取自己内部类对象。
内部类只需要研究CollectionCollectionCollectiona前两个成员变量，cursor（指针），默认初始化0，所以指向0索引。lastRet（刚刚操作索引的位置），现在指向的是0索引，那刚刚就是-1，所以初始化为-1。
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;//表示集合变化的次数，每add一次或者remove一次，这个变量都会自增，当我们创建迭代器对象的时候，就会把这个次数告诉迭代器，迭代器自己做一个记录。假设现在的次数为3
public boolean hasNext() {
/*
假如一个集合，a、b、c，一共三个元素，size = 3。最开始curson = 0，判断为true，存在元素；然后curson = 1，判断为true；最后curson = 2，判断为true。再往下就是false，说明指针已经出去了
*/
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//检查方法，检查当前集合中做新的变化次数跟一开始记录的次数是否相同，如果相同，证明当前集合没有发生改变；如果不一样，证明迭代器在遍历的过程中用了集合的增加或删除方法，别人已经变化了集合里的内容。这就是并发修改异常底层的原理
int i = cursor;//记录当前指针指向的索引位置，最开始为0
if (i >= size)//i >= 3就报错，也就是指向了3就报错
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//底层数组拿过来
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;//最开始i = 0 ,所以curson = 1，把当前指针往右移动一位，指针来到了1索引的位置
return (E) elementData[lastRet = i];//i = 0，lastRet = 0，elementData[0]
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
关于并发修改异常的一个结论：在以后如何避免并发修改异常，在使用迭代器或者是增强for遍历集合的过程中，不要使用集合的方法去添加或者删除元素即可。
六.泛型深入
这部分来聊一聊泛型，深入泛型。泛型是JDK5引入的特性，可以在编译阶段约束操作的数据类型，并进行检查，泛型只能支持引用数据类型。
比如一个集合ArrayList<String>，只能往里存String类型的。那在JDK5之前，没有泛型，是怎么约束操作的数据类型呢？集合怎么存储数据呢？
//没有泛型的时候，集合如何存储数据
//结论：
//如果我们没有给集合指定类型，默认认为所有的数据类型都是Object类型
//此时可以往集合添加任意的数据类型。
//带来一个坏处：我们在获取数据的时候，无法使用他的特有行为。
//1.创建集合的对象
ArrayList list = new ArrayList<>();
//2.添加数据
list.add(123);
list.add("aaa");
list.add(new Student("zhangsan",123));
//3.遍历集合获取里面的每一个元素
Iterator it = list.iterator();
while(it.hasNext()){
Object str = it.next();//想强转都不行，你都不知道到底要转成什么样的数据类型
//多态的弊端是不能访问子类的特有功能
//obj.length();
//str.length();
System.out.println(str);
}
那看了上面的例子，想想泛型的好处是什么。首先肯定是统一了数据类型，只能存一类数据。其次，把运行期间的问题提前到了编译期间，避免了强制类型转换带来的错误，因为在编译期数据类型就能确定下来。
扩展知识点：Java中的泛型是伪泛型。什么意思呢，就是你确定了一个泛型String，他相当于是看门的，看见你存入的数据的确是String类型，放你进了，但是所有数据进入集合之后又都会变成Object类，但是在出来的时候，他又会被强转成泛型。我们写Java文件时，泛型存在，编译成class文件后，泛型又没了，被称为泛型的擦除。
关于泛型就记住一句话，统一数据类型。还有一些小细节：
- 泛型不能存基本数据类型
- 确定泛型后，可以传入该类型或其子类型
- 如果不写泛型，类型默认是Object
泛型不仅可以用到集合上，还可以有泛型类、泛型方法、泛型接口。
泛型类使用场景：类中，某个变量的数据类型不确定，就可以定义泛型类。创建对象时，才会确定泛型。
public class MyArrayList<E> {
Object[] obj = new Object[10];
int size;
/*
E : 表示是不确定的类型。该类型在类名后面已经定义过了。
e：形参的名字，变量名
* */
public boolean add(E e){
obj[size] = e;
size++;
return true;
}
public E get(int index){
return (E)obj[index];//返回的是Object类型，要进行强转
}
@Override
public String toString() {
return Arrays.toString(obj);
}
}
泛型方法：当方法的形参类型不确定时，就可以在方法上定义泛型。当然也可以在类名后面定义泛型。两者有一定区别，在类名上定义泛型，整个类中的所有方法都能用，但是在某一个方法上定义泛型，只能这个方法用。
public class ListUtil {
private ListUtil(){}
//类中定义一个静态方法addAll，用来添加多个集合的元素。
/*
* 参数一：集合
* 参数二~最后：要添加的元素
* 传入集合之后，要添加的元素泛型也就确定了
* */
public static<E> void addAll(ArrayList<E> list, E e1,E e2,E e3,E e4){
list.add(e1);
list.add(e2);
list.add(e3);
list.add(e4);
}
//可以添加很多个元素，多少个我也不知道，这个叫可变参数，底层是个数组
/* public static<E> void addAll2(ArrayList<E> list, E...e){
for (E element : e) {
list.add(element);
}
}*/
public void show(){
System.out.println("尼古拉斯·纯情·天真·暖男·阿玮");
}
}
泛型接口：重点在于如何使用一个带泛型的接口
- 实现类给出具体类型
- 实现类延续泛型，创建对象时再确定
public class MyArrayList2 implements List<String>
//MyArrayList2中只能存String
public class GenericsDemo4 {
public static void main(String[] args) {
/*
泛型接口的两种使用方式：
1.实现类给出具体的类型
2.实现类延续泛型，创建实现类对象时再确定类型
*/
MyArrayList2 list = new MyArrayList3<>();//这里创建对象的时候就不需要再指定泛型了
}
}
public class MyArrayList3<E> implements List<E>{
@Override
public boolean add(E e) {
return false;
}
//可以看见这里add的参数类型也不确定了
//创建对象的时候就需要指定类型了
MyArrayList3<String> list = new MyArrayList3<>();
泛型的继承和通配符
- 泛型是不具备继承性的，但是数据具备继承性
public class GenericsDemo5 {
public static void main(String[] args) {
/*
泛型不具备继承性，但是数据具备继承性
*/
//创建集合的对象，三种类，存在继承关系
ArrayList<Ye> list1 = new ArrayList<>();
ArrayList<Fu> list2 = new ArrayList<>();
ArrayList<Zi> list3 = new ArrayList<>();
//调用method方法
//method(list1);
//method(list2); 报错
//method(list3); 报错
//数据具备继承性
list1.add(new Ye());
list1.add(new Fu());
list1.add(new Zi());
}
/*
* 此时，泛型里面写的是什么类型，那么只能传递什么类型的数据。这叫做泛型不具备继承性
* */
public static<Ye> void method(ArrayList<Ye> list) {
}
}
class Ye{}
class Fu extends Ye{}
class Zi extends Fu(){}
public class GenericsDemo6 {
public static void main(String[] args) {
/*
* 需求：
* 定义一个方法，形参是一个集合，但是集合中的数据类型不确定。
*
* */
//创建集合的对象
ArrayList<Ye> list1 = new ArrayList<>();
ArrayList<Fu> list2 = new ArrayList<>();
ArrayList<Zi> list3 = new ArrayList<>();
ArrayList<Student2> list4 = new ArrayList<>();
method(list1);
method(list2);
method(list3);
//method(list4);
}
/*
泛型方法有个弊端：
利用泛型方法，此时它可以接收任意的数据类型
Ye Fu Zi Student
希望： 本方法虽然不确定类型，但我只希望他只能传递Ye、Fu、Zi
此时我们就可以使用泛型的通配符:
?也表示不确定的类型
他可以进行类型的限定
？ extends E：表示可以传递E或者E的所有子类
？ super E：表示可以传递E或者E所有的父类
*/
//public <E> static void method(ArrayList<E> list) {}
public static void method(ArrayList<? extends Ye> list)
}
class Ye {
}
class Fu extends Ye {
}
class Zi extends Fu {
}
class Student2{}
我们学了这么多泛型的相关内容，那各种泛型应用场景如何呢：
- 如果我们在定义类、方法、接口时，类型不确定，就可以定义泛型类、泛型方法、泛型接口
- 如果类型不确定，但知道以后只能传递某个继承体系，就可以用泛型的通配符
学完泛型之后，最需要理解的就是这句话：泛型不具有继承性，但数据具有继承性。
单列集合中的Vector被淘汰了，就不用多说了。
七.数据结构（树）
在学习Set之前，我们先来学习一种数据结构，叫做树。
树里的每一个元素叫做节点（Node），一个节点会存放自己的值、父节点地址、左子节点地址和右子节点地址，没有就记为null。
二叉查找树，又称二叉排序树或二叉搜索树，特点：
- 每一个节点上最多有两个子节点
- 任意节点左子树上的值都小于当前节点
- 任意节点右子树上的值都大于当前节点
添加节点规则：小的存左边，大的存右边，一样的不存。
查找规则：和添加节点规则类似
二叉树的遍历方式：
1 .前序遍历：从根节点开始，按照当前，左，有的顺序遍历
20 18 16 19 23 22 24
2. 中序遍历：从最左边的子节点开始，按照左，当前，右的顺序遍历 最重要最常见
16 18 19 20 22 23 24 从小到大排序
3. 后序遍历：从最左边的子节点开始，按照左，右，当前的顺序遍历
16 19 18 22 24 23 20
4. 层序遍历：一层一层遍历
二叉查找树的弊端：不平衡，就像下面这个树一样
找五次才能找到13，和链表一样了，不合理。我们想要左右差不多的树，这就需要这种树了，平衡二叉树。这种数任意节点的左右子树高度差不能超过1，提高查找效率。
二叉树 -> 二叉查找树 -> 平衡二叉树
平衡二叉树的旋转机制
规则1：左旋
规则2：右旋
触发时机：当添加一个节点之后，该树不再是一颗平衡二叉树
左旋：添加12之后不平衡了
首先要确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
10节点右子树比左子树高的超过了，这时候就以10为支点，而且10的右边比左边多，选择左旋。
步骤：
- 以不平衡的点作为支点
- 把支点左旋降级，变成左子节点
- 晋升原来的右子节点
复杂一点的情况：
支点为7，左旋。
- 以不平衡的点作为支点
- 将根节点的右侧往左拉
- 原先的右子节点变成新的父节点，并把多余的左子节点让出，给已经降级的根节点当右子节点
右旋：
新添加的是1，往上找支点，4为支点，对4进行右旋。
步骤：
- 以不平衡的点作为支点
- 把支点左旋降级，变成左子节点
- 晋升原来的右子节点
复杂情况：
支点7，右旋
步骤：
- 以不平衡的点作为支点
- 将根节点的左侧往右拉
- 原先的左子节点变成新的父节点，并把多余的右子节点让出，给已经降级的根节点当左子节点
平衡二叉树需要旋转的四种情况
- 左左：根节点左子树的左子树有节点插入，导致二叉树不平衡，一次右旋就能搞定
- 左右：根节点的左子树的右子树插入，导致二叉树不平衡，一次旋转无法解决
右旋一次，仍不平衡
先对局部进行左旋，就和左左是一样的
最后就整体右旋
3.右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡，左旋一次
4.右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡
对局部进行右旋
最后整体左旋
最后总结一下，最开始我们只有普通的二叉树，但是数据都是随意存储，没有规律，查询效率低。后来我们有了二叉查找树，这种书添加的时候小的放左边，大的放右边，查询效率提升，但是他有弊端，容易出现长短腿，长短腿就跟链表一样了，而且还是单向链表，查询效率低。最后出现了平衡二叉树，任意节点左右高度差不能超过1，查询效率要更高。
平衡二叉树记住以下八个问题：
- 平衡二叉树怎么添加节点？和二叉查找树一样，小的放左边，大的放右边，一样的不存。
- 在平衡二叉树中，如何查找单个节点？从根节点查找，小的往左边查，大的往右边查
- 为什么要旋转？因为往树中添加一个元素后，树就不平衡了，那就需要通过旋转使树重新平衡。
- 旋转的出发时机？和上个问题一样
- 左左是什么意思？如何旋转？
- 左右是什么意思？如何旋转？
- 右右是什么意思？如何旋转？
- 右左是什么意思？如何旋转
下面我们再来学习一种新的数据结构，也是一种新的树，叫红黑树，是一种自平衡的二叉查找树。红黑树是一种特殊的二叉查找树，每一个节点上都有存储位表示节点的颜色，每一个节点可以是红或者黑；红黑树不是高度平衡的，他的平衡是通过“红黑规则”进而实现的。
红黑树和平衡二叉树有什么区别呢？平衡二叉树是高度平衡的，当左右子树高度差超过1时，通过旋转保持平衡，但是这样有些强迫症，会影响效率。而红黑二叉树添加一个元素后，不符合自己的红黑规则才旋转，这个规则比平衡二叉树要轻一点。
红黑规则：
- 每一个节点只能是红或者黑
- 根节点必须是黑
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，视为叶节点，必须为黑
- 如果某一个节点为红，那他的子节点必须为黑，不能出现两个红色节点相连的情况
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
如果一个节点没有子节点，那这个节点存储的对应子节点的地址就为Null，但是也要挂一个节点，叫做Nil，里面没有任何数据。什么是后代节点，对于13来说，所有点都是他的后代节点，那什么是后代叶节点，就是所有的Nil。简单路径就是不能走回头路。
默认添加的节点是红色的（效率高），添加的时候不容易违背规则。别以为上面的五条规则就是规则了，下面的才是震惊。注意的是旋转过程中不需要考虑Nil。红黑树增删改查效率都高。
八.Set
学完树之后，就可以学单列集合的第二个分支Set集合了。回想一下List集合的特点，有序，可重复，有索引，Set集合的特点就是无序，不可重复，无索引。无序的意思就是存取顺序不一样，不可重复可以帮助我们去重，无索引的特性就说明Set中的方法都没有带索引的，也不能用普通for遍历，不能通过索引获取元素。
Set实现类包括：
- HashSet：无序、不重复、无索引
- LinkedHashSet：有序、不重复、无索引
- TreeSet：可排序、不重复、无索引
Set接口继承了Collection接口，方法也是Collection中的方法。
Set接口中的add()返回值可有用了，存在的元素add()之后返回值是false，可以通过返回值判断添加元素是否存在。
九.HashSet
首先学习第一个实现类，HashSet，它没有什么额外的方法，要关注底层原理。
- HashSet底层采用哈希表存储数据
- 哈希表是一种对于增删改查数据性能都比较好的结构
哈希表的组成
- JDK8之前：数组+链表
- JDK8开始：数组+链表+红黑树
哈希值是哈希表的灵魂所在，是对象的整数表现形式。哈希表的底层是一个数组哈希表中的数据不是从0开始存的，而是根据公式int index = (数组长度 - 1) & 哈希值来计算数据应存入的位置。
哈希值
- 根据hashCode方法算出来的int类型整数
- 该方法定义在Object中，所有对象都可以调用，默认使用地址值计算
- 一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
对象的哈希值特点
- 如果没写重写hashCode方法，不同对象计算出的哈希值不同，因为默认是根据地址值计算，地址值肯定不同
- 如果重写hashCode方法，不同对象属性值相同，计算出的哈希值相同。重写在类中IDEA可以帮我们直接重写。
- 在小部分情况下，不同的属性值或者不同的地址值计算出的哈希值可能相同，被称为哈希碰撞
//String类底层已经重写了hashCode
//在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。
//哈希碰撞
System.out.println("abc".hashCode());//96354
System.out.println("acD".hashCode());//96354
HashSet JDK8之前的底层原理 数组+链表
- 创建一个默认长度16，默认加载因子0.75的数组，数组名table，一开始数组中存的都是null
- 根据元素的哈希值跟数组的长度计算出应存入的位置 int index = (数组长度 - 1) & 哈希值
- 判断当前位置是否为null，如果是null直接存入
- 如果位置不为null，表示有元素，则调用equals方法比较属性值
- 一样：不存 不一样：存入数组，形成链表
- JDK8以前：新元素存入数组，老元素挂在新元素下面，形成链表
- JDK8以后：新元素直接挂在老元素下面，形成链表
- 如果新添加的元素的位置不为null，而且该位置已经存在链表了，那这个新元素就要和链表里的每一个元素都进行比较，一样就不存入，不一样就放在下面形成链表
- 随着元素加的原来越多，这个数组也越来越慢，就会用到影响因子。影响因子就是扩容时机，当数组中存入16*0.75 = 12的时候，数组就会扩容为原来的二倍，长度为32。当链表长度大于8且数组长度大于等于64时，那么当前链表会自动转成红黑树。所以JDK8以后的HashSet就是有数组、链表、红黑树三部分组成。
注意：存入自定义对象的时候，一定要重写hashCode和equals方法，要不然默认就是用地址值计算，没有意义。重些hashCode的目的是希望根据属性值计算，重写equals的目的是希望比较的时候比的也是对象的内部属性值。
HashSet的三个问题：
- HashSet为什么存和取顺序不一样？
- HashSet为什么没索引？
- HashSet是利用什么机制保证数据去重的？
问题1：我们存入第一个数据的时候，可能方法数组的后边，存入第二个数据的时候，放在数组前边。但是遍历数组的时候，可是要从前面开始遍历的，所以取的时候顺序和存的顺序可不一样啊。
问题2：因为HashSet不够纯粹，底层由三种结构组成，那你怎么定义谁是0谁是1呢。比如有的地方是链表，那么多数据都是一个索引，肯定不合适啊
问题3：通过HashCode和equal方法去重。HashCode可以获取哈希值，而哈希值就可以确定当前元素可以添加在数组的哪个位置，然后再去调用equals方法，判断对象的属性值是否相同，所以一定要重写这两个方法。String、Integer这种就不用重写，java给重写好了。
十.LinkedList
现在我们学习HashSet的子类LinkedHashSet，他没有什么特殊的方法，都是继承自Collection，我们只需要学习他的底层。这个Set集合有序、不重复、无索引，有序是指存取顺序一致。他的底层数据结构依然是哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序。
根据哈希值找到位置之后，存入进去，会产生一个链表指向它。第二个元素进去之后，第一个元素会记录第二个元素的地址值，而且第二个也会进去第一个的地址值，这就形成了双向链表。第三个元素存入位置和第二个一样，并且不是相同元素时，三挂在二下面形成链表，并且二三之间形成双向链表。
LinkedHashSet的效率没有HashSet高，因为前者的底层多做了一些事情，所以如果单纯去重还是要用HashSet。
十一.TreeSet
学习最后一个Set，叫做TreeSet，不重复，无索引，可排序。可排序的意思是按照元素的默认规则（由小到大）排序，TreeSet底层基于红黑树实现，增删改查性能良好。
TreeSet集合默认的规则
- 对于数值类型：Integer、Double，默认按照从小到大的顺序进行排序
- 对于字符串、字符按照字符在ASCII中的数字升序排列。如果字符串的字符数比较多，就从首字母开始比较，和字符串的长度没什么关系，因为只要有一个字符能确定大小关系，后面的都不会再看了。
我们如果要往TreeSet中添加自定义对象，一定要在添加之前自己来创建比较规则。
TreeSet有两种比较规则
- 默认排序/自然排序：JavaBean类实现Comparable接口指定比较规则
比如我要根据Student的年龄排序，需要指定排序规则，但不需要重写hashCode和equals方法，就是按照红黑树排序，添加一个元素，就要从根开始比较。
//在自定义类上实现Comparable接口，注意这个接口有泛型
public class Student implements Comparable<Student>{
@Override
//this：表示当前要添加的元素
//o：表示已经在红黑树存在的元素
//返@回值：
//负数：表示当前要添加的元素是小的，存左边
//正数：表示当前要添加的元素是大的，存右边
//0 :表示当前要添加的元素已经存在，舍弃
public int compareTo(Student o) {
System.out.println("--------------");
System.out.println("this:" + this);
System.out.println("o:" + o);
//指定排序的规则
//只看年龄，我想要按照年龄的升序进行排列
return this.getAge() - o.getAge();
}
}
- 比较器排序：创建TreeSet对象的时候，传递比较器Comparator指定规则
使用原则是默认使用第一种，第一种不满足了才使用第二种。
/*
需求：请自行选择比较器排序和自然排序两种方式；
要求：存入四个字符串， “c”, “ab”, “df”, “qwer”
按照长度排序，如果一样长则按照首字母排序
采取第二种排序方式：比较器排序
*/
TreeSet<String> ts = new TreeSet<>();
ts.add("c");
ts.add("ab");
ts.add("df");
ts.add("qwer");
System.out.println(ts);//[ab,c,df,qwer]
/*
默认情况下，就是首字母排序，为什么是这样呢，因为是String写好的代码
String继承了Comparable<String>接口并重写了compareTo方法，这就是字符串默认的排序规则，按照字母排序。
此时我们就可以采取第二种排序方法
*/
//o1表示当前要添加的元素
//o2表示已经在红黑树中存在的元素
//返回值规则跟第一种规则一样
TreeSet<String> ts1 = new TreeSet<>(new Comparator<String>(){
@Override
public int compare(String o1,String o2){
//按照长度排序
int i = o1.length() - o2.length();
//如果一样长则按照首字母排序，这里的comparaTo是String自带的，默认的比较规则
i = i == 0?o1.comparaTo(o2) : i;
return i;
}
});
//形参Comparator是一个函数式接口，所以可以用Lambda表达式
TreeSet<String> ts = new TreeSet<>((o1, o2)->{
// 按照长度排序
int i = o1.length() - o2.length();
//如果一样长则按照首字母排序
i = i == 0 ? o1.compareTo(o2) : i;
return i;
});
如果方式一和方式二都存在的情况下，以方式二为准。
现在我们的List接口和Set接口都学完了，总结一下什么场景回用到哪个集合：
- 如果想要集合中的元素可重复
- 用ArrayList集合，基于数组的
- 如果想集合中的元素可重复，而且增删操作多于查找操作
- 用LinkedList集合，基于链表的
- 如果想对集合中的元素去重
- 用HashSet集合，基于哈希表的
- 如果想对集合中的元素去重，而且保证存取顺序
- 用LinkedHashSet集合，基于哈希表和双链表，效率低于HashSet
- 如果想对集合中的元素排序
- 用TreeSet集合，基于红黑树，也可以用List排序
我是一个转码的小白，平时会在牛客中做选择题，在做题中遇到不会的内容就会去找视频或者文章学习，以此不断积累知识。这个专栏主要是记录一些我通过做题所学到的基础知识，希望能对大家有帮助
查看8道真题和解析
投递顺丰集团等公司10个岗位