Collection集合，List集合，set集合，Map集合

集合框架

认识集合

集合是一种容器，用来装数据的，类似于数组，但集合的大小可变，开发中也非常常用。

集合体系结构

常用集合有哪些？各自有啥特点？

1. Collection(接口)：单列集合：每个元素（数据）只包含一个值。
   • List(接口)：添加的元素是有序、可重复、有索引。
     1. ArrayList：有序、可重复、有索引。
     2. LinkedList：有序、可重复、有索引。
   • Set(接口)：无序、不重复、无索引
     1. HashSet：无序、不重复、无索引
        • LinkedHashSet：有序、不重复、无索引
     2. TreeSet：按照大小默认升序排序、不重复、无索引
2. Map(接口)：双列集合：每个元素包含两个值（键值对）。
   • HashMap：
     • LinkedHashMap
   • TreeMap

Collection的功能

常用功能

为啥要先学Collection的常用方法？
Collection是单列集合的祖宗，它规定的方法（功能）是全部单列集合都会继承的。

方法名	说明
public boolean add(E e)	把给定的对象添加到当前集合中
public void clear()	清空集合中所有的元素
public boolean remove(E e)	把给定的对象在当前集合中删除
public boolean contains(Object obj)	判断当前集合中是否包含给定的对象
public boolean isEmpty()	判断当前集合是否为空
public int size()	返回集合中元素的个数。
public Object[] toArray()	把集合中的元素，存储到数组中

三种遍历方式

方式1
迭代器是用来遍历集合的专用方式(数组没有迭代器)，在Java中迭代器的代表是Iterator。
Collection集合获取迭代器的方法
通过迭代器获取集合的元素，如果取元素越界会出现什么异常?
会出现NoSuchElementException异常。

方法名称	说明
Iterator<E> iterator()	返回集合中的迭代器对象，该迭代器对象默认指向当前集合的第一个元素

Iterator迭代器中的常用方法

方法名称	说明
boolean hasNext()	询问当前位置是否有元素存在，存在返回true ,不存在返回false
E next()	获取当前位置的元素，并同时将迭代器对象指向下一个元素处。

Iterator<String> it = names.iterator();while (it.hasNext()) {String name = it.next();System.out.println(name);}

方式2增强for循环

// for (元素的数据类型 变量名 : 数组或者集合) { }
Collection<String> c = new ArrayList<>();
for(String s : c) { System.out.println(s);}

增强for可以用来遍历集合或者数组。
增强for遍历集合，本质就是迭代器遍历集合的简化写法。

方式3Lambda表达式

得益于JDK 8开始的新技术Lambda表达式，提供了一种更简单、更直接的方式来遍历集合。
需要使用Collection的如下方法来完成

方法名称	说明
default void forEach(Consumer<? super T> action)	结合lambda遍历集合

Collection<String> lists = new ArrayList<>();
lists.forEach(new Consumer<String>() {@Overridepublic void accept(String s) {System.out.println(s);}
});lists.forEach(s -> { System.out.println(s); });
//  lists.forEach(s -> System.out.println(s));
names.forEach(System.out::println);

三种遍历方式的区别

认识并发修改异常问题
遍历集合的同时又存在增删集合元素的行为时可能出现业务异常，这种现象被称之为并发修改异常问题。

需求：

• 现在假如购物车中存储了如下这些商品：Java入门,宁夏枸杞，黑枸杞，人字拖，特级枸杞，枸杞子。现在用户不想买枸杞了，选择了批量删除。

分析：

1. 后台使用ArrayList集合表示购物车，存储这些商品名。
2. 遍历集合中的每个数据，只要这个数据包含了“枸杞”则删除它。
3. 输出集合看是否已经成功删除了全部枸杞数据了。

代码实现以及bug分析

ArrayList<String> list = new ArrayList<>();list.add("Java入门");list.add("宁夏枸杞");list.add("黑枸杞");list.add("人字拖");list.add("特级枸杞");list.add("枸杞子");list.add("西洋参");System.out.println(list);// 需求1：删除全部枸杞for (int i = 0; i < list.size(); i++) {String name = list.get(i);if(name.contains("枸杞")){list.remove(name);}}System.out.println(list);   //出现并发修改异常问题。// [Java入门, 宁夏枸杞, 黑枸杞, 人字拖, 特级枸杞, 枸杞子, 西洋参]// [Java入门, 黑枸杞, 人字拖, 枸杞子, 西洋参]//           i// [Java入门, 黑枸杞, 人字拖, 枸杞子, 西洋参]// 每次删完后紧接着的第二次元素会占用被删元素的的位置。会被跳过

使用迭代器

// 需求1：删除全部枸杞
// 方案一：迭代器遍历并删除默认也存在并发修改异常问题。
// 可以解决，解决方案3：使用迭代器自己的方法来删除
Iterator<String> it = list4.iterator();
while(it.hasNext()){String name = it.next();if(name.contains("枸杞")){it.remove();   // 可以解决 解决方案3：使用迭代器自己的方法来删除当前数据}
}
System.out.println(list4);

使用增强for

ArrayList<String> list2 = new ArrayList<>();
list2.add("Java入门");
list2.add("宁夏枸杞");
list2.add("黑枸杞");
list2.add("人字拖");
list2.add("特级枸杞");
list2.add("枸杞子");
list2.add("西洋参");
System.out.println(list2);// 需求1：删除全部枸杞
for (int i = 0; i < list2.size(); i++) {String name = list2.get(i);if(name.contains("枸杞")){list2.remove(name);i--; // 解决方案1：删除数据后做一步i--操作 （前提是支持索引）}
}
// [Java入门, 宁夏枸杞, 黑枸杞, 人字拖, 特级枸杞, 枸杞子, 西洋参]
// [Java入门, 人字拖,  西洋参]
//                  i
System.out.println(list2);System.out.println("=====================================================");ArrayList<String> list3 = new ArrayList<>();
list3.add("Java入门");
list3.add("宁夏枸杞");
list3.add("黑枸杞");
list3.add("人字拖");
list3.add("特级枸杞");
list3.add("枸杞子");
list3.add("西洋参");
System.out.println(list3);// 需求1：删除全部枸杞
// 解决方案2：倒着遍历并删除（前提是支持索引）
for (int i = list3.size() - 1; i >= 0; i--) {String name = list3.get(i);if(name.contains("枸杞")){list3.remove(name);}
}
// [Java入门, 人字拖, 西洋参]
//     i
System.out.println(list3);

使用Lambda

// 直接报错无法解决

1. 如果集合支持索引，可以使用for循环遍历，每删除数据后做i–；或者可以倒着遍历
2. 可以使用迭代器遍历，并用迭代器提供的删除方法删除数据。

注意：增强for循环/Lambda遍历均不能解决并发修改异常问题，因此增它们只适合做数据的遍历，不适合同时做增删操作。

List集合

1. Collection(接口)：单列集合：每个元素（数据）只包含一个值。
   • List(接口)：添加的元素是有序、可重复、有索引。
     1. ArrayList：有序、可重复、有索引。基于数组存储数据的，索引查询快，增删慢。
     2. LinkedList：有序、可重复、有索引。基于双链表存储数据的，索引查询慢，增删快，对首尾增删改查极快。
   • Set(接口)：无序、不重复、无索引
     1. HashSet：无序、不重复、无索引
        • LinkedHashSet：有序、不重复、无索引
     2. TreeSet：按照大小默认升序排序、不重复、无索引
2. Map(接口)：双列集合：每个元素包含两个值（键值对）。
   • HashMap：
     • LinkedHashMap
   • TreeMap

ArrayList和LinkedList底层实现不同，适合的场景不同

List集合因为支持索引，所以多了很多与索引相关的方法，当然，Collection的功能List也都继承了。

方法名称	说明
void add(int index,E element)	在此集合中的指定位置插入指定的元素
E remove(int index)	删除指定索引处的元素，返回被删除的元素
E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
E get(int index)	返回指定索引处的元素

遍历方式
for循环（因为List集合有索引）
迭代器
增强for循环
Lambda表达式

public class ListDemo1 {public static void main(String[] args) {// 目标：掌握List系列集合独有的功能。ArrayList<String> names = new ArrayList<>(); // 一行经典代码// 添加数据names.add("张三");names.add("李四");names.add("王五");names.add("赵六");System.out.println(names); // [张三, 李四, 王五, 赵六]// 给第三个位置插入一个数据：赵敏names.add(2, "赵敏");System.out.println(names);// 删除李四System.out.println(names.remove(1)); // 根据下标删除，返回删除的数据System.out.println(names);// 把王五修改成：金毛System.out.println(names.set(2, "金毛")); // 根据下标修改，返回修改前的数据System.out.println(names);// 获取张三System.out.println(names.get(0));System.out.println("-----------四种遍历演示---------------");// 1、for循环for (int i = 0; i < names.size(); i++) {System.out.println(names.get(i));}// 2、迭代器Iterator<String> it = names.iterator();while (it.hasNext()) {String name = it.next();System.out.println(name);}// 3、增强forfor (String name : names) {System.out.println(name);}// 4、lambda表达式names.forEach(name ->  System.out.println(name) );System.out.println(15 >> 1);}
}

LinkedList新增了：很多首尾操作的特有方法。

方法名称	说明
public void addFirst(E e)	在该列表开头插入指定的元素
public void addLast(E e)	将指定的元素追加到此列表的末尾
public E getFirst()	返回此列表中的第一个元素
public E getLast()	返回此列表中的最后一个元素
public E removeFirst()	从此列表中删除并返回第一个元素
public E removeLast()	从此列表中删除并返回最后一个元素

List的特点、特有功能

ArrayList底层原理

LinkedList底层原理

LinkedList的应用场

可以用来设计队列: 先进先出，后进后出。

设计栈：后进先出，先进后出。

import java.util.LinkedList;
public class ListDemo2 {public static void main(String[] args) {// 目标：用LinkedList做一个队列对象。LinkedList<String> queue = new LinkedList<>();// 入队queue.addLast("赵敏");queue.addLast("西门吹雪");queue.addLast("陆小凤");queue.addLast("石观音");System.out.println(queue); // [赵敏, 西门吹雪, 陆小凤, 石观音]// 出队System.out.println(queue.removeFirst());// 赵敏System.out.println(queue.removeFirst());// 西门吹雪System.out.println(queue); // [陆小凤, 石观音]System.out.println("-------------------------------------------------");// 做一个栈LinkedList<String> stack = new LinkedList<>();// 压栈stack.push("第1颗子弹");stack.push("第2颗子弹");stack.push("第3颗子弹");stack.push("第4颗子弹");System.out.println(stack);  // [第4颗子弹, 第3颗子弹, 第2颗子弹, 第1颗子弹]// 出栈System.out.println(stack.pop());// 第4颗子弹System.out.println(stack.pop());// 第3颗子弹System.out.println(stack);// [第2颗子弹, 第1颗子弹]}
}

list:电影信息管理模块案例

需求

• 开发一个电影信息管理模块，用户可以上架电影，查询电影
• 下架某部电影，以及下架某个主演参演的全部电影。

分析

1. 每部电影都是一个电影对象，设计电影类。
2. 需要定义一个电影操作类，其对象专门用于处理电影数据的业务。
3. 操作类中需要定义一个集合存放全部的电影对象

public class Test {public static void main(String[] args) {// 目标：完成电影案例// 1、创建电影对象：定义电影类。// 2、创建一个电影操作对象：专门负责对象电影数据进行业务处理（上架，下架，查询，封杀某个电影明星的电影）MovieService movieService = new MovieService();movieService.start();}
}
// javabean类
@Data
@NoArgsConstructor
@AllArgsConstructor
public class Movie {private String name;private double score;private String actor;private double price;
}
// 业务层
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class MovieService {// 4、准备一个集合容器：存储全部上架的电影数据。private static List<Movie> movies = new ArrayList<>();private static Scanner sc = new Scanner(System.in);public void start() {while (true) {// 3、准备操作界面:GUI界面/cmd命令做。System.out.println("====电影信息操作系统===");System.out.println("1、上架");System.out.println("2、下架某个电影");System.out.println("3、查询某个电影");System.out.println("4、封杀某个明星");System.out.println("5、退出");System.out.println("6、展示全部电影");System.out.println("7、修改某个电影");System.out.println("请您输入操作命令：");String command = sc.next();switch (command) {case "1":// 上架(独立功能独立成方法)addMovie();break;case "2":// 下架某个电影(自己做一下)break;case "3":// 查询某个电影queryMovie();break;case "4":// 封杀某个明星deleteStar();break;case "5":System.out.println("退出成功！");return;case "6":// 展示全部电影queryAllMovies();break;case "7":// 修改某个电影(自己做一下)break;default:System.out.println("命令有毛病！");}}}private void queryAllMovies() {System.out.println("===========展示全部电影============");for (Movie m : movies) {System.out.println(m.getName() + "  " + m.getActor() + "  " + m.getPrice() + "  " + m.getScore());}}/*** 封杀某个明星*/private void deleteStar() {System.out.println("===========封杀明星============");System.out.println("请您输入要封杀的明星：");String star = sc.next();for (int i = 0; i < movies.size(); i++) {Movie movie = movies.get(i);if (movie.getActor().contains(star)) {movies.remove(movie);i--;// 退一步}}System.out.println("封杀成功！");// 展示全部电影。queryAllMovies();}/*** 根据电影名称查询某部电影对象展示出来*/private void queryMovie() {System.out.println("===========查询电影============");System.out.println("请您输入电影名称：");String name = sc.next();// 根据电影名称查询电影对象返回，展示这个对象数据。Movie movie = queryMovieByName(name);if (movie != null) {System.out.println(movie.getName() + "  " + movie.getActor() + "  " + movie.getPrice() + "  " + movie.getScore());} else {System.out.println("没有找到这个电影！");}}// 根据电影名称查询电影对象返回// movies = [m1, m2, m3 , ...]//                              mpublic Movie queryMovieByName(String name) {for (Movie m : movies) {if (m.getName().equals(name)) {return m; // 找到这个电影对象}}return null; // 没有找到这个电影对象}/*** 上架电影*/private void addMovie() {System.out.println("===========上架电影============");// 分析：每点击一次上架电影，其实就是新增一部电影。每部电影是一个电影对象封装数据的// 1、创建电影对象，封装这部电影信息。Movie movie = new Movie();// 2、给电影对象注入数据。System.out.println("请您输入电影名称：");movie.setName(sc.next());System.out.println("请您输入主演：");movie.setActor(sc.next());System.out.println("请您输入电影价格：");movie.setPrice(sc.nextDouble());System.out.println("请您输入电影评分：");movie.setScore(sc.nextDouble());// 3、把电影对象添加到集合中。movies.add(movie);System.out.println("上架成功！");}
}

Set集合

1. Collection(接口)：单列集合：每个元素（数据）只包含一个值。
   • List(接口)：添加的元素是有序、可重复、有索引。
     1. ArrayList：有序、可重复、有索引。基于数组存储数据的，索引查询快，增删慢。第一次扩容长度是10。
     2. LinkedList：有序、可重复、有索引。基于双链表存储数据的，索引查询慢，增删快，对首尾增删改查极快。
   • Set(接口)：不重复、无索引，常用方法是Collection提供的，几乎没有新增的常用功能。
     1. HashSet：无序、不重复、无索引。第一次扩容长度是16。哈希表(哈希表=数组+链表+红黑树)。
        • LinkedHashSet：有序、不重复、无索引。哈希表(数组+链表+红黑树)。但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置。即双链表+哈希表(哈希表=数组+链表+红黑树)。
     2. TreeSet：按照大小默认升序排序、不重复、无索引。红黑树+哈希表(哈希表=数组+链表+红黑树)。对于自定义类型如Student对象，TreeSet默认是无法直接排序的会报错。想要排序需要重写Comparator对象去指定比较规则。
2. Map(接口)：双列集合：每个元素包含两个值（键值对）。
   • HashMap：
     • LinkedHashMap
   • TreeMap

注意：HashSet
Set要用到的常用方法，基本上就是Collection提供的。自己几乎没有额外新增一些常用功能！

set集合使用

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;public class SetDemo1 {public static void main(String[] args) {// 目标：认识Set家族集合的特点。// 1、创建一个Set集合，特点：无序，不重复，无索引。
//        Set<String> set = new HashSet<>(); // 一行经典代码 HashSet 无序，不重复，无索引。//  使用上面进行添加，打印结果如下[java, 新媒体, 鸿蒙, 电商设计, 大数据]Set<String> set = new LinkedHashSet<>(); // LinkedHashSet 有序，不重复，无索引。set.add("鸿蒙");set.add("鸿蒙");set.add("java");set.add("java");set.add("电商设计");set.add("电商设计");set.add("新媒体");set.add("大数据");System.out.println(set);// [鸿蒙, java, 电商设计, 新媒体, 大数据]// 2、创建一个TreeSet集合：排序（默认一定要大小升序排序），不重复，无索引。Set<Double> set1 = new TreeSet<>();set1.add(3.14);set1.add(5.6);set1.add(1.0);set1.add(1.0);set1.add(2.0);System.out.println(set1);// [1.0, 2.0, 3.14, 5.6]}
}

哈希值

这是学习底层原理的前置知识。
哈希值：就是一个int类型的随机值，Java中每个对象都有一个哈希值。
Java中的所有对象，都可以调用Obejct类提供的hashCode方法，返回该对象自己的哈希值。

// public int hashCode(); //返回对象的哈希码值
String s1 = "acd";
String s2 = "abc";
System.out.println(s1.hashCode());// 96386
System.out.println(s1.hashCode());// 96386
System.out.println(s2.hashCode());// 96354
System.out.println(s2.hashCode());// 96354

对象哈希值的特点:

1. 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
2. 不同的对象，它们的哈希值大概率不相等，但也有可能会相等(哈希碰撞)。

为什么大概率不相等？
因为int取值范围 (-21亿多 ~ 21亿多)一共45亿个对象。当我们有48亿个对象，就会有三亿个对象重复。

红黑树

前置知识。
我们知道普通二叉树。

但是存在问题我们的数字都出现在一侧

于是有了平衡二叉树
在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。

但是还不够好。于是有了红黑树。
红黑树，就是可以自平衡的二叉树：让红黑数量相等。

HashSet底层原理

基于哈希表存储数据的。
哈希表
JDK8之前，哈希表 = 数组+链表
JDK8开始，哈希表 = 数组+链表+红黑树
哈希表是一种增删改查数据，性能都较好的数据结构

Set<String> set = new HashSet<>();

1. 创建一个默认长度16的数组，默认加载因子为0.75，数组名table
   
2. 使用元素的哈希值对数组的长度做运算计算出应存入的位置,可以想象这个运算是取余。
3. 判断当前位置是否为null，如果是null直接存入
   
4. 如果不为null，表示有元素，则调用equals方法比较相等，则不存入链表；不相等，则存入链表。
   • JDK 8之前，新元素存入数组，占老元素位置，老元素挂下面
   • JDK 8开始之后，新元素直接使用链表挂在老元素下面。
5. 但是如果我们链表过长不就相当于LinkedList了吗。所以当这16个元素被占用了16(当前长度) * 上面第一步的加载因子(0.75) = 12个元素后，会自动扩容。
6. 但是会有一种可能，我的链表可以一直无限长。但是我的HashSet长度的元素一直没有达到扩容标准。于是加了一个另一个准则：JDK8开始，当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树
   

HashSet集合元素的对象去重操作

在类中重写hashCode()和equals()

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import java.util.Objects;@Data
@NoArgsConstructor
@AllArgsConstructor
public class Student {private String name;private int age;private String address;private String phone;// 只要两个对象的内容一样结果一定是true.// s3.equals(s1)@Overridepublic boolean equals(Object o) {// 1、如果是自己和自己比直接返回trueif (this == o) return true;// 2、如果o为空或者o不是Student类型，直接返回falseif (o == null || this.getClass() != o.getClass()) return false;// 3、比较两个对象的内容是否一样Student student = (Student) o;return this.age == student.age && Objects.equals(name, student.name) && Objects.equals(address, student.address) && Objects.equals(phone, student.phone);}@Overridepublic int hashCode() {// 不同学生对象，如果内容一样返回的哈希值一定是一样的，return Objects.hash(name, age, address, phone);}
}
// main
import java.util.HashSet;
import java.util.Set;
public class SetDemo2 {public static void main(String[] args) {// 目标：掌握HashSet集合去重操作。Student s1 = new Student("张三", 18, "北京", "123456");Student s2 = new Student("李四", 19, "上海", "989876");Student s3 = new Student("张三", 18, "北京", "123456");Student s4 = new Student("李四", 19, "上海", "989876");Set<Student> set = new HashSet<>(); // 不重复的！set.add(s1);set.add(s2);set.add(s3);set.add(s4);System.out.println(set);// 如果在Student类中不重写hashCode()和equals()方法。这里hashCode()相当于不同地址。虽然内容一样。// [Student(name=张三, age=18, address=北京, phone=123456),// Student(name=李四, age=19, address=上海, phone=989876)]}
}

LinkedHashSet集合的底层原理

依然是基于哈希表(数组、链表、红黑树)实现的。
但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置。

TreeSet集合底层原理

底层是基于红黑树实现的排序。

TreeSet集合排序规则

• 对于数值类型：Integer , Double，默认按照数值本身的大小进行升序排序。
• 对于字符串类型：默认按照首字符的编号升序排序。
• 对于自定义类型如Student对象，TreeSet默认是无法直接排序的。

TreeSet集合自定义排序规则

TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方式来指定比较规则。

1. 让自定义的类（如学生类）实现Comparable接口，重写里面的compareTo方法来指定比较规则。

   package com.itheima.demo1hashset;import lombok.AllArgsConstructor;
   import lombok.Data;
   import lombok.NoArgsConstructor;// 1、对象类实现一个Comparable比较接口，重写compareTo方法，//    指定大小比较规则
   @Data
   @NoArgsConstructor
   @AllArgsConstructor
   public class Teacher implements Comparable<Teacher>{private String name;private int age;private double salary;// t2.compareTo(t1)// t2 == this 比较者// t1 == o  被比较者// 规定1：如果你认为左边大于右边 请返回正整数// 规定2：如果你认为左边小于右边 请返回负整数// 规定3：如果你认为左边等于右边 请返回0// 默认就会升序。@Overridepublic int compareTo(Teacher o) {// 按照年龄升序
   //        if(this.getAge() > o.getAge()) return 1;
   //        if(this.getAge() < o.getAge()) return -1;
   //        return 0;return this.getAge() - o.getAge(); // 升序
   //        return o.getAge() - this.getAge(); // 降序}
   }
   

2. 通过调用TreeSet集合有参数构造器，可以设置Comparator对象（比较器对象，用于指定比较规则。

   public TreeSet(Comparator<? super E> comparator)
   

   设置Comparator

   package com.itheima.demo1hashset;import java.util.Comparator;
   import java.util.Set;
   import java.util.TreeSet;public class SetDemo3 {public static void main(String[] args) {// 2、public TreeSet（Comparator c）集合自带比较器Comparator对象，指定比较规则Set<Teacher> teachers = new TreeSet<>(new Comparator<Teacher>() {@Overridepublic int compare(Teacher o1, Teacher o2) {// return o2.getAge() - o1.getAge(); //降序//  if(o1.getSalary() > o2.getSalary()){ return 1; }// else if(o1.getSalary() < o2.getSalary()){//      return -1; }// return 0;// return Double.compare(o1.getSalary(), o2.getSalary()); // 薪水升序return Double.compare(o2.getSalary(), o1.getSalary()); // 薪水升序}}); // 排序，不重复，无索引// 简化形式//Set<Teacher> teachers = new TreeSet<>((o1, o2) -> Double.compare(o1.getSalary(), o2.getSalary())); // 排序，不重复，无索引teachers.add(new Teacher("老陈", 20, 6232.4));teachers.add(new Teacher("dlei", 18, 3999.5));teachers.add(new Teacher("老王", 22, 9999.9));teachers.add(new Teacher("老李", 20, 1999.9));System.out.println(teachers);// 结论：TreeSet集合默认不能 给自定义对象排序啊，因为不知道大小规则。}
   }

两种方式中，关于返回值的规则：
如果认为第一个元素 > 第二个元素 返回正整数即可。
如果认为第一个元素 < 第二个元素返回负整数即可。
如果认为第一个元素 = 第二个元素返回0即可，此时Treeset集合只会保留一个元素，认为两者重复。
注意：如果类本身有实现Comparable接口，TreeSet集合同时也自带比较器，默认使用集合自带的比较器排序。

Collection小节

1. 如果希望记住元素的添加顺序，需要存储重复的元素，又要频繁的根据索引查询数据？
   用ArrayList集合（有序、可重复、有索引），底层基于数组的。（常用）
2. 如果希望记住元素的添加顺序，且增删首尾数据的情况较多？
   用LinkedList集合（有序、可重复、有索引），底层基于双链表实现的。
3. 如果不在意元素顺序，也没有重复元素需要存储，只希望增删改查都快？
   用HashSet集合（无序，不重复，无索引），底层基于哈希表实现的。 （常用）
4. 如果希望记住元素的添加顺序，也没有重复元素需要存储，且希望增删改查都快？
   用LinkedHashSet集合（有序，不重复，无索引）， 底层基于哈希表和双链表。
5. 如果要对元素进行排序，也没有重复元素需要存储？且希望增删改查都快？
   用TreeSet集合，基于红黑树实现。

Map集合

1. Collection(接口)：单列集合：每个元素（数据）只包含一个值。
   • List(接口)：添加的元素是有序、可重复、有索引。
     1. ArrayList：有序、可重复、有索引。基于数组存储数据的，索引查询快，增删慢。第一次扩容长度是10。
     2. LinkedList：有序、可重复、有索引。基于双链表存储数据的，索引查询慢，增删快，对首尾增删改查极快。
   • Set(接口)：不重复、无索引，常用方法是Collection提供的，几乎没有新增的常用功能。
     1. HashSet：无序、不重复、无索引。第一次扩容长度是16。哈希表(哈希表=数组+链表+红黑树)。
        • LinkedHashSet：有序、不重复、无索引。哈希表(数组+链表+红黑树)。但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置。即双链表+哈希表(哈希表=数组+链表+红黑树)。
     2. TreeSet：按照大小默认升序排序、不重复、无索引。红黑树+哈希表(哈希表=数组+链表+红黑树)。对于自定义类型如Student对象，TreeSet默认是无法直接排序的会报错。想要排序需要重写Comparator对象去指定比较规则，或者实现Comparable接口，重写里面的compareTo方法来指定比较规则。
2. Map(接口)：双列集合：每个元素包含两个值(键,值),键不重复、无索引
   • HashMap：无序、键不重复、无索引。哈希表(哈希表=数组+链表+红黑树)
     • LinkedHashMap：有序、键不重复、无索引。双链表+哈希表(哈希表=数组+链表+红黑树)
   • TreeMap：按照大小默认升序排序、键不重复、无索引。红黑树+哈希表(哈希表=数组+链表+红黑树)，想要排序需要重写Comparator对象去指定比较规则。

Map集合也被叫做“键值对集合”，格式：{key1=value1 , key2=value2 , key3=value3 , …}
Map集合的所有键是不允许重复的，但值可以重复，键和值是一一对应的，每一个键只能找到自己对应的值

Map集合在什么业务场景下使用。
需要存储一一对应的数据时，就可以考虑使用Map集合来做。

{商品1=2 , 商品2=3 ， 商品3 = 2  , 商品4= 3}

注意：Map系列集合的特点都是由键决定的，值只是一个附属品，值是不做要求的
HashMap（由键决定特点）: 无序、不重复、无索引； （用的最多）
LinkedHashMap （由键决定特点）:由键决定的特点：有序、不重复、无索引。
TreeMap （由键决定特点）:按照大小默认升序排序、不重复、无索引。

Map集合的常用方法

为什么要先学习Map的常用方法 ?
Map是双列集合的祖宗，它的功能是全部双列集合都可以继承过来使用的。

方法名称	说明
public V put(K key,V value)	添加元素
public int size()	获取集合的大小
public void clear()	清空集合
public boolean isEmpty()	判断集合是否为空，为空返回true , 反之
public V get(Object key)	根据键获取对应值
public V remove(Object key)	根据键删除整个元素
public boolean containsKey(Object key)	判断是否包含某个键
public boolean containsValue(Object value)	判断是否包含某个值
public Set<K> keySet()	获取全部键的集合
public Collection<V> values()	获取Map集合的全部值

public class MapDemo2 {public static void main(String[] args) {// 目标：掌握Map的常用方法。Map<String,Integer> map = new HashMap<>();map.put("嫦娥", 20);map.put("女儿国王", 31);map.put("嫦娥", 28);map.put("铁扇公主", 38);map.put("紫霞", 31);map.put(null, null);System.out.println(map); // {null=null, 嫦娥=28, 铁扇公主=38, 紫霞=31, 女儿国王=31}// 写代码演示常用方法System.out.println(map.get("嫦娥")); // 根据键取值  28System.out.println(map.get("嫦娥2")); // 根据键取值 nullSystem.out.println(map.containsKey("嫦娥")); // 判断是否包含某个键 trueSystem.out.println(map.containsKey("嫦娥2")); // falseSystem.out.println(map.containsValue(28)); // 判断是否包含某个值 trueSystem.out.println(map.containsValue(28.0)); // falseSystem.out.println(map.remove("嫦娥")); // 根据键删除键值对,返回值System.out.println(map);// {null=null, 铁扇公主=38, 紫霞=31, 女儿国王=31}// map.clear(); // 清空map// System.out.println(map);System.out.println(map.isEmpty()); // 判断是否为空 falseSystem.out.println(map.size()); // 获取键值对的个数 4// 获取所有的键放到一个Set集合返回给我们Set<String> keys = map.keySet();for (String key : keys) {System.out.print(key+" ");}// null 铁扇公主  紫霞 女儿国王// 获取所有的值放到一个Collection集合返回给我们Collection<Integer> values = map.values();for (Integer value : values) {System.out.print(value+" ");}// null 38 31 31}
}

三种遍历方式

1. 键找值：先获取Map集合全部的键，再通过遍历键来找值
2. 键值对：把“键值对“看成一个整体进行遍历（难度较大）
3. Lambda：JDK 1.8开始之后的新技术（非常的简单）

键找值

方法名称	说明
public Set<K> keySet()	获取所有键的集合
public V get(Object key)	根据键获取其对应的值

import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class MapTraverseDemo3 {public static void main(String[] args) {Map<String,Integer> map = new HashMap<>();map.put("嫦娥", 20);map.put("女儿国王", 31);map.put("嫦娥", 28);map.put("铁扇公主", 38);map.put("紫霞", 31);System.out.println(map); // {嫦娥=28, 铁扇公主=38, 紫霞=31, 女儿国王=31}// 1、提起Map集合的全部键到一个Set集合中去Set<String> keys = map.keySet();// 2、遍历Set集合，得到每一个键for (String key : keys) {// 3、根据键去找值Integer value = map.get(key);System.out.println(key + "=" + value);}}
}

键值对

Map提供的方法	说明
Set<Map.Entry<K, V>> entrySet()	获取所有“键值对”的集合

Map.Entry提供的方法	说明
K getKey()	获取键
V getValue()	获取值

import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class MapTraverseDemo4 {public static void main(String[] args) {Map<String,Integer> map = new HashMap<>();map.put("嫦娥", 20);map.put("女儿国王", 31);map.put("嫦娥", 28);map.put("铁扇公主", 38);map.put("紫霞", 31);System.out.println(map); // {嫦娥=28, 铁扇公主=38, 紫霞=31, 女儿国王=31}// 1、把Map集合转换成Set集合，里面的元素类型都是键值对类型（Map.Entry<String, Integer>）/***  map = {嫦娥=28, 铁扇公主=38, 紫霞=31, 女儿国王=31}*   ↓*   map.entrySet()*   ↓*  Set<Map.Entry<String, Integer>> entries = [(嫦娥=28), (铁扇公主=38), (紫霞=31), (女儿国王=31)]*                                                                                   entry*/Set<Map.Entry<String, Integer>> entries = map.entrySet();// 2、遍历Set集合，得到每一个键值对类型元素for (Map.Entry<String, Integer> entry : entries) {String key = entry.getKey();Integer value = entry.getValue();System.out.println(key + "=" + value);}}
}

Lambda

方法名称	说明
default void forEach(BiConsumer<? super K, ? super V> action)	结合lambda遍历Map集合

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.function.BiConsumer;public class MapTraverseDemo5 {public static void main(String[] args) {Map<String,Integer> map = new HashMap<>();map.put("嫦娥", 20);map.put("女儿国王", 31);map.put("嫦娥", 28);map.put("铁扇公主", 38);map.put("紫霞", 31);System.out.println(map); // {嫦娥=28, 铁扇公主=38, 紫霞=31, 女儿国王=31}// 1、直接调用Map集合的forEach方法完成遍历
//        map.forEach(new BiConsumer<String, Integer>() {
//            @Override
//            public void accept(String key, Integer value) {
//                System.out.println(key + "=" + value);
//            }
//        });map.forEach((k,v) -> System.out.println(k + "=" + v));}
}

案例练习 统计投票信息

需求：

某个班级80名学生，现在需要组织秋游活动，班长提供了四个景点依次是（A、B、C、D）,每个学生只能选择一个景点，请统计出最终哪个景点想去的人数最多。

分析

• 将80个学生选择的数据拿到程序中去，[A, A, B , A, B, C, D, …]
• 准备一个Map集合用于存储统计的结果，Map<String，Integer>，键是景点，值代表投票数量。
• 遍历80个学生选择的景点，每遍历一个景点，就看Map集合中是否存在该景点，不存在存入“景点=1“，存在则其对应值+1

需要存储一一对应的数据时，就可以考虑使用Map集合来做

import java.util.*;public class MapTest6 {public static void main(String[] args) {// 目标：完成Map集合相关的案例：投票统计程序。calc();}public static void calc(){// 1、把80个学生选择的景点数据拿到程序中来，才可以统计。List<String> locations = new ArrayList<>();String[] names = {"玉龙雪山", "长城", "少林寺", "丽江"};Random r = new Random();for (int i = 1; i <= 80; i++) {int index = r.nextInt(names.length); // 0  1  2 3locations.add(names[index]);}System.out.println(locations);// locations = [丽江, 玉龙雪山, 玉龙雪山, 丽江, 少林寺, 玉龙雪山, 丽江, 丽江, 长城, 长城, 长城, 少林寺, ....// 2、统计每个景点被选择的次数// 最终统计的结果是一个键值对的形式，所以可以考虑定义一个Map集合来统计结果。Map<String, Integer> map = new HashMap<>(); // map = { }// 3、遍历80个学生选择的景点，来统计选择的次数。for (String location : locations) {// 4、判断当前遍历的景点是否在Map集合中存在，如果不存在说明是第一次出现，如果存在说明之前统计过。
//            if (map.containsKey(location)) {
//                // 这个景点之前出现过，其值+1
//                map.put(location, map.get(location) + 1);
//            } else {
//                // 这个景点是第一次统计，存入“景点=1”
//                map.put(location, 1);
//            }// 简化写法！map.put(location, map.containsKey(location) ? map.get(location) + 1 : 1);}// 5、把统计结果打印出来。map.forEach((k, v) -> {System.out.println(k + "被选择了" + v + "次");});}
}

HashMap集合的底层原理

HashMap跟HashSet的底层原理是一模一样的，都是基于哈希表实现的。

实际上：原来学的Set系列集合的底层就是基于Map实现的，只是Set集合中的元素只要键数据，不要值数据而已。
下面是 HashSet源码。我们发现set就是给Map套了一个壳子。
public HashSet() { map = new HashMap<>();}

LinkedHashMap集合的原理

底层数据结构依然是基于哈希表实现的，只是每个键值对元素又额外的多了一个双链表的机制记录元素顺序(保证有序)。
实际上：原来学习的LinkedHashSet集合的底层原理就是LinkedHashMap。

TreeMap集合的原理

特点：不重复、无索引、可排序(按照键的大小默认升序排序，只能对键排序)
原理：TreeMap跟TreeSet集合的底层原理是一样的，都是基于红黑树实现的排序。
TreeMap集合同样也支持两种方式来指定排序规则
让类实现Comparable接口，重写比较规则。
TreeMap集合有一个有参数构造器，支持创建Comparator比较器对象，以便用来指定比较规则。

Map<Teacher, String> map = new TreeMap<>((o1, o2) -> Double.compare(o2.getSalary(), o1.getSalary())); // 按照键排序：升序
map.put(new Teacher("老陈", 20, 6232.4), "462期");
map.put(new Teacher("dlei", 18, 3999.5), "422期");
map.put(new Teacher("老王", 22, 9999.9), "461期");
map.put(new Teacher("老李", 20, 1999.9), "423期");
System.out.println(map);