集合（3）JavaSE_综合

1 集合

1.1 集合的概念及其结构

容器是什么？
数组，集合都是对多个数据进行存储操作的，简称为容器。
注意：这里的存储指的是内存层面的存储，而不是持久化存储（.txt,.avi,.jpg,数据库）。
为什么要学习集合？
数组的特点：
（1）数组一旦指定了长度，那么长度就被确定了，不可以更改。
EG: int[] arr = new int[6];
（2）数组一旦声明了类型以后，数组中只能存放这个类型的数据。数组中只能存放同一种类型的数据。
EG: int[] arr,String[] s,double[] d.....
数组的缺点：
（1）数组一旦指定了长度，那么长度就被确定了，不可以更改。
（2）删除，增加元素的效率低。
（3）数组中实际元素的数量是没有办法获取的，没有提供对应的方法或者属性来获取
（4）数组存储：对于某些具体要求，比如要求加入后的数组有序，其中元素可重复，或者无序的，不可重复的数组不能满足要求。
正因为上面的缺点，所以引入了一个新的存储数据的结构：集合。而集合又有很多种类，分别适用于不同问题。
集合继承结构图
Collection的继承结构图
Map的继承结构图

1.2 Collection

Collection的注意事项：
因为Collection是一个接口，所以我们不能直接创建它的对象，但是我们可以创建它的实现类ArrayList，然后用Collection接口变量来接收，这样ArrayList就只能使用Collection接口中的方法了。
Collection使用的代码实例：

public class Test {
    public static void main(String[] args) {
    /*Collection接口的常用方法：增加：add(E e) addAll(Collection<? extends E> c)删除：clear()删除所有 remove(Object o)删除指定修改：查看：iterator() size()判断：contains(Object o) equals(Object o) isEmpty()*///创建对象：接口不能创建对象，利用Collection的实现类ArrayList创建对象：Collection col = new ArrayList();//调用方法：//集合有一个特点：只能存放引用数据类型的数据，不能是基本数据类型//基本数据类型自动装箱，对应包装类。int--->Integercol.add(18);col.add(12);col.add(11);col.add(17);System.out.println(col/*.toString()*/);List list = Arrays.asList(new Integer[]{
    11, 15, 3, 7, 1});col.addAll(list);//将另一个集合添加入col中System.out.println(col);//col.clear();清空集合System.out.println(col);System.out.println("集合中元素的数量为："+col.size());System.out.println("集合是否为空："+col.isEmpty());boolean isRemove = col.remove(15);//如果集合中有15，就删除一次，否则不变System.out.println(col);System.out.println("集合中数据是否被删除："+isRemove);Collection col2 = new ArrayList();col2.add(18);col2.add(12);col2.add(11);col2.add(17);Collection col3 = new ArrayList();col3.add(18);col3.add(12);col3.add(11);col3.add(17);System.out.println(col2.equals(col3));//比较每个位置内容的值System.out.println(col2==col3);//地址一定不相等 falseSystem.out.println("是否包含元素："+col3.contains(117));//对集合遍历（对集合中元素进行查看）//方式1：普通for循环/*for(int i= 0;i<col.size();i++){col.}*///方式2：增强for循环for(Object o:col){
    System.out.println(o);}System.out.println("------------------------");//方式3：iterator()Iterator it = col.iterator();while(it.hasNext()){
    System.out.println(it.next());}}
}

迭代器iterator原理图：

1.2.1 List

List是继承Collection接口的一个接口。

使用代码实例：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
    public static void main(String[] args) {
    /*List接口中常用方法：增加：add(int index, E element)删除：remove(int index) remove(Object o)修改：set(int index, E element)查看：get(int index)判断：*/List list = new ArrayList();list.add(13);list.add(17);list.add(6);list.add(-1);list.add(2);list.add("abc");System.out.println(list);list.add(3,66);System.out.println(list);list.remove(2);//参数为int数，调用remove方法调用的是：remove(int index)System.out.println(list);list.remove("abc");//参数为String，调用remove方法调用的是：remove(object o)System.out.println(list);Object o = list.get(0);//获取索引为0的对象System.out.println(o);//List集合 遍历：//方式1：普通for循环：System.out.println("---------------------");for(int i = 0;i<list.size();i++){
    System.out.println(list.get(i));}//方式2：增强for循环：System.out.println("---------------------");for(Object obj:list){
    System.out.println(obj);}//方式3：迭代器：System.out.println("---------------------");Iterator it = list.iterator();while(it.hasNext()){
    System.out.println(it.next());}}
}

1.2.2 ArrayList

ArrayList是List的一个实现类，它的操作和List基本相同，只增加了有限几个方法。重点关注的是底层的实现：

1.2.2.1 JDK1.7的ArrayList源码

ArrayList的失误：
ArrayList实现List接口属于一种失误。集合创始人也承认了这个失误，但是在后续的版本中没有删除，觉得没必要。
ArrayList底层的重要属性：
ArrayList的初始化：
在JDK1.7中：在调用构造器的时候给底层数组elementData初始化，数组初始化长度为10：
初始化对应内存图：
ArrayList调用add方法代码实例：

        ArrayList al = new ArrayList();System.out.println(al.add("abc"));System.out.println(al.add("def"));

ArrayList中的add方法：
ArrayList中add方法中的ensureCapacityInternal方法：
（当数组中的10个位置都满了的时候就开始进行数组的扩容，扩容长度为原数组的1.5倍）
ArrayList中add方法中ensureCapacityInternal中的grow扩容方法：

1.2.2.2 JDK1.8的ArrayList源码

JDK1.8底层ArrayList的重要属性：
和JDK1.7一样依旧是Object类型的数组和size。
ArrayList调用构造器发生了改变：
初始化不会一开始就建立像JDK1.7一样一个长度为10的数组，而是一个空的数组。
ArrayList中的add方法：

1.2.3 Vector

Vector和ArrayList一样，是List的一个实现类。现在已经基本被放弃，但是面试会经常问两者的区别。

Vector和ArrayList区别：
（1）ArrayList底层扩容长度为原数组的1.5倍，线程不安全，效率高
（2）Vector底层扩容长度为原数组的2倍，线程安全(因为被synchronized修饰)，效率低（淘汰）
Vector底层代码：
（1）Vector构造器

（2）Vector的add方法

1.2.4 泛型（Generic）

1.2.4.1 泛型类和泛型接口

什么是泛型？
（1）泛型就相当于标签。形式：< > （被称为钻石运算符）
（2）集合容器类在设计阶段/声明阶段不能确定这个容器到底实际存的是什么类型的对象，所以在JDK1.5之前只能把元素类型设计为Object。JDK1.5之后使用泛型来解决，因为加入元素的类型不确定，因此此时把元素的类型设计成一个参数，而这个类型参数就叫做泛型。
（3）EG:
Collection<E>，List<E>，ArrayList<E> （这个< E >就是类型参数，即泛型。之后这些集合中就只能放入E这个类型的数据了。）
为什么使用泛型？
一般在使用集合时存入的一般都是相同类型的数据，以便管理。但如果没有泛型，现在什么引用类型都可以放入同一个集合中，会造成混乱。
没有使用泛型时，集合的默认基本类型：
没有确定泛型的具体类型，默认为Object
代码使用实例：

import java.util.ArrayList;
public class Test {
    public static void main(String[] args) {
    //创建一个ArrayList集合，向这个集合中存入学生的成绩：//加入泛型的优点：在编译时期就会对类型进行检查，不是泛型对应的类型就不可以添加入这个集合。ArrayList<Integer> al = new ArrayList<Integer>();al.add(98);al.add(18);al.add(39);al.add(60);al.add(83);/*运行之前就会报错al.add("丽丽");al.add(9.8);*///对集合遍历查看：/*for(Object obj:al){System.out.println(obj);}*/for(Integer i:al){
    System.out.println(i);}}
}

自定义泛型代码实例：

/*** GenericTest就是一个普通的类* GenericTest<E> 就是一个泛型类* <>里面就是一个参数类型，但是这个类型是什么呢？这个类型现在是不确定的，相当于一个占位* 但是现在确定的是这个类型一定是一个引用数据类型，而不是基本数据类型*/
class GenericTest<E> {
    int age;String name;E sex;public void a(E n){
    }public void b(E[] m){
    }
}
public class Test{
    public static void main(String[] args) {
    //GenericTest进行实例化：//(1)实例化的时候不指定泛型：如果实例化的时候不明确的指定类的泛型，那么认为此泛型为Object类型GenericTest gt1 = new GenericTest();gt1.a("abc");gt1.a(17);gt1.a(9.8);gt1.b(new String[]{
    "a","b","c"});//（2）实例化的时候指定泛型：---》推荐方式GenericTest<String> gt2 = new GenericTest<>();gt2.sex = "男";gt2.a("abc");gt2.b(new String[]{
    "a","b","c"});}
}

泛型的继承情况：
（1）父类如果指定泛型，那么子类会自然继承这个泛型

class SubGenericTest extends GenericTest<Integer>{
    }
public class Test{
    public static void main(String[] args) {
    //指定父类泛型，那么子类就不需要再指定泛型了，可以直接使用SubGenericTest sgt = new SubGenericTest();sgt.a(19);}
}

（2）父类不指定泛型，那么子类也会变成一个泛型类，这个E类型可以在创建子类对象的时候确定：

class SubGenericTest2<E> extends GenericTest<E>{
    
}
class Demo{
    public static void main(String[] args) {
    SubGenericTest2<String> s = new  SubGenericTest2<>();s.a("abc");s.sex = "女";}
}

泛型可以定义多个参数类型

public class TestGeneric<A,B,C>{
    A age;B name;C sex;public void a(A m,B n,C x){
    }
}

注意构造器不能这样写：（不加泛型即可）
不同的泛型的引用类型不可以相互赋值：
泛型类中的静态方法不可以使用泛型
因为泛型是创建对象的时候确定的，而static修饰的方法是在类加载的时候，而这个时候无法判断A是什么，所以不可以。
泛型不可以直接拿来用

1.2.4.2 泛型方法

/*** 1.什么是泛型方法：* 不是所有带泛型的方法就是泛型方法* 泛型方法有要求：这个方法的泛型的参数类型要和当前的类的泛型无关* 换个角度：* 泛型方法对应的那个泛型参数类型 和 当前所在的这个类 是否是泛型类，泛型是啥 无关* 2.泛型方法定义的时候，前面要加上<T>* 原因：如果不加的话，会把T当做一种数据类型，然而代码中没有T类型那么就会报错* 3.T的类型是在调用方法的时候确定的* 4.泛型方法可否是静态方法？可以是静态方法 注意修饰符要放在泛型前面*/
class TestGeneric<E> {
    //不是泛型方法 （不能是静态方法）public static void a(E e){
    }//是泛型方法public static <T>  void b(T t){
    }public <T>  void b(T t){
    }
}
public class Test{
    public static void main(String[] args) {
    TestGeneric<String> tg = new TestGeneric<>();tg.a("abc");tg.b("abc");tg.b(19);tg.b(true);}
}

1.2.4.3 通配符

在没有通配符的时候会有什么影响：
下面的a方法，相当于方法的重复定义，报错

public class Test {
    public void a(List<Object> list){
    }public void a(List<String> list){
    }public void a(List<Integer> list){
    }
}

引入通配符之后的效果：
发现： A 和 B是子类父类的关系，G< A >和G< B >不存在子类父类关系，是并列的
加入通配符？后，G< ? >就变成了 G< A >和G< B >的父类

public class Test {
    public static void main(String[] args) {
    List<Object> list1 = new ArrayList<>();List<String> list2 = new ArrayList<>();List<Integer> list3 = new ArrayList<>();List<?> list = null;list = list1;list = list2;list = list3;}
}

使用通配符代码实例：

public class Test {
    /*public void a(List<Object> list){}public void a(List<String> list){}public void a(List<Integer> list){}*/public void a(List<?> list){
    //内部遍历的时候用Object即可，不用？for(Object a:list){
    System.out.println(a);}}
}
class Demo{
    public static void main(String[] args) {
    Test t = new Test();t.a(new ArrayList<Integer>());t.a(new ArrayList<String>());t.a(new ArrayList<Object>());}
}

使用通配符的细节：
如果一个方法定义中使用了通配符，那么不能随意的写入数据

public class Test {
    public void a(List<?> list){
    //1.遍历：传入的是List<?>类型的，但是具体是谁不知道，所以用Object来接受for(Object a:list){
    System.out.println(a);}//2.数据的写入操作 ：//list.add("abc");-->出错，不能随意的添加数据，因为传入的实参不知道?具体是哪个类型list.add(null);//3.数据的读取操作：Object s = list.get(0);}
}
class T{
    public static void main(String[] args) {
    Test t = new Test();t.a(new ArrayList<Integer>());t.a(new ArrayList<String>());t.a(new ArrayList<Object>());}
}

利用通配符实现泛型受限：

public class Test {
    public static void main(String[] args) {
    //a,b,c三个集合是并列的关系：List<Object> a = new ArrayList<>();List<Person> b = new ArrayList<>();List<Student> c = new ArrayList<>();/*开始使用泛型受限：泛型的上限List<? extends Person>:就相当于：List<? extends Person>是List<Person>的父类，是List<Person的子类>的父类*/List<? extends Person> list1 = null;list1 = a; //报错，因为a中泛型不是Person或者它的的子类list1 = b; //可以list1 = c; //可以/*开始使用泛型受限：泛型的下限List<? super Person>就相当于：List<? super Person>是List<Person>的父类，是List<Person的父类>的父类*/List<? super Person> list2 = null;list2 = a;	//可以list2 = b;	//可以list3 = c;  //不行，因为Student不是Person的父类}
}

1.2.5 LinkedList

LinkedList和ArrayList、Vector一样是List接口的实现类。

LinkedList常用方法和遍历的代码实例：

public class Test {
    public static void main(String[] args) {
    /*LinkedList常用方法：增加 addFirst(E e) addLast(E e)offer(E e) offerFirst(E e) offerLast(E e)删除 poll()pollFirst() pollLast() ---》JDK1.6以后新出的方法，提高了代码的健壮性removeFirst() removeLast()修改查看 element() ：获取但是不移除第一个元素getFirst() getLast()indexOf(Object o)：返回第一次出现o的索引 lastIndexOf(Object o)peek()：获取但是不移除头peekFirst() peekLast()判断*///创建一个LinkedList集合对象：LinkedList<String> list = new LinkedList<>();list.add("aaaaa");list.add("bbbbb");list.add("ccccc");list.add("ddddd");list.add("eeeee");list.add("bbbbb");list.add("fffff");list.addFirst("jj");list.addLast("hh");list.offer("kk");//添加元素在尾端list.offerFirst("pp");list.offerLast("rr");System.out.println(list);//LinkedList可以添加重复数据System.out.println(list.poll());//删除头上的元素并且将元素输出System.out.println(list.pollFirst());System.out.println(list.pollLast());System.out.println(list.removeFirst());System.out.println(list.removeLast());System.out.println(list);//LinkedList可以添加重复数据list.clear();//清空集合System.out.println(list);/*System.out.println(list.pollFirst());*//*System.out.println(list.removeFirst());报错：Exception in thread "main" java.util.NoSuchElementException*///集合的遍历：System.out.println("---------------------");//普通for循环：for(int i = 0;i<list.size();i++){
    System.out.println(list.get(i));}System.out.println("---------------------");//增强for：for(String s:list){
    System.out.println(s);}System.out.println("---------------------");//迭代器：/*Iterator<String> it = list.iterator();while(it.hasNext()){System.out.println(it.next());}*///下面这种方式好，节省内存for(Iterator<String> it = list.iterator();it.hasNext();){
    System.out.println(it.next());}}

ArrayList和LiskedList的底层区别：
LinkedList源码分析

public class LinkedList<E>{
    //E是一个泛型，具体的类型要在实例化的时候才会最终确定transient int size = 0;//集合中元素的数量//Node的内部类private static class Node<E> {
    E item;//当前元素Node<E> next;//指向下一个元素地址Node<E> prev;//上一个元素地址Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;this.next = next;this.prev = prev;}}transient Node<E> first;//链表的首节点transient Node<E> last;//链表的尾节点//空构造器：public LinkedList() {
    }//添加元素操作：public boolean add(E e) {
    linkLast(e);return true;}void linkLast(E e) {
    //添加的元素efinal Node<E> l = last;//将链表中的last节点给l 如果是第一个元素的话 l为null//将元素封装为一个Node具体的对象：final Node<E> newNode = new Node<>(l, e, null);//将链表的last节点指向新的创建的对象：last = newNode;if (l == null)//如果添加的是第一个节点first = newNode;//将链表的first节点指向为新节点else//如果添加的不是第一个节点 l.next = newNode;//将l的下一个指向为新的节点size++;//集合中元素数量加1操作modCount++;}//获取集合中元素数量public int size() {
    return size;}//通过索引得到元素：public E get(int index) {
    checkElementIndex(index);//健壮性考虑return node(index).item;}Node<E> node(int index) {
    //如果index在链表的前半段，那么从前往后找if (index < (size >> 1)) {
    Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {
    //如果index在链表的后半段，那么从后往前找Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}
}

1.2.6 iterator(),Iterator,Iterable关系和ListIterator

对应的关系
hasNext(),next()的具体实现
增强for循环，底层也是通过迭代器实现的：可以在增强for语句上加入断点Debug验证
为什么使用ListIterator：
因为普通的Iterator中，如果有两个指针同时对集合操作会出错

public class Test {
    public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();list.add("aa");list.add("bb");list.add("cc");//在"cc"之后添加一个字符串"kk"Iterator<String> it = list.iterator();while(it.hasNext()){
    if("cc".equals(it.next())){
    list.add("kk");}}}
}

集合（3）JavaSE
出错原因：就是迭代器和list同时对集合进行操作：
解决办法：让一个人做，引入新的迭代器：ListIterator

public class Test {
    public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();list.add("aa");list.add("bb");list.add("cc");list.add("dd");list.add("ee");//在"cc"之后添加一个字符串"kk"ListIterator<String> it = list.listIterator();//正向遍历while(it.hasNext()){
    if("cc".equals(it.next())){
    it.add("kk"); //都是it来做}}//逆向遍历：while(it.hasPrevious()){
    System.out.println(it.previous());}System.out.println(list);}
}

1.2.7 HashSet

HashSet是Set接口的一个实现类。

Set和List的区别：
List：可以有重复值；放入的数据是排列是有序的；底层结构是数组或者是链表
Set：不能有重复值；放入的数据是无序加入的(无论是String还是Integer都是如此)。底层结构是哈希表（数组+链表）
想要放入HashSet中的数据类型必须有hashcode和equals方法，这样才能使HashSet计算出存储的位置。
注意：Set中的无序并不是说是随机乱排序的，而是根据hashcode和equals方法决定的

public class Test {
    public static void main(String[] args) {
    //创建一个HashSet集合：HashSet<Integer> hs = new HashSet<>();System.out.println(hs.add(19));//truehs.add(5);hs.add(20);System.out.println(hs.add(19));//false 这个19没有放入到集合中hs.add(41);hs.add(0);System.out.println(hs.size());//唯一，无序System.out.println(hs);//[0, 19, 20, 5, 41]}
}

HashSet原理图

1.2.8 LinkedHashSet

LinkedHashSet其实就是在HashSet的基础上，多了一个总的链表，这个总链表将放入的元素串在一起，方便有序的遍历。

使用代码实例：

public class TestInteger {
    public static void main(String[] args) {
    //创建一个LinkedHashSet集合：LinkedHashSet<Integer> hs = new LinkedHashSet<>();System.out.println(hs.add(19));//truehs.add(5);hs.add(20);System.out.println(hs.add(19));//false 这个19没有放入到集合中hs.add(41);hs.add(0);System.out.println(hs.size());//唯一，无序System.out.println(hs);//[19, 5, 20, 41, 0]}
}

原理图：

1.2.9 比较器

在上一章中的2.7 String类中，以及详细介绍了comparaTo方法。下面介绍比较器的具体细节

比较器就是对两个对象根据某种规则进行比较的方法。
比较器可以在类的内部定义（也称为内部比较器），也可以在类外部自定义一个比较器（外部比较器），然后对外部实例进行比较。
大多数情况下使用的是外部比较器。（因为具有多态的特性，扩展性好）
内部比较器使用代码实例：（方法：要比较的类先实现Comparable接口，并且实现compareTo()方法即可）

public class Student implements Comparable<Student>{
    private int age;private double height;private String name;public Student(int age, double height, String name) {
    this.age = age;this.height = height;this.name = name;}@Overridepublic String toString() {
    return "Student{" +"age=" + age +", height=" + height +", name='" + name + '\'' +'}';}@Overridepublic int compareTo(Student o) {
    //按照年龄进行比较：/* return this.age-o.age;*///按照身高比较/* return ((Double)(this.height)).compareTo((Double)(o.height));*///按照名字比较：return this.name.compareTo(o.name);}
}
```java
public class Test {
    public static void main(String[] args) {
    //比较两个学生：Student s1 = new Student(14,160.5,"alili");Student s2 = new Student(14,170.5,"bnana");System.out.println(s1.compareTo(s2));//-1}
}

外部比较器使用代码实例：（方法：自定义一个类，让这个类实现Comparator接口，并且实现compare()方法即可）

class Student{
    int age;double height;String name;public Student(int age, double height, String name) {
    this.age = age;this.height = height;this.name = name;}@Overridepublic String toString() {
    return "Student{" +"age=" + age +", height=" + height +", name='" + name + '\'' +'}';}
}
class MyComparator1 implements Comparator<Student>{
    @Overridepublic int compare(Student o1, Student o2) {
    return o1.age-o2.age;}
}
class MyComparator2 implements Comparator<Student>{
    @Overridepublic int compare(Student o1, Student o2) {
    return ((Double)o1.height).compareTo((Double)o2.height);}
}
class MyComparator3 implements Comparator<Student>{
    @Overridepublic int compare(Student o1, Student o2) {
    return o1.name.compareTo(o2.name);}
}
public class Test {
    public static void main(String[] args) {
    //比较两个学生：Student s1 = new Student(14,160.5,"alili");Student s2 = new Student(14,170.5,"bnana");MyComparator1 myComparator1 = new MyComparator1();MyComparator2 myComparator2 = new MyComparator2();MyComparator3 myComparator3 = new MyComparator3();System.out.println(myComparator1.compare(s1,s2));//0System.out.println(myComparator2.compare(s1,s2));//-1System.out.println(myComparator3.compare(s1,s2));//-1}
}

1.2.10 TreeSet

TreeSet存储的特点是唯一，有序。（HashSet是唯一，无序）
要放入TreeSet的数据类型必须是实现了比较器的类，这样才能使TreeSet计算出存储的位置。
TreeSet的使用代码实例
（1）Integer和String底层已经完成了比较器功能，可以直接存入

public class Test {
    public static void main(String[] args) {
    //创建一个TreeSet:。测试存储int类型TreeSet<Integer> ts1 = new TreeSet<>();ts1.add(12);ts1.add(3);ts1.add(7);ts1.add(9);ts1.add(3);ts1.add(16);System.out.println(ts1.size());//5 重复时不存System.out.println(ts1);//[3, 7, 9, 12, 16] 按升序存储//创建一个TreeSet。测试存储String类型（底层已经实现了比较器）TreeSet<String> ts2 = new TreeSet<>();ts2.add("elili");ts2.add("blili");ts2.add("alili");ts2.add("elili");ts2.add("clili");ts2.add("flili");ts2.add("glili");System.out.println(ts2.size());//6 elili重复时不存入System.out.println(ts2);//[alili, blili, clili, elili, flili, glili]}
}

TreeSet存储的底层是一个二叉树。

（2）自定义类必须要实现比较器，可以通过内部比较器和外部比较器两种。
1 内部比较器

class Student implements Comparable<Student> {
    int age;String name;public Student(int age, String name) {
    this.age = age;this.name = name;}@Overridepublic int compareTo(Student o) {
    return this.getAge()-o.getAge();}
}
public class Test {
    public static void main(String[] args) {
    //创建一个TreeSet:TreeSet<Student> ts = new TreeSet<>();ts.add(new Student(10,"elili"));ts.add(new Student(8,"blili"));ts.add(new Student(4,"alili"));ts.add(new Student(9,"elili"));ts.add(new Student(10,"flili"));ts.add(new Student(1,"dlili"));System.out.println(ts.size());// 5 age为10的重复了，所以后加入的不存入TreeSet中System.out.println(ts);/* [Student{age=1, name='dlili'}, Student{age=4, name='alili'}, Student{age=8, name='blili'}, Student{age=9, name='elili'}, Student{age=10, name='elili'}]*/}
}

2 外部比较器

class Student{
    int age;double height;String name;public Student(int age,  String name) {
    this.age = age;this.height = height;this.name = name;}@Overridepublic String toString() {
    return "Student{" +"age=" + age +", name='" + name + '\'' +'}';}
}
class MyComparator implements Comparator<Student>{
    @Overridepublic int compare(Student o1, Student o2) {
    return o1.name.compareTo(o2.name);}
}
public class Test{
    public static void main(String[] args){
    //创建一个TreeSet://利用外部比较器，必须自己定义MyComparator myComparator = new Mycomparator();//myComparator底层比较的是字符串TreeSet<Student> ts = new TreeSet(myComparator);ts.add(new Student(10,"elili"));ts.add(new Student(8,"blili"));ts.add(new Student(4,"alili"));ts.add(new Student(9,"elili"));ts.add(new Student(10,"flili"));ts.add(new Student(1,"dlili"));System.out.println(ts.size());//5System.out.println(ts);/* [Student{age=4, name='alili'}, Student{age=8, name='blili'}, Student{age=1, name='dlili'}, Student{age=10, name='elili'}, Student{age=10, name='flili'}]*/}
}

外部类可以换一种写法

class Student{
    int age;double height;String name;public Student(int age,  String name) {
    this.age = age;this.height = height;this.name = name;}@Overridepublic String toString() {
    return "Student{" +"age=" + age +", name='" + name + '\'' +'}';}
}
public class Test {
    public static void main(String[] args) {
    //创建一个TreeSet://利用外部比较器，必须自己制定：TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
    @Overridepublic int compare(Student o1, Student o2) {
    return o1.getName().compareTo(o2.getName());}});//一旦指定外部比较器，那么就会按照外部比较器来比较ts.add(new Student(10,"elili"));ts.add(new Student(8,"blili"));ts.add(new Student(4,"alili"));ts.add(new Student(9,"elili"));ts.add(new Student(10,"flili"));ts.add(new Student(1,"dlili"));System.out.println(ts.size());System.out.println(ts);}
}

1.3 Map

1.3.1 HashMap

和Collcetion接口不同的是，Collection是单值存储的，而Map接口是以键值对的形式成对的存入数据的。键值对（key，value）中，其中key是以set集合存储的，所以key必须唯一
HashMap是Map的一个实现类，所以存入的数据同样是无序排列的，键值对中键key唯一。
想要放入HashMap中的数据类型必须有hashcode和equals方法，这样才能使HashMap计算出存储的位置。
HashMap的使用代码实例：

public class Test {
    public static void main(String[] args) {
    /*增加：put(K key, V value)删除：clear() remove(Object key)修改：查看：entrySet() get(Object key) keySet() size() values()判断：containsKey(Object key) containsValue(Object value)equals(Object o) isEmpty()*///创建一个Map集合：无序，唯一Map<String,Integer> map = new HashMap<>();System.out.println(map.put("lili", 10101010));//0map.put("nana",12345234);map.put("feifei",34563465);System.out.println(map.put("lili", 34565677));//10101010map.put("mingming",12323);/*map.clear();清空*//*map.remove("feifei");移除*/System.out.println(map.size());//4System.out.println(map);//{nana=12345234, lili=34565677, mingming=12323, feifei=34563465}System.out.println(map.containsKey("lili"));//trueSystem.out.println(map.containsValue(12323));//trueMap<String,Integer> map2 = new HashMap<>();System.out.println(map2.put("lili", 10101010));//nullmap2.put("nana",12345234);map2.put("feifei",34563465);System.out.println(map2.put("lili", 34565677));//101010map2.put("mingming",12323);System.out.println(map==map2);//falseSystem.out.println(map.equals(map2));//true equals进行了重写，比较的是集合中的值是否一致System.out.println("判断是否为空："+map.isEmpty());//falseSystem.out.println(map.get("nana"));//12345234System.out.println("-----------------------------------");//keySet()对集合中的key进行遍历查看：Set<String> set = map.keySet();for(String s:set){
    System.out.println(s);}System.out.println("-----------------------------------");//values()对集合中的value进行遍历查看：//nana//lili//mingming//feifeiCollection<Integer> values = map.values();for(Integer i:values){
    System.out.println(i);}System.out.println("-----------------------------------");//通过key遍历value。get(Object key) keySet()//12345234//34565677//12323//34563465Set<String> set2 = map.keySet();for(String s:set2){
    System.out.println(map.get(s));}System.out.println("-----------------------------------");//entrySet()：生成一个Set集合，集合里面装一个一个的Map下的Entry对象，Entry就是Map中的 键值对 对象//nana----12345234//lili----34565677//mingming----12323//feifei----34563465Set<Map.Entry<String, Integer>> entries = map.entrySet();for(Map.Entry<String, Integer> e:entries){
    System.out.println(e.getKey()+"----"+e.getValue());}}
}

HashMap源码解析
（1）原理图解释：
EG：

public class Test {
    public static void main(String[] args) {
    //JDK1.7以后支持后面的<>中内容可以不写HashMap<Integer,String> hm = new HashMap<>();System.out.println(hm.put(12,"丽丽"));//nullSystem.out.println(hm.put(7,"菲菲"));//nullSystem.out.println(hm.put(19,"露露"));//nullSystem.out.println(hm.put(12,"明明"));//丽丽System.out.println(hm.put(6,"莹莹"));//nullSystem.out.println("集合的长度："+hm.size());//集合的长度：4System.out.println("集合中内容查看："+hm);//{19=露露, 6=莹莹, 7=菲菲, 12=明明}}
}

集合（3）JavaSE
（2）源代码归总

//HashMap的重要属性以及重要方法归总：（不可运行）
public class HashMap<K,V>extends AbstractMap<K,V> //【1】继承的AbstractMap中，已经实现了Map接口//【2】又实现了这个接口，多余，但是设计者觉得没有必要删除，就这么地了implements Map<K,V>, Cloneable, Serializable{
    //【3】后续会用到的重要属性：先粘贴过来：static final int DEFAULT_INITIAL_CAPACITY = 16;//哈希表主数组的默认长度//定义了一个float类型的变量，以后作为：默认的装填因子，加载因子是表示Hsah表中元素的填满的程度//太大容易引起哈西冲突，太小容易浪费 0.75是经过大量运算后得到的最好值//这个值其实可以自己改，但是不建议改，因为这个0.75是大量运算得到的static final float DEFAULT_LOAD_FACTOR = 0.75f;transient Entry<K,V>[] table;//主数组,每个元素为Entry类型transient int size;int threshold;//数组扩容的界限值,门槛值 16*0.75=12 final float loadFactor;//用来接收装填因子的变量//【4】查看构造器：内部相当于：this(16,0.75f);调用了当前类中的带参构造器public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}//【5】本类中带参数构造器：--》作用给一些数值进行初始化的！public HashMap(int initialCapacity, float loadFactor) {
    //【6】给capacity赋值，capacity的值一定是 大于你传进来的initialCapacity 的 最小的 2的倍数int capacity = 1;while (capacity < initialCapacity)capacity <<= 1;//【7】给loadFactor赋值，将装填因子0.75赋值给loadFactorthis.loadFactor = loadFactor;//【8】数组扩容的界限值,门槛值threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//【9】给table数组赋值，初始化数组长度为16table = new Entry[capacity];}//【10】调用put方法：public V put(K key, V value) {
    //【11】对空值的判断if (key == null)return putForNullKey(value);//【12】调用hash方法，获取哈希码int hash = hash(key);//【14】得到key对应在数组中的位置int i = indexFor(hash, table.length);//【16】如果你放入的元素，在主数组那个位置上没有值，e==null 那么下面这个循环不走//当在同一个位置上放入元素的时候for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;//哈希值一样 并且 equals相比一样 //(k = e.key) == key 如果是一个对象就不用比较equals了if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;//【17】走addEntry添加这个节点的方法：addEntry(hash, key, value, i);return null;}//【13】hash方法返回这个key对应的哈希值，内部进行二次散列，为了尽量保证不同的key得到不同的哈希码！final int hash(Object k) {
    int h = 0;if (useAltHashing) {
    if (k instanceof String) {
    return sun.misc.Hashing.stringHash32((String) k);}h = hashSeed;}//k.hashCode()函数调用的是key键值类型自带的哈希函数，//由于不同的对象其hashCode()有可能相同，所以需对hashCode()再次哈希，以降低相同率。h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor)./*接下来的一串与运算和异或运算，称之为“扰动函数”，扰动的核心思想在于使计算出来的值在保留原有相关特性的基础上，增加其值的不确定性，从而降低冲突的概率。不同的版本实现的方式不一样，但其根本思想是一致的。往右移动的目的，就是为了将h的高位利用起来，减少哈西冲突*/h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}//【15】返回int类型数组的坐标static int indexFor(int h, int length) {
    //其实这个算法就是取模运算：h%length，取模效率不如位运算return h & (length-1);}//【18】调用addEntryvoid addEntry(int hash, K key, V value, int bucketIndex) {
    //【25】size的大小 大于 16*0.75=12的时候，比如你放入的是第13个，这第13个你打算放在没有元素的位置上的时候if ((size >= threshold) && (null != table[bucketIndex])) {
    //【26】主数组扩容为2倍resize(2 * table.length);//【30】重新调整当前元素的hash码hash = (null != key) ? hash(key) : 0;//【31】重新计算元素位置bucketIndex = indexFor(hash, table.length);}//【19】将hash,key,value,bucketIndex位置 封装为一个Entry对象：createEntry(hash, key, value, bucketIndex);}//【20】void createEntry(int hash, K key, V value, int bucketIndex) {
    //【21】获取bucketIndex位置上的元素给eEntry<K,V> e = table[bucketIndex];//【22】然后将hash, key, value封装为一个对象，然后将下一个元素的指向为e （链表的头插法）//【23】将新的Entry放在table[bucketIndex]的位置上table[bucketIndex] = new Entry<>(hash, key, value, e);//【24】集合中加入一个元素 size+1size++;}//【27】void resize(int newCapacity) {
    Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;return;}//【28】创建长度为newCapacity的数组Entry[] newTable = new Entry[newCapacity];boolean oldAltHashing = useAltHashing;useAltHashing |= sun.misc.VM.isBooted() &&(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);boolean rehash = oldAltHashing ^ useAltHashing;//【28.5】转让方法：将老数组中的东西都重新放入新数组中transfer(newTable, rehash);//【29】老数组替换为新数组table = newTable;//【29.5】重新计算threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}//【28.6】void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;for (Entry<K,V> e : table) {
    while(null != e) {
    Entry<K,V> next = e.next;if (rehash) {
    e.hash = null == e.key ? 0 : hash(e.key);}//【28.7】将哈希值，和新的数组容量传进去，重新计算key在新数组中的位置int i = indexFor(e.hash, newCapacity);//【28.8】头插法e.next = newTable[i];//获取链表上元素给e.nextnewTable[i] = e;//然后将e放在i位置 e = next;//e再指向下一个节点继续遍历}}}
}

（3）细节解析（面试题）：HashMap中主数组的长度为2的倍数的原因:
主数组长度为2的倍数
集合（3）JavaSE
因为这个length的长度，会影响 key的位置：
key的位置的计算：（实际上这个算法就是： h%(length-1) 。但是取模的话效率太低，所以用位运算效率会很高。）

原因1：h&(length-1)和h%(length-1) 等效的前提就是 length必须是2的整数倍。
原因2：如果不是2的整数倍，那么哈西碰撞哈西冲突的概率就高了很多。
eg：位运算就涉及到 length是不是2的整数倍：
比如是2的整数倍：h&(length-1)：
集合（3）JavaSE
（并且这个得到的索引值，一定在 0-15之间（数组是16的时候））

比如如果不是2的整数倍：

（4）细节讲解（面试题）：装填因子为0.75的原因：
如果装填因子是1，那么数组满了再扩容，可以做到最大的空间利用率。
但是这是一个理想状态，元素不可能完全的均匀分布，很可能就哈西碰撞产生链表了。产生链表的话查询时间就长了。
—》空间好，时间不好
如果装填因子搞小一点，如果是0.5的话，就浪费空间，但是可以做到到0.5就扩容，然后哈西碰撞就少。另外因为不产生链表的话，那么查询效率很高
—》时间好，空间不好

所以我们为了平衡这种因素，就取值为0.75。
（5）HashSet底层原理
HashSet实际上底层就是使用了HashMap来构造的。所以搞懂了HashMap就可以掌握HashSet。

public class HashSet<E>{
    //重要属性：private transient HashMap<E,Object> map;private static final Object PRESENT = new Object();//构造器：public HashSet() {
    map = new HashMap<>();//HashSet底层就是利用HashMap来完成的}   public boolean add(E e) {
    return map.put(e, PRESENT)==null;}      
}

1.3.2 TreeMap

TreeMap和HashMap都是Map的实现类，不同的是TreeMap中键值对中键key的存储方式必须是根据某种规则有序排列的。
要放入TreeMap的数据类型必须是实现了比较器的类，这样才能使TreeMap计算出存储的位置。
TreeMap使用的代码实例：

class Student {
    int age;double height;String name;public Student(int age,String name,double height) {
    this.age = age;this.height = height;this.name = name;}@Overridepublic String toString() {
    return "Student{" +"age=" + age +", height=" + height +", name='" + name + '\'' +'}';}
}
public class Test {
    public static void main(String[] args) {
    Map<Student,Integer> map = new TreeMap<>(new Comparator<Student>() {
    @Overridepublic int compare(Student o1, Student o2) {
    return ((Double)(o1.height)).compareTo((Double)(o2.height));}});map.put(new Student(19,"blili",170.5),1001);map.put(new Student(18,"blili",150.5),1003);map.put(new Student(19,"alili",180.5),1023);map.put(new Student(17,"clili",140.5),1671);map.put(new Student(10,"dlili",160.5),1891);map.put(new Student(10,"elili",160.5),1891);//比较器是对升高height比较，所以160.5相同，elili不再存入System.out.println(map);/*{Student{age=17, height=140.5, name='clili'}=1671,Student{age=18, height=150.5, name='blili'}=1003,Student{age=10, height=160.5, name='dlili'}=1891,Student{age=19, height=170.5, name='blili'}=1001,Student{age=19, height=180.5, name='alili'}=1023}*/System.out.println(map.size());//5}
}

TreeMap源码解析
（1）原理图解

（2）源码归总

public class TreeMap<K,V>{
    //重要属性：//外部比较器：private final Comparator<? super K> comparator;//树的根节点：private transient Entry<K,V> root = null;//集合中元素的数量：private transient int size = 0;//空构造器:public TreeMap() {
    comparator = null;//如果使用空构造器，那么底层就不使用外部比较器}//有参构造器：public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;//如果使用有参构造器，那么就相当于指定了外部比较器}public V put(K key, V value) {
    //k,V的类型在创建对象的时候确定了//如果放入的是第一对元素，那么t的值为nullEntry<K,V> t = root;//在放入第二个节点的时候，root已经是根节点了//如果放入的是第一个元素的话，走入这个if中：if (t == null) {
    //自己跟自己比compare(key, key); // type (and possibly null) check//根节点确定为rootroot = new Entry<>(key, value, null);//size值变为1size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable paths//将外部比较器赋给cpr:Comparator<? super K> cpr = comparator;//cpr不等于null，意味着你刚才创建对象的时候调用了有参构造器，指定了外部比较器if (cpr != null) {
    do {
    parent = t;cmp = cpr.compare(key, t.key);//将元素的key值做比较//cmp返回的值就是int类型的数据：//要是这个值《0 =0 》0if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;else//cpm==0//如果key的值一样，那么新的value替换老的value 但是key不变 因为key是唯一的return t.setValue(value);} while (t != null);}//cpr等于null，意味着你刚才创建对象的时候调用了空构造器，没有指定外部比较器，使用内部比较器else {
    if (key == null)throw new NullPointerException();Comparable<? super K> k = (Comparable<? super K>) key;do {
    parent = t;cmp = k.compareTo(t.key);//将元素的key值做比较if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);size++;//size加1 操作modCount++;return null;}   
}static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;V value;Entry<K,V> left = null;Entry<K,V> right = null;Entry<K,V> parent;boolean color = BLACK;}

1.4 Collection工具类

public class Test {
    public static void main(String[] args) {
    //Collections不支持创建对象，因为构造器私有化了/*Collections cols = new Collections();*///里面的属性和方法都是被static修饰，我们可以直接用类名.去调用即可：//常用方法：//addAll：ArrayList<String> list = new ArrayList<>();list.add("cc");list.add("bb");list.add("aa");Collections.addAll(list,"ee","dd","ff");Collections.addAll(list,new String[]{
    "gg","oo","pp"});System.out.println(list);//[cc, bb, aa, ee, dd, ff, gg, oo, pp]//binarySearch二分查找 必须在有序的集合中查找：--》排序：Collections.sort(list);//sort提供的是升序排列System.out.println(list);//[aa, bb, cc, dd, ee, ff, gg, oo, pp]//binarySearch:二分查找System.out.println(Collections.binarySearch(list, "cc"));//2 cc在集合中第二个位置//copy:替换方法ArrayList<String> list2 = new ArrayList<>();Collections.addAll(list2,"tt","ss");Collections.copy(list,list2);//将list2的内容替换到list上去System.out.println(list);//[tt, ss, cc, dd, ee, ff, gg, oo, pp]System.out.println(list2);//[tt, ss]//fill 填充Collections.fill(list2,"yyy");System.out.println(list2);//[yyy, yyy]}
}

（3）TreeSet源码解析
TreeSet类似，底层也是使用了TreeMap。（和HashSet和HashMap的关系一样）

public class TreeSet<E> extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable{
    //重要属性：private transient NavigableMap<E,Object> m;private static final Object PRESENT = new Object();//在调用空构造器的时候，底层创建了一个TreeMappublic TreeSet() {
    this(new TreeMap<E,Object>());}TreeSet(NavigableMap<E,Object> m) {
    this.m = m;}public boolean add(E e) {
    return m.put(e, PRESENT)==null;}    
}