# 第 12 章_集合框架

讲师：尚硅谷 - 宋红康（江湖人称：康师傅）

官网：http://www.atguigu.com

# 本章专题与脉络

主线：

集合 vs 数组
Collection 接口
- List 子接口
  - ArrayList
  - LinkedList
  - Vector
- Set 子接口
  - HashSet
    - LinkedHashSet
  - TreeSet
Map 接口
- HashMap
  - LinkedHashMap
- Hashtable
  - Properties
- ~~SortedMap~~
  - TreeMap
Collections 工具类

# 1. 集合框架概述

# 1.1 生活中的容器

# 1.2 数组的特点与弊端

一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。
另一方面，使用数组存储对象方面具有 一些弊端 ，而 Java 集合就像一种容器，可以 动态地 把多个对象的引用放入容器中。
数组在内存存储方面的 特点 ：
- 数组初始化以后，长度就确定了。
- 数组中的添加的元素是依次紧密排列的，有序的，可重复的。
- 数组声明的类型，就决定了进行元素初始化时的类型。不是此类型的变量，就不能添加。
- 可以存储基本数据类型值，也可以存储引用数据类型的变量
数组在存储数据方面的 弊端 ：
- 数组初始化以后，长度就不可变了，不便于扩展
- 数组中提供的属性和方法少，不便于进行添加、删除、插入、获取元素个数等操作，且效率不高。
- 数组存储数据的特点单一，只能存储有序的、可重复的数据
Java 集合框架中的类可以用于存储多个 对象 ，还可用于保存具有 映射关系 的关联数组。

# 1.3 数组 vs 集合

	数组	集合
长度	长度固定	动态长度
可存储的元素类型	基本数据类型、引用数据类型	引用数据类型 / 映射
元素类型要求	元素的类型必须相同	元素的类型可以不同
是否连续存储	连续存储	非连续存储
元素特点	有序、可重复	List：有序、可重复；Set：无序、不可重复；Map：无序、不可重复；
查找速度	快（通过索引值，复杂度为 O (1)）	慢（复杂度为 O (n)）
增、删、插速度	慢	快
举例		List、Set、Map

# 1.4 Java 集合框架体系（java.util 包）

Java 集合可分为 Collection 和 Map 两大体系：

Collection 接口：用于存储一个一个的数据，也称 单列数据集合 。
- List 子接口：用来存储有序的、可重复的数据（主要用来替换数组，"动态" 数组）
  - 实现类：ArrayList、LinkedList、Vector
- Set 子接口：用来存储无序的、不可重复的数据（类似于高中讲的"集合"）
  - 实现类：HashSet、LinkedHashSet、TreeSet
Map 接口：用于存储具有映射关系 “key-value 对”的集合，其中key 是唯一的，即一对一对的数据，也称 双列数据集合 。(类似于高中的函数、映射。(x1,y1),(x2,y2) ---> y = f(x) )
- 实现类：HashMap、LinkedHashMap、TreeMap、Hashtable、Properties
图示：集合框架全图

集合框架全图.png

简图 1：Collection 接口继承树

简图 2：Map 接口继承树

# 1.5 集合的使用场景

第12章_集合的使用场景

# 2. Collection 接口及方法

JDK 不提供 Collection 接口的任何直接实现，而是提供更具体的子接口（如：Set 和 List）去实现。
Collection 接口是 List 和 Set 接口的父接口，Collection 接口里定义的方法既可用于操作 Set 集合，也可用于操作 List 集合。方法如下：

# 2.1 添加

（1）add(E obj)：添加元素对象到当前集合中
（2）addAll(Collection other)：添加 other 集合中的所有元素对象到当前集合中，即 this = this ∪ other

注意：
coll.addAll(other); 与 coll.add(other);
向 Collection 添加的元素的所在类一定要重写了 equals ()。因为后续使用 Collection 接口中的 contains ()、containsAll ()、equals ()、remove ()、removeAll ()、retainAll () 时，都需要调用元素所在类的 equals () 是否返回 true 来判断元素是否相等。

	package com.atguigu.collection;

	import org.junit.Test;

	import java.util.ArrayList;
	import java.util.Collection;

	public class TestCollectionAdd {
	@Test
	public void testAdd(){
	//ArrayList 是 Collection 的子接口 List 的实现类之一。
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	System.out.println(coll);
	}

	@Test
	public void testAddAll(){
	Collection c1 = new ArrayList();
	c1.add(1);
	c1.add(2);
	System.out.println("c1集合元素的个数：" + c1.size());//2
	System.out.println("c1 = " + c1);

	Collection c2 = new ArrayList();
	c2.add(1);
	c2.add(2);
	System.out.println("c2集合元素的个数：" + c2.size());//2
	System.out.println("c2 = " + c2);

	Collection other = new ArrayList();
	other.add(1);
	other.add(2);
	other.add(3);
	System.out.println("other集合元素的个数：" + other.size());//3
	System.out.println("other = " + other);
	System.out.println();

	c1.addAll(other);
	System.out.println("c1集合元素的个数：" + c1.size());//5
	System.out.println("c1.addAll(other) = " + c1);// ①

	c2.add(other);
	System.out.println("c2集合元素的个数：" + c2.size());//3
	System.out.println("c2.add(other) = " + c2);
	}// ②
	}

# 2.2 判断

（3）int size()：获取当前集合中实际存储的元素个数

不要和容量搞混淆了

（4）boolean isEmpty()：判断当前集合是否为空集合
（5）boolean contains(Object obj)：判断当前集合中是否存在一个与 obj 对象equals 返回 true的元素

前提是重写了 equals 方法，比较的是值，而不是地址。如果没有重写 equals 方法，那么调用的是 Object 类中的 equals 方法，相当于 ==，比较的是地址！

（6）boolean containsAll(Collection coll)：判断 coll 集合中的元素是否在当前集合中都存在。即 coll 集合是否是当前集合的 “子集”
（7）boolean equals(Object obj)：判断当前集合与 obj 是否相等

	package com.atguigu.collection;

	import org.junit.Test;

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;

	public class TestCollectionContains {
	@Test
	public void test01() {
	Collection coll = new ArrayList();
	System.out.println("coll在添加元素之前，isEmpty = " + coll.isEmpty());
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	coll.add("佛地魔");
	System.out.println("coll的元素个数" + coll.size());

	System.out.println("coll在添加元素之后，isEmpty = " + coll.isEmpty());
	}

	@Test
	public void test02() {
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	coll.add("佛地魔");
	System.out.println("coll = " + coll);
	System.out.println("coll是否包含“小李广” = " + coll.contains("小李广"));
	System.out.println("coll是否包含“宋红康” = " + coll.contains("宋红康"));

	Collection other = new ArrayList();
	other.add("小李广");
	other.add("扫地僧");
	other.add("尚硅谷");
	System.out.println("other = " + other);

	System.out.println("coll.containsAll(other) = " + coll.containsAll(other));
	}

	@Test
	public void test03(){
	Collection c1 = new ArrayList();
	c1.add(1);
	c1.add(2);
	System.out.println("c1集合元素的个数：" + c1.size());//2
	System.out.println("c1 = " + c1);

	Collection c2 = new ArrayList();
	c2.add(1);
	c2.add(2);
	System.out.println("c2集合元素的个数：" + c2.size());//2
	System.out.println("c2 = " + c2);

	Collection other = new ArrayList();
	other.add(1);
	other.add(2);
	other.add(3);
	System.out.println("other集合元素的个数：" + other.size());//3
	System.out.println("other = " + other);
	System.out.println();

	c1.addAll(other);
	System.out.println("c1集合元素的个数：" + c1.size());//5
	System.out.println("c1.addAll(other) = " + c1);
	System.out.println("c1.contains(other) = " + c1.contains(other));
	System.out.println("c1.containsAll(other) = " + c1.containsAll(other));
	System.out.println();

	c2.add(other);
	System.out.println("c2集合元素的个数：" + c2.size());
	System.out.println("c2.add(other) = " + c2);
	System.out.println("c2.contains(other) = " + c2.contains(other));
	System.out.println("c2.containsAll(other) = " + c2.containsAll(other));
	}

	}

# 2.3 删除

（8）void clear()：清空集合元素
（9） boolean remove(Object obj) ：从当前集合中删除第一个找到的与 obj 对象equals 返回 true的元素
（10）boolean removeAll(Collection coll)：从当前集合中删除所有与 coll 集合中equals 返回 true 的元素。即 this = this - this ∩ coll
（11）boolean retainAll(Collection coll)：从当前集合中删除两个集合中不同的元素，使得当前集合仅保留与 coll 集合中的元素相同的元素，即当前集合中仅保留两个集合的交集，即 this = this ∩ coll

	package com.atguigu.collection;

	import org.junit.Test;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.function.Predicate;

	public class TestCollectionRemove {
	@Test
	public void test01(){
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	coll.add("佛地魔");
	System.out.println("coll = " + coll);

	coll.remove("小李广");
	System.out.println("删除元素\"小李广\"之后coll = " + coll);

	coll.clear();
	System.out.println("coll清空之后，coll = " + coll);
	}

	@Test
	public void test02() {
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	coll.add("佛地魔");
	System.out.println("coll = " + coll);

	Collection other = new ArrayList();
	other.add("小李广");
	other.add("扫地僧");
	other.add("尚硅谷");
	System.out.println("other = " + other);

	coll.removeAll(other);
	System.out.println("coll.removeAll(other)之后，coll = " + coll);
	System.out.println("coll.removeAll(other)之后，other = " + other);
	}

	@Test
	public void test03() {
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	coll.add("佛地魔");
	System.out.println("coll = " + coll);

	Collection other = new ArrayList();
	other.add("小李广");
	other.add("扫地僧");
	other.add("尚硅谷");
	System.out.println("other = " + other);

	coll.retainAll(other);
	System.out.println("coll.retainAll(other)之后，coll = " + coll);
	System.out.println("coll.retainAll(other)之后，other = " + other);
	}

	}

# 2.4 其它

（12）Object[] toArray()：集合转换为数组

数组转换为集合：Arrays.asList()

	@Test
	public void test6() {
	Integer[] arr = new Integer[]{1, 2, 3, 4, 5}; // 自动装箱成包装类 Integer
	List list = Arrays.asList(arr); // 此时 list 中的元素是 Integer 类型
	System.out.println(list.size()); // 因此 list 的长度为 5
	System.out.println(list); // [1, 2, 3, 4, 5]

	int[] arr1 = new int[]{1, 2, 3, 4, 5}; // 基本数据类型，不会自动装箱
	List list1 = Arrays.asList(arr1); // 此时 list1 中的元素是 int [] 类型
	System.out.println(list1.size()); // 因此 list1 的长度为 1
	System.out.println(list1); // [ [I@75412c2f ]
	}

（13）hashCode()：获取集合对象的哈希值
（14）iterator()：返回迭代器对象，用于集合遍历

	public class TestCollectionContains {
	@Test
	public void test01() {
	Collection coll = new ArrayList();

	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	coll.add("佛地魔");
	// 集合转换为数组：集合的 toArray () 方法
	Object[] objects = coll.toArray();
	System.out.println("用数组返回coll中所有元素：" + Arrays.toString(objects));

	// 对应的，数组转换为集合：调用 Arrays 的 asList (Object ...objs)
	Object[] arr1 = new Object[]{123,"AA","CC"};
	Collection list = Arrays.asList(arr1);
	System.out.println(list);
	}
	}

# 3. Iterator (迭代器) 接口

# 3.1 Iterator 接口

在程序开发中，经常需要遍历集合中的所有元素。针对这种需求，JDK 专门提供了一个接口 java.util.Iterator 。 Iterator 接口也是 Java 集合中的一员，但它与 Collection 、 Map 接口有所不同。
- Collection 接口与 Map 接口主要用于 存储 元素
- Iterator ，被称为迭代器接口，本身并不提供存储对象的能力，主要用于 遍历 Collection 中的元素
Collection 接口继承了 java.lang.Iterable 接口，该接口有一个 iterator () 方法，那么所有实现了 Collection 接口的集合类都有一个 iterator () 方法，用以返回一个实现了 Iterator 接口的对象。
- public Iterator iterator() : 获取集合对应的迭代器，用来遍历集合中的元素。
- 集合对象每次调用 iterator () 方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。
Iterator 接口的常用方法如下：
- public E next()：返回迭代的下一个元素。
  - 指针下移
  - 返回指针当前指向的元素
- public boolean hasNext()：如果仍有元素可以迭代，则返回 true。
注意：在调用 it.next () 方法之前必须要调用 it.hasNext () 进行检测。若不调用，且下一条记录无效，直接调用 it.next () 会抛出 NoSuchElementException异常 。

举例：

	package com.atguigu.iterator;

	import org.junit.Test;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Iterator;

	public class TestIterator {
	@Test
	public void test01(){
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");

	Iterator iterator = coll.iterator();
	System.out.println(iterator.next());
	System.out.println(iterator.next());
	System.out.println(iterator.next());
	System.out.println(iterator.next()); // 报 NoSuchElementException 异常
	}

	@Test
	public void test02(){
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");

	Iterator iterator = coll.iterator();// 获取迭代器对象
	while(iterator.hasNext()) {// 判断是否还有元素可迭代
	System.out.println(iterator.next());// 取出下一个元素
	}
	}
	}

# 3.2 错误的遍历

	/**
	* 常见误区一：循环判断条件中，不要写 (iterator.next ()) != null，否则会报错 NoSuchElementException
	*/
	@Test
	public void test1() {
	Collection coll = new ArrayList();
	coll.add("AA");
	coll.add(123);
	coll.add(new Object());
	coll.add(new String("BB"));

	Iterator iterator = coll.iterator();
	while ((iterator.next()) != null) { // 每次判断都会调用 next () 方法，指针会下移
	System.out.println(iterator.next()); // 如果没有下一个元素，会报错 NoSuchElementException
	}
	}

	/**
	* 常见误区二：循环判断条件中，不要写 coll.iterator ().hasNext ()，
	* 因为每次调用 iterator () 方法都会生成一个新的 Iterator 实例，
	* 指针都会指向第一个元素之前，这样就会导致判断条件永远为 true，陷入死循环
	*/
	@Test
	public void test2() {
	Collection coll = new ArrayList();
	coll.add("AA");
	coll.add(123);
	coll.add(new Object());
	coll.add(new String("BB"));

	while (coll.iterator().hasNext()) {
	System.out.println(coll.iterator().next());
	}
	}

# 3.3 迭代器的执行原理

Iterator 迭代器对象在遍历集合时，内部采用指针的方式来跟踪集合中的元素，接下来通过一个图例来演示 Iterator 对象迭代元素的过程：

# 3.4 删除元素

使用 Iterator 迭代器删除元素：java.util.Iterator 迭代器中有一个方法：void remove() ;

	Iterator iter = coll.iterator();// 回到起点
	while(iter.hasNext()){
	Object obj = iter.next();
	if(obj.equals("Tom")){
	iter.remove();
	}
	}

注意：

Iterator 可以删除集合的元素，但是遍历过程中通过迭代器对象的 remove 方法，不是集合对象的 remove 方法。
如果还未调用 next () 或在上一次调用 next () 方法之后已经调用了 remove () 方法，再调用 remove () 都会报 IllegalStateException。
Collection 已经有 remove (xx) 方法了，为什么 Iterator 迭代器还要提供删除方法呢？因为迭代器的 remove () 可以按指定的条件进行删除。

例如：要删除以下集合元素中的偶数

	package com.atguigu.iterator;

	import org.junit.Test;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Iterator;

	public class TestIteratorRemove {
	@Test
	public void test01(){
	Collection coll = new ArrayList();
	coll.add(1);
	coll.add(2);
	coll.add(3);
	coll.add(4);
	coll.add(5);
	coll.add(6);

	Iterator iterator = coll.iterator();
	while(iterator.hasNext()){
	Integer element = (Integer) iterator.next();
	if(element % 2 == 0){
	iterator.remove();
	}
	}
	System.out.println(coll);
	}
	}

在 JDK8.0 时，Collection 接口有了 removeIf 方法，即可以根据条件删除。（第 18 章中再讲）

	package com.atguigu.collection;

	import org.junit.Test;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.function.Predicate;

	public class TestCollectionRemoveIf {
	@Test
	public void test01(){
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	coll.add("佛地魔");
	System.out.println("coll = " + coll);

	coll.removeIf(new Predicate() {
	@Override
	public boolean test(Object o) {
	String str = (String) o;
	return str.contains("地");
	}
	});
	System.out.println("删除包含\"地\"字的元素之后coll = " + coll);
	}
	}

# 3.5 foreach 循环

foreach 循环（也称增强 for 循环）是 JDK5.0 中定义的一个高级 for 循环，专门用来 遍历数组和集合 的。
foreach 循环的语法格式：

	for(元素的数据类型局部变量 : Collection集合或数组){
	// 操作局部变量的输出操作
	}
	// 这里局部变量就是一个临时变量，自己命名就可以

举例：

	package com.atguigu.iterator;

	import org.junit.Test;

	import java.util.ArrayList;
	import java.util.Collection;

	public class TestForeach {
	@Test
	public void test01(){
	Collection coll = new ArrayList();
	coll.add("小李广");
	coll.add("扫地僧");
	coll.add("石破天");
	//foreach 循环其实就是使用 Iterator 迭代器来完成元素的遍历的。
	for (Object o : coll) {
	System.out.println(o);
	}
	}
	@Test
	public void test02(){
	int[] nums = {1,2,3,4,5};
	for (int num : nums) {
	System.out.println(num);
	}
	System.out.println("-----------------");
	String[] names = {"张三","李四","王五"};
	for (String name : names) {
	System.out.println(name);
	}
	}
	}

对于集合的遍历，增强 for 的内部原理其实还是个 Iterator 迭代器。如下图。

它用于遍历 Collection 和数组。通常只进行遍历元素，不要在遍历的过程中对集合元素进行增删操作，因为增强 for 循环是将集合或数组中的元素依次赋值给 **临时变量**，可能不会导致原有数组 / 集合中的元素修改！
- 练习：判断输出结果为何？

	@Test
	public void test4() {
	// （1）普通 for 循环赋值
	String[] arr1 = new String[]{"AA", "CC", "DD"};
	for (int i = 0; i < arr1.length; i++) {
	arr1[i] = "MM"; // 修改的是数组中的元素
	}
	for (int i = 0; i < arr1.length; i++) {
	System.out.println(arr1[i]); // MM MM MM
	}

	// （2）增强 for 循环赋值
	String[] arr2 = new String[]{"AA", "CC", "DD"};
	for (String str : arr2) {
	str = "NN"; // 修改的是局部变量 str 的值，不会影响数组中的元素
	}

	for (String str : arr2) {
	System.out.println(str); // AA CC DD
	}
	}

# 4. Collection 子接口 1：List

小结

List 接口的实现类	ArrayList	LinkedList	~~Vector~~
地位	主要实现类		古老实现类
底层实现	Object 数组，但可以扩容	双向链表	Object 数组
默认的初始容量	JDK6.0 及之前是 10；JDK8.0 之后是 `0` ，之后在添加第一个元素时，再创建长度为 10 的数组	0	`10`
扩容机制	默认扩容为原来的 `1.5倍`	不需要扩容	默认扩容增加为原来的 `2倍`
特点	线程不安全、效率高	线程不安全	线程安全、效率低
使用场景	频繁追加、查找数据	频繁插入、删除数据	避免使用
说明	对于频繁访问列表中的某一个元素，只需要在列表末尾进行添加和删除元素操作的情况下	元素是通过指针相互连接的，在插入 / 删除元素时，只需要改动前后元素的指针即可

# 4.1 List 接口特点

鉴于 Java 中数组用来存储数据的局限性，我们通常使用 java.util.List 替代数组，可以理解为是“动态数组”。
List 集合类中 元素有序 、且 可重复 ，集合中的每个元素都有其对应的顺序索引。
- 举例：List 集合存储数据，就像银行门口客服，给每一个来办理业务的客户分配序号：第一个来的是 “张三”，客服给他分配的是 0；第二个来的是 “李四”，客服给他分配的 1；以此类推，最后一个序号应该是 “总人数 - 1”。

1563549818689

JDK API 中 List 接口的实现类常用的有： ArrayList 、 LinkedList 和 Vector 。

# 4.2 List 接口方法

List 除了从 Collection 集合继承的方法外，因为 List 集合是有序的，因此添加了一些根据 索引 来操作集合元素的方法。

插入元素
- void add(int index, Object ele): 在 index 位置插入 ele 元素
- boolean addAll(int index, Collection eles): 从 index 位置开始将 eles 中的所有元素添加进来
获取元素
- Object get(int index): 获取指定 index 位置的元素
- List subList(int fromIndex, int toIndex):返回从 fromIndex 到 toIndex 位置的子集合
获取元素索引
- int indexOf(Object obj): 返回 obj 在集合中首次出现的位置
- int lastIndexOf(Object obj): 返回 obj 在当前集合中末次出现的位置
删除和替换元素
- Object remove(int index): 移除指定 index 位置的元素，并返回此元素
- Object set(int index, Object ele): 设置指定 index 位置的元素为 ele

List 子接口的方法小结

增
- add (E obj)：在列表的末尾添加指定元素
- addAll(Collection other)
删
- clear()
- remove (Object obj)：移除列表中首次出现的指定元素，如果存在，返回 true，否则返回 false
- removeAll(Collection coll)
- retainAll(Collection coll)
- remove(int index)
改
- set(int index, Object ele)
查
- get(int index)
- subList(int fromIndex, int toIndex):
- indexOf(Object obj)
- lastIndexOf(Object obj)
插
- add(int index, Object ele)
- addAll(int index, Collection eles)
长度
- size ()：返回列表中实际存储的元素个数
遍历
- iterator()
- 增强 for 循环
- 普通 for 循环
其他
- isEmpty()
- contains(Object obj)
- containsAll(Collection coll)
- equals(Object obj)
- toArray()
- hashCode()

举例：

	package com.atguigu.list;

	import java.util.ArrayList;
	import java.util.List;

	public class TestListMethod {
	public static void main(String[] args) {
	// 创建 List 集合对象
	List<String> list = new ArrayList<String>();

	// 往尾部添加指定元素
	list.add("图图");
	list.add("小美");
	list.add("不高兴");

	System.out.println(list);
	//add (int index,String s) 往指定位置添加
	list.add(1,"没头脑");

	System.out.println(list);
	// String remove (int index) 删除指定位置元素返回被删除元素
	// 删除索引位置为 2 的元素
	System.out.println("删除索引位置为2的元素");
	System.out.println(list.remove(2));

	System.out.println(list);

	// String set(int index,String s)
	// 在指定位置进行元素替代（改）
	// 修改指定位置元素
	list.set(0, "三毛");
	System.out.println(list);

	// String get (int index) 获取指定位置元素
	// 跟 size () 方法一起用来遍历的
	for(int i = 0;i<list.size();i++){
	System.out.println(list.get(i));
	}
	// 还可以使用增强 for
	for (String string : list) {
	System.out.println(string);
	}
	}
	}

注意：在 JavaSE 中 List 名称的类型有两个，一个是 java.util.List 集合接口，一个是 java.awt.List 图形界面的组件，别导错包了。

# 4.3 List 接口主要实现类：ArrayList

ArrayList 是 List 接口的 主要实现类 ，一般作为 List 的默认选择。
底层使用Object 数组存储
- 在添加数据、查找数据时，效率较高
- 在插入数据、删除数据时，效率较低
线程不安全、效率高
本质上，ArrayList 是对象引用的一个” 变长” 数组
- 初始化的长度是 10
- 会自动扩容，每次增加 50%
ArrayList 类特有的方法
- ensureCapacity(int minCapacity)：确保列表的容量至少等于指定的最小值
trimToSize()：将列表的容量调整为列表的当前大小
- clone()：返回一个 ArrayList 对象的浅拷贝
Arrays.asList (…) 方法返回的 List 集合，既不是 ArrayList 实例，也不是 Vector 实例。 Arrays.asList (…) 返回值是一个固定长度的 List 集合

# 4.4 List 的实现类之二：LinkedList

对于频繁的插入或删除元素的操作，建议使用 LinkedList 类，效率较高。这是由底层采用链表（双向链表）结构存储数据决定的。
- 在添加数据、查找数据时，效率较低
- 在插入数据、删除数据时，效率较高

特有方法：
- void addFirst(Object obj)
- void addLast(Object obj)
- Object getFirst()
- Object getLast()
- Object removeFirst()
- Object removeLast()

# 4.5 List 的实现类之三：Vector

Vector 是一个 古老 的集合，JDK1.0 就有了。
大多数操作与 ArrayList 相同，区别之处在于 Vector 是线程安全的，因此效率也低。
底层使用Object 数组存储
在各种 List 中，最好把 ArrayList作为默认选择 。当插入、删除频繁时，使用 LinkedList；Vector 总是比 ArrayList 慢，所以尽量避免使用。
特有方法：
- void addElement(Object obj)
- void insertElementAt(Object obj,int index)
- void setElementAt(Object obj,int index)
- void removeElement(Object obj)
- void removeAllElements()

# 4.6 练习

面试题：

	@Test
	public void testListRemove() {
	List list = new ArrayList();
	list.add(1);
	list.add(2);
	list.add(3);
	updateList(list);
	System.out.println(list);//[1,2]
	}

	private static void updateList(List list) {
	list.remove(2); // 移除的是 index=2 的元素，而非 Integer 实例
	// list.remove(Integer.valueOf(2));
	}

练习 1：

定义学生类，属性为姓名、年龄，提供必要的 getter、setter 方法，构造器，toString ()，equals () 方法。
使用 ArrayList 集合，保存录入的多个学生对象。
循环录入的方式，1：继续录入，0：结束录入。
录入结束后，用 foreach 遍历集合。

代码实现，效果如图所示：

	package com.atguigu.test01;

	import java.util.ArrayList;
	import java.util.Scanner;

	public class StudentTest {
	public static void main(String[] args) {

	Scanner scanner = new Scanner(System.in);
	ArrayList stuList = new ArrayList();

	for (;;) {

	System.out.println("选择（录入 1 ；结束 0）");
	int x = scanner.nextInt();// 根据 x 的值，判断是否需要继续循环

	if (x == 1) {
	System.out.println("姓名");
	String name = scanner.next();
	System.out.println("年龄");
	int age = scanner.nextInt();
	Student stu = new Student(age, name);
	stuList.add(stu);

	} else if (x == 0) {
	break;

	} else {

	System.out.println("输入有误，请重新输入");
	}
	}

	for (Object stu : stuList) {
	System.out.println(stu);
	}
	}
	}

	public class Student {

	private int age;
	private String name;

	public Student() {
	}


	public Student(int age, String name) {
	super();
	this.age = age;
	this.name = name;
	}


	public int getAge() {
	return age;
	}

	public void setAge(int age) {
	this.age = age;
	}

	public String getName() {
	return name;
	}

	public void setName(String name) {
	this.name = name;

	}

	@Override
	public String toString() {
	return "Student [age=" + age + ", name=" + name + "]";
	}

	}

练习 2：

1、请定义方法 public static int listTest (Collection list,String s) 统计集合中指定元素出现的次数

2、创建集合，集合存放随机生成的 30 个小写字母

3、用 listTest 统计，a、b、c、x 元素的出现次数

4、效果如下

1559896150606

	package com.atguigu.test02;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Random;

	public class Test02 {
	public static void main(String[] args) {
	Collection list = new ArrayList();
	Random rand = new Random();
	for (int i = 0; i < 30; i++) {
	list.add((char)(rand.nextInt(26)+97)+"");
	}
	System.out.println(list);
	System.out.println("a:"+listTest(list, "a"));
	System.out.println("b:"+listTest(list, "b"));
	System.out.println("c:"+listTest(list, "c"));
	System.out.println("x:"+listTest(list, "x"));
	}

	public static int listTest(Collection list, String string) {
	int count = 0;
	for (Object object : list) {
	if(string.equals(object)){
	count++;
	}
	}
	return count;
	}
	}

练习 3：KTV 点歌系统

描述

分别使用 ArrayList 和 LinkedList 集合，编写一个 ** KTV点歌系统 ** 的程序。在程序中：

指令 1 代表添加歌曲
指令 2 代表将所选歌曲置顶
指令 3 代表将所选歌曲提前一位
指令 4 代表退出该系统

要求根据用户输入的指令和歌曲名展现歌曲列表。例如输入指令 1，输入歌曲名 "爱你一万年"，则输出 “当前歌曲列表：[爱你一万年]”。

提示

为了指引用户操作，首先要将各个指令所表示的含义打印到控制台

	System.out.println("-------------欢迎来到点歌系统------------");
	System.out.println("1.添加歌曲至列表");
	System.out.println("2.将歌曲置顶");
	System.out.println("3.将歌曲前移一位");
	System.out.println("4.退出");

程序中需要创建一个集合作为歌曲列表，并向其添加一部分歌曲
通过 ArrayList 或 LinkedList 集合定义的方法操作歌曲列表

代码

使用 ArrayList 集合模拟点歌系统的实现代码，如下所示：

	/**
	* @author 尚硅谷 - 宋红康
	* @create 20:26
	*/
	public class KTVByArrayList {
	private static ArrayList musicList = new ArrayList();// 创建歌曲列表
	private static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
	addMusicList();// 添加一部分歌曲至歌曲列表
	boolean flag = true;
	while (flag) {
	System.out.println("当前歌曲列表：" + musicList);
	System.out.println("-------------欢迎来到点歌系统------------");
	System.out.println("1.添加歌曲至列表");
	System.out.println("2.将歌曲置顶");
	System.out.println("3.将歌曲前移一位");
	System.out.println("4.退出");
	System.out.print("请输入操作序号：");
	int key = sc.nextInt();//// 接收键盘输入的功能选项序号
	// 执行序号对应的功能
	switch (key) {
	case 1:// 添加歌曲至列表
	addMusic();
	break;
	case 2:// 将歌曲置顶
	setTop();
	break;
	case 3:// 将歌曲前移一位
	setBefore();
	break;
	case 4:// 退出
	System.out.println("----------------退出---------------");
	System.out.println("您已退出系统");
	flag = false;
	break;
	default:
	System.out.println("----------------------------------");
	System.out.println("功能选择有误，请输入正确的功能序号!");
	break;
	}

	}
	}

	// 初始时添加歌曲名称
	private static void addMusicList() {
	musicList.add("本草纲目");
	musicList.add("你是我的眼");
	musicList.add("老男孩");
	musicList.add("白月光与朱砂痣");
	musicList.add("不谓侠");
	musicList.add("爱你");
	}

	// 执行添加歌曲
	private static void addMusic() {
	System.out.print("请输入要添加的歌曲名称：");
	String musicName = sc.next();// 获取键盘输入内容
	musicList.add(musicName);// 添加歌曲到列表的最后
	System.out.println("已添加歌曲：" + musicName);
	}

	// 执行将歌曲置顶
	private static void setTop() {
	System.out.print("请输入要置顶的歌曲名称：");
	String musicName = sc.next();// 获取键盘输入内容
	int musicIndex = musicList.indexOf(musicName);// 查找指定歌曲位置
	if (musicIndex < 0) {// 判断输入歌曲是否存在
	System.out.println("当前列表中没有输入的歌曲！");
	}else if(musicIndex == 0){
	System.out.println("当前歌曲默认已置顶！");
	}else {
	musicList.remove(musicName);// 移除指定的歌曲
	musicList.add(0, musicName);// 将指定的歌曲放到第一位
	System.out.println("已将歌曲《" + musicName + "》置顶");
	}
	}

	// 执行将歌曲置前一位
	private static void setBefore() {
	System.out.print("请输入要置前的歌曲名称：");
	String musicName = sc.next();// 获取键盘输入内容
	int musicIndex = musicList.indexOf(musicName);// 查找指定歌曲位置
	if (musicIndex < 0) {// 判断输入歌曲是否存在
	System.out.println("当前列表中没有输入的歌曲！");
	} else if (musicIndex == 0) {// 判断歌曲是否已在第一位
	System.out.println("当前歌曲已在最顶部！");
	} else {
	musicList.remove(musicName);// 移除指定的歌曲
	musicList.add(musicIndex - 1, musicName);// 将指定的歌曲放到前一位
	System.out.println("已将歌曲《" + musicName + "》置前一位");
	}
	}
	}

# 5. Collection 子接口 2：Set

# 5.1 Set 接口概述

Set 接口是 Collection 的子接口，Set 接口相较于 Collection 接口没有提供额外的方法
Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。
Set 集合支持的遍历方式和 Collection 集合一样：foreach和Iterator。
Set 的常用实现类有：HashSet、TreeSet、LinkedHashSet。
开发中的使用场景：
- 相较于 List、Map 来说，Set 使用较少
- 一般用于去重，过滤重复数据
无序性（以 HashSet 为例）：
- 不等于随机性
- 不能理解为 “元素的遍历顺序与添加顺序不一样”
  因为 LinkedHashSet 的两个顺序是一样的
- 与添加的元素的位置有关，不像 ArrayList 一样是依次紧密排列的
- 根据添加的元素的哈希值，计算其存储位置，此位置不是依次紧密排列的，表现为无序性
不可重复性（以 HashSet 为例）：
- 添加到 Set 中的元素是不能相同的
- 比较的标准，需要判断 hashCode () 得到的哈希值，以及 equals () 得到的 boolean 结果
- 哈希值相同，且 equals () 返回 true，则认为元素是相同的
  hashCode () 不能保证对于不同的实例得到不同的哈希值... 因此需要借助 equals ()
添加到 HashSet / LinkedHashSet 中元素的要求：
- 元素所在类要重写 equals () 和 hashCode ()
- 同时要求 equals () 和 hashCode () 保持一致性！
  只需要在 IDEA 中自动生成这两个方法的重写即可。
小结

Set 接口的实现类	HashSet	LinkedHashSet	TreeSet
地位	主要实现类	HashSet 的子类	了解即可
底层实现（存储在 key 中）	HashMap	LinkedHashMap	TreeMap
数据结构	数组 + 单向链表 + 红黑树	数组 + 单向链表 + 红黑树 + 双向链表	红黑树
对添加的元素的要求	所在类要重写 `equals()` 和 `hashCode()` ，同时要求二者保持一致性	与 HashSet 相同	属于同一个类，且要求该类实现 `Comparable接口` 并重写 `compareTo(Object obj)` ，或者定义一个 `Comparator接口` 的实现类实例，并重写 `compare(Object o1,Object o2)` ，将实例作为参数传递给 TreeSet 的构造器
遍历顺序	与添加顺序不同	与添加顺序相同（得益于双向链表）	按照指定属性的大小顺序
判断两个元素相等的标准	`hashCode()` 返回的哈希值相等，且 `equals()` 返回 true	与 HashSet 相同	两个对象通过 `compareTo(Object obj) 或compare(Object o1,Object o2)` 方法的返回值为 0
特点	线程不安全，元素可以是 null	`插入性能略低` 于 HashSet，但在 `迭代访问` Set 里的全部元素时有很好的性能	可以实现自然排序、定制排序

# 5.2 Set 主要实现类：HashSet

# 5.2.1 HashSet 概述

HashSet 是 Set 接口的主要实现类，大多数时候使用 Set 集合时都使用这个实现类。
HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存储、查找、删除性能。
HashSet 具有以下 特点 ：
- 无序：不能保证元素的排列顺序
- HashSet 是线程不安全的
- 集合元素可以是 null
HashMap 中元素的特点：
- key 无序、不可重复，构成一个（Hash）Set 集合
  因此 key 所在类要重写 hashCode() 和 equals()
- value 无序、可重复，构成一个 Collection 集合
  因此 value 所在类要重写 equals()
- entry=（key，value）无序、不可重复，构成一个 Set 集合
- 为了避免麻烦，一般对于要添加到集合中的元素所在类，同时重写 hashCode() 和 equals()
  宁滥勿缺
底层使用 HashMap 实现，即使用 数组+单向链表+红黑树 进行存储（JDK8）
HashSet 集合 判断两个元素相等的标准 ：两个对象通过 hashCode() 方法得到的哈希值相等，并且两个对象的 equals() 方法返回值为 true。
对于存放在 Set 容器中的对象，对应的类一定要重写 hashCode () 和 equals (Object obj) 方法，同时这两个方法要保证一致性，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。
HashSet 集合中元素的无序性，不等同于随机性。这里的无序性与元素的添加位置有关。具体来说：我们在添加每一个元素到数组中时，具体的存储位置是由元素的 hashCode () 调用后返回的 hash 值决定的。导致在数组中每个元素不是依次紧密存放的，表现出一定的无序性。

# 5.2.2 HashSet 中添加元素的过程：

第 1 步：当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法得到该对象的 hashCode 值，然后根据 hashCode 值，通过某个散列函数决定该对象在 HashSet 底层数组中的存储位置。
第 2 步：如果要在数组中存储的位置上没有元素，则直接添加成功，保存在底层数组中。
第 3 步：如果要在数组中存储的位置上有元素，则继续比较：
- 如果两个元素的hashCode 值不相等，则添加成功，通过 链表 的方式继续链接，存储。
- 如果两个元素的hashCode () 值相等，则会继续调用 **equals ()** 方法：
  - 如果 equals () 方法结果为false，则添加成功，通过 链表 的方式继续链接，存储。
  - 如果 equals () 方法结果为true，则添加失败。
第 2 步添加成功，元素会保存在底层数组中。
第 3 步两种添加成功的操作，由于该底层数组的位置已经有元素了，则会通过 链表 的方式继续链接，存储。

举例 1：

测试类：

	/**
	* 向 HashSet 中添加数据时，hashCode () 与 equals () 调用顺序为：
	* 1. 先调用 hashCode () 方法，计算出哈希值
	* 2. 通过某个散列算法，将哈希值转换成数组下标
	* 3. 如果该数组下标位置没有元素，则直接将该元素添加进去，保存在数组中
	* 4. 如果该数组下标位置有元素，则比较哈希值：
	* - 如果哈希值不同，则直接将该元素添加进去，通过链表的方式保存
	* - 如果哈希值相同，则比较 equals () 方法：
	* -- 如果 equals () 方法返回 false，则直接将该元素添加进去，通过链表的方式保存
	* -- 如果 equals () 方法返回 true，则不添加该元素
	*/
	@Test
	public void test1() {
	HashSet set = new HashSet();
	Person p1 = new Person(1001, "AA");
	Person p2 = new Person(1002, "BB");

	set.add(p1);
	set.add(p2);
	p1.name = "CC";
	set.remove(p1); //p1 存储时的哈希值是根据 id:1001,name:"AA" 计算出来的，而现在 p1 的 name 已经变成了 "CC"，计算出来的哈希值就不一样了，所以 remove 不掉
	System.out.println(set); // [Person{id=1002, name='BB'}, Person{id=1001, name='CC'}]

	set.add(new Person(1001, "CC")); // 该对象的哈希值是根据 id:1001,name:"CC" 计算出来的，所以可以添加进去
	System.out.println(set); // [Person{id=1002, name='BB'}, Person{id=1001, name='CC'}, Person{id=1001, name='CC'}]

	set.add(new Person(1001, "AA")); // 该对象的哈希值是根据 id:1001,name:"AA" 计算出来的，即使与 p1 的哈希值一样，但是此时 equals () 方法返回 false（因为 name 不一样），所以可以添加进去
	System.out.println(set); // [Person{id=1002, name='BB'}, Person{id=1001, name='CC'}, Person{id=1001, name='CC'}, Person{id=1001, name='AA'}]
	}

Person 类：

	public class Person {
	private int id;
	public String name;

	public Person() {
	}

	public Person(int id, String name) {
	this.id = id;
	this.name = name;
	}

	@Override
	public boolean equals(Object o) {
	System.out.println("Person.equals()...");
	if (this == o) {
	return true;
	}
	if (!(o instanceof Person)) {
	return false;
	}
	Person person = (Person) o;
	return getId() == person.getId() && Objects.equals(getName(), person.getName());
	}

	@Override
	public int hashCode() {
	return Objects.hash(getId(), getName());
	}

	@Override
	public String toString() {
	return "Person{" +
	"id=" + id +
	", name='" + name + '\'' +
	'}';
	}

	public int getId() {
	return id;
	}

	public void setId(int id) {
	this.id = id;
	}

	public String getName() {
	return name;
	}

	public void setName(String name) {
	this.name = name;
	}
	}

举例 2：

	package com.atguigu.set;

	import java.util.Objects;

	public class MyDate {
	private int year;
	private int month;
	private int day;

	public MyDate(int year, int month, int day) {
	this.year = year;
	this.month = month;
	this.day = day;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) return true;
	if (o == null \|\| getClass() != o.getClass()) return false;
	MyDate myDate = (MyDate) o;
	return year == myDate.year &&
	month == myDate.month &&
	day == myDate.day;
	}

	@Override
	public int hashCode() {
	return Objects.hash(year, month, day);
	}

	@Override
	public String toString() {
	return "MyDate{" +
	"year=" + year +
	", month=" + month +
	", day=" + day +
	'}';
	}
	}

	package com.atguigu.set;

	import org.junit.Test;

	import java.util.HashSet;

	public class TestHashSet {
	@Test
	public void test01(){
	HashSet set = new HashSet();
	set.add("张三");
	set.add("张三");
	set.add("李四");
	set.add("王五");
	set.add("王五");
	set.add("赵六");

	System.out.println("set = " + set);// 不允许重复，无序
	}

	@Test
	public void test02(){
	HashSet set = new HashSet();
	set.add(new MyDate(2021,1,1));
	set.add(new MyDate(2021,1,1));
	set.add(new MyDate(2022,2,4));
	set.add(new MyDate(2022,2,4));


	System.out.println("set = " + set);// 不允许重复，无序
	}
	}

# 5.2.3 重写 hashCode () 方法的基本原则

在程序运行时，同一个对象多次调用 hashCode () 方法应该返回相同的值。
当两个对象的 equals () 方法比较返回 true 时，这两个对象的 hashCode () 方法的返回值也应相等。
equals () 与 hashCode () 的一致性
对象中用作 equals () 方法比较的 Field，都应该用来计算 hashCode 值。

注意：如果两个元素的 equals () 方法返回 true，但它们的 hashCode () 返回值不相等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功。

# 5.2.4 重写 equals () 方法的基本原则

重写 equals 方法的时候一般都需要同时复写 hashCode 方法。通常参与计算 hashCode 的对象的属性也应该参与到 equals () 中进行计算。

推荐：开发中直接调用 Eclipse/IDEA 里的快捷键自动重写 equals () 和 hashCode () 方法即可。

为什么用 Eclipse/IDEA 复写 hashCode 方法，有 31 这个数字？

首先，选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。（减少冲突）

其次，31只占用5bits,相乘造成数据溢出的概率较小。

再次，31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。（提高算法效率）

最后，31是一个素数，素数作用就是如果我用一个数字来乘以这个素数，那么最终出来的结果只能被素数本身和被乘数还有1来整除！(减少冲突)

# 5.2.5 练习

** 练习 1：** 在 List 内去除重复数字值，要求尽量简单

	public static List duplicateList(List list) {
	HashSet set = new HashSet(list);
	return new ArrayList(set);
	}
	public static void main(String[] args) {
	List list = new ArrayList();
	list.add(new Integer(1));
	list.add(new Integer(2));
	list.add(new Integer(2));
	list.add(new Integer(4));
	list.add(new Integer(4));
	List list2 = duplicateList(list);
	for (Object integer : list2) {
	System.out.println(integer);
	}
	}

** 练习 2：** 获取随机数

编写一个程序，获取 10 个 1 至 20 的随机数，要求随机数不能重复。并把最终的随机数输出到控制台。

	/**
	*
	* @Description
	* @author 尚硅谷 - 宋红康
	* @date 2022 年 5 月 7 日上午 12:43:01
	*
	*/
	public class RandomValueTest {
	public static void main(String[] args) {
	HashSet hs = new HashSet(); // 创建集合对象
	Random r = new Random();
	while (hs.size() < 10) {
	int num = r.nextInt(20) + 1; // 生成 1 到 20 的随机数
	hs.add(num);
	}

	for (Integer integer : hs) { // 遍历集合
	System.out.println(integer); // 打印每一个元素
	}
	}
	}

** 练习 3：** 去重

使用 Scanner 从键盘读取一行输入，去掉其中重复字符，打印出不同的那些字符。比如：aaaabbbcccddd

	/**
	*
	* @Description
	* @author 尚硅谷 - 宋红康
	* @date 2022 年 5 月 7 日上午 12:44:01
	*
	*/
	public class DistinctTest {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in); // 创建键盘录入对象
	System.out.println("请输入一行字符串:");
	String line = sc.nextLine(); // 将键盘录入的字符串存储在 line 中
	char[] arr = line.toCharArray(); // 将字符串转换成字符数组

	HashSet hs = new HashSet(); // 创建 HashSet 集合对象

	for (Object c : arr) { // 遍历字符数组
	hs.add(c); // 将字符数组中的字符添加到集合中
	}

	for (Object ch : hs) { // 遍历集合
	System.out.print(ch);
	}
	}
	}

** 练习 4：** 面试题

	public class Person {
	private int id;
	public String name;

	public Person() {
	}

	public Person(int id, String name) {
	this.id = id;
	this.name = name;
	}

	@Override
	public boolean equals(Object o) {
	System.out.println("Person.equals()...");
	if (this == o) {
	return true;
	}
	if (!(o instanceof Person)) {
	return false;
	}
	Person person = (Person) o;
	return getId() == person.getId() && Objects.equals(getName(), person.getName());
	}

	@Override
	public int hashCode() {
	return Objects.hash(getId(), getName());
	}

	@Override
	public String toString() {
	return "Person{" +
	"id=" + id +
	", name='" + name + '\'' +
	'}';
	}

	public int getId() {
	return id;
	}

	public void setId(int id) {
	this.id = id;
	}

	public String getName() {
	return name;
	}

	public void setName(String name) {
	this.name = name;
	}
	}

	/**
	* 向 HashSet 中添加数据时，hashCode () 与 equals () 调用顺序为：
	* 1. 先调用 hashCode () 方法，计算出哈希值
	* 2. 通过某个散列算法，将哈希值转换成数组下标
	* 3. 如果该数组下标位置没有元素，则直接将该元素添加进去，保存在数组中
	* 4. 如果该数组下标位置有元素，则比较哈希值：
	* - 如果哈希值不同，则直接将该元素添加进去，通过链表的方式保存
	* - 如果哈希值相同，则比较 equals () 方法：
	* -- 如果 equals () 方法返回 false，则直接将该元素添加进去，通过链表的方式保存
	* -- 如果 equals () 方法返回 true，则不添加该元素
	*/
	@Test
	public void test1() {
	HashSet set = new HashSet();
	Person p1 = new Person(1001, "AA");
	Person p2 = new Person(1002, "BB");

	set.add(p1);
	set.add(p2);
	p1.name = "CC";
	set.remove(p1); //p1 存储时的哈希值是根据 id:1001,name:"AA" 计算出来的，而现在 p1 的 name 已经变成了 "CC"，计算出来的哈希值就不一样了，所以 remove 不掉
	System.out.println(set); // [Person{id=1002, name='BB'}, Person{id=1001, name='CC'}]

	set.add(new Person(1001, "CC")); // 该对象的哈希值是根据 id:1001,name:"CC" 计算出来的，所以可以添加进去
	System.out.println(set); // [Person{id=1002, name='BB'}, Person{id=1001, name='CC'}, Person{id=1001, name='CC'}]

	set.add(new Person(1001, "AA")); // 该对象的哈希值是根据 id:1001,name:"AA" 计算出来的，即使与 p1 的哈希值一样，但是此时 equals () 方法返回 false（因为 name 不一样），所以可以添加进去
	System.out.println(set); // [Person{id=1002, name='BB'}, Person{id=1001, name='CC'}, Person{id=1001, name='CC'}, Person{id=1001, name='AA'}]
	}

运行结果：

# 5.3 Set 实现类之二：LinkedHashSet

LinkedHashSet 是 HashSet 的子类，不允许集合元素重复。
底层使用 LinkedHashMap 实现，使用 数组+单向链表+红黑树 +** 双向链表 ** 进行存储，其中双向链表用于记录元素的添加顺序，那么我们可以按照元素的添加顺序进行遍历，便于频繁的查询。
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用 双向链表 维护元素的次序，这使得元素看起来是以 添加顺序 保存的。
LinkedHashSet 插入性能略低 于 HashSet，但在 迭代访问 Set 里的全部元素时有很好的性能。

举例：

	package com.atguigu.set;

	import org.junit.Test;

	import java.util.LinkedHashSet;

	public class TestLinkedHashSet {
	@Test
	public void test01(){
	LinkedHashSet set = new LinkedHashSet();
	set.add("张三");
	set.add("张三");
	set.add("李四");
	set.add("王五");
	set.add("王五");
	set.add("赵六");

	System.out.println("set = " + set);// 不允许重复，体现添加顺序
	}
	}

# 5.4 Set 实现类之三：TreeSet

# 5.4.1 TreeSet 概述

TreeSet 是 SortedSet 接口的实现类，TreeSet 可以按照添加的元素的指定的属性的大小顺序进行遍历。
TreeSet底层使用 红黑树 结构存储数据
新增的方法如下： (了解)
- Comparator comparator()
- Object first()
- Object last()
- Object lower(Object e)
- Object higher(Object e)
- SortedSet subSet(fromElement, toElement)
- SortedSet headSet(toElement)
- SortedSet tailSet(fromElement)
TreeSet特点：不允许重复、实现排序（自然排序或定制排序）
TreeSet 两种排序方法： 自然排序 和 定制排序 。默认情况下，TreeSet 采用自然排序。
- 自然排序 ：TreeSet 会调用集合元素的 compareTo (Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序 (默认情况) 排列。
  - 如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable 接口。
  - 实现 Comparable 的类必须实现 compareTo (Object obj) 方法，两个对象即通过 compareTo (Object obj) 方法的返回值来比较大小。
- 定制排序 ：如果元素所属的类没有实现 Comparable 接口，或不希望按照升序 (默认情况) 的方式排列元素，或希望按照其它属性大小进行排序，则考虑使用定制排序。定制排序，通过 Comparator 接口来实现。需要重写 **compare (T o1,T o2)** 方法。
  - 利用 int compare (T o1,T o2) 方法，比较 o1 和 o2 的大小：如果方法返回正整数，则表示 o1 大于 o2；如果返回 0，表示相等；返回负整数，表示 o1 小于 o2。
  - 要实现定制排序，需要将实现 Comparator 接口的实例作为形参传递给TreeSet 的构造器。
因为只有相同类的两个实例才会比较大小，所以向 TreeSet 中添加的应该是 同一个类的对象 。
对于 TreeSet 集合而言，它判断 两个对象是否相等的唯一标准 是：两个对象通过 compareTo(Object obj) 或compare(Object o1,Object o2) 方法比较返回值。返回值为 0，则认为两个对象相等。

# 5.4.2 举例

举例 1：

User 定义类：

	public class User implements Comparable {
	private String name;
	private int age;

	public User(String name, int age) {
	this.name = name;
	this.age = age;
	}

	public String getName() {
	return name;
	}

	public void setName(String name) {
	this.name = name;
	}

	public int getAge() {
	return age;
	}

	public void setAge(int age) {
	this.age = age;
	}

	/**
	* 按照年龄从小到大排序，年龄相同，按照姓名从大到小排序
	*
	* @param o
	* @return
	*/
	@Override
	public int compareTo(Object o) {
	if (this == o) {
	return 0;
	}
	if (o instanceof User) {
	User user = (User) o;
	if (this.age - user.age != 0) {
	return this.age - user.age;
	} else {
	return -this.name.compareTo(user.name);
	}
	} else {
	throw new RuntimeException("输入的类型不匹配");
	}
	}

	@Override
	public String toString() {
	return "User{" +
	"name='" + name + '\'' +
	", age=" + age +
	'}';
	}
	}

测试类：

	public class TreeSetTest {
	/**
	* 自然排序：针对 String 类型，天然实现了 Comparable 接口，按照字典顺序进行排序
	*/
	@Test
	public void test1() {
	Set treeSet = new TreeSet();
	// TreeSet 要求所添加的元素必须是同一种类型，因为 TreeSet 是按照元素中指定属性的大小进行排序的
	treeSet.add("a");
	treeSet.add("b");
	treeSet.add("c");
	//treeSet.add (1); 编译报错 ClassCastException，因为 TreeSet 中的元素必须是同一种类型
	// 遍历：iterator，且遍历顺序是按照元素中指定属性的大小进行排序的，对于 String 类型，天然实现了 Comparable 接口，按照字典顺序进行排序
	Iterator iterator = treeSet.iterator();
	while (iterator.hasNext()) {
	System.out.println(iterator.next());
	}
	}

	/**
	* 自然排序：针对自定义类型，需要实现 Comparable 接口，并重写 compareTo 方法
	*/
	@Test
	public void test2() {
	TreeSet treeSet = new TreeSet();
	treeSet.add(new User("Tom", 23));
	treeSet.add(new User("Jerry", 43));
	treeSet.add(new User("Rose", 13));
	treeSet.add(new User("Jack", 23));
	treeSet.add(new User("Tony", 33));
	// 遍历：iterator，且遍历顺序是按照元素中指定属性的大小进行排序的，对于自定义类型，需要实现 Comparable 接口，并重写 compareTo 方法
	Iterator iterator = treeSet.iterator();
	while (iterator.hasNext()) {
	System.out.println(iterator.next());
	}
	}

	/**
	* 定制排序：需要实现 Comparator 接口，并重写 compare 方法，将实现类的实例对象作为参数传入 TreeSet 的构造器中
	*/
	@Test
	public void test3() {
	// 定义一个 Comparator 的匿名实现类的对象
	Comparator comparator = new Comparator() {
	/**
	* 按照年龄从小到大排序，年龄相同，按照姓名从大到小排序
	*/
	@Override
	public int compare(Object o1, Object o2) {
	if (o1 instanceof User && o2 instanceof User) {
	User user1 = (User) o1;
	User user2 = (User) o2;
	if (user1.getAge() == user2.getAge()) {
	return -user1.getName().compareTo(user2.getName());
	} else {
	return Integer.compare(user1.getAge(), user2.getAge());
	}
	} else {
	throw new RuntimeException("输入的类型不匹配");
	}
	}
	};
	// 将 Comparator 的匿名实现类的对象作为参数传入 TreeSet 的构造器中
	TreeSet treeSet = new TreeSet(comparator);
	treeSet.add(new User("Tom", 23));
	treeSet.add(new User("Jerry", 43));
	treeSet.add(new User("Rose", 13));
	treeSet.add(new User("Jack", 23));
	treeSet.add(new User("Tony", 33));
	// 遍历：iterator，且遍历顺序是按照元素中指定属性的大小进行排序的，对于自定义类型，需要实现 Comparable 接口，并重写 compareTo 方法
	Iterator iterator = treeSet.iterator();
	while (iterator.hasNext()) {
	System.out.println(iterator.next());
	}
	}
	}

举例 2：

	package com.atguigu.set;


	import org.junit.Test;
	import java.util.Iterator;
	import java.util.TreeSet;

	/**
	* @author 尚硅谷 - 宋红康
	* @create 14:22
	*/
	public class TreeSetTest {
	/*
	* 自然排序：针对 String 类的对象
	* */
	@Test
	public void test1(){
	TreeSet set = new TreeSet();

	// TreeSet 要求所添加的元素必须是同一种类型，因为 TreeSet 是按照元素中指定属性的大小进行排序的
	set.add("MM");
	set.add("CC");
	set.add("AA");
	set.add("DD");
	set.add("ZZ");
	//set.add (123); // 报 ClassCastException 的异常

	// 遍历：iterator，且遍历顺序是按照元素中指定属性的大小进行排序的，对于 String 类型，天然实现了 Comparable 接口，按照字典顺序进行排序
	Iterator iterator = set.iterator();
	while(iterator.hasNext()){
	System.out.println(iterator.next());
	}
	}
	/*
	* 自然排序：针对 User 类的对象
	* */
	@Test
	public void test2(){
	TreeSet set = new TreeSet();

	set.add(new User("Tom",12));
	set.add(new User("Rose",23));
	set.add(new User("Jerry",2));
	set.add(new User("Eric",18));
	set.add(new User("Tommy",44));
	set.add(new User("Jim",23));
	set.add(new User("Maria",18));
	//set.add("Tom");

	Iterator iterator = set.iterator();
	while(iterator.hasNext()){
	System.out.println(iterator.next());
	}

	System.out.println(set.contains(new User("Jack", 23))); //true
	}
	}

其中，User 类定义如下：

	/**
	* @author 尚硅谷 - 宋红康
	* @create 14:22
	*/
	public class User implements Comparable{
	String name;
	int age;

	public User() {
	}

	public User(String name, int age) {
	this.name = name;
	this.age = age;
	}

	@Override
	public String toString() {
	return "User{" +
	"name='" + name + '\'' +
	", age=" + age +
	'}';
	}
	/*
	举例：按照 age 从小到大的顺序排列，如果 age 相同，则按照 name 从大到小的顺序排列
	* */
	public int compareTo(Object o) {
	if(this == o){
	return 0;
	}

	if(o instanceof User){
	User user = (User)o;
	int value = this.age - user.age;
	if(value != 0){
	return value;
	}
	return -this.name.compareTo(user.name);
	}
	throw new RuntimeException("输入的类型不匹配");
	}
	}

举例 3：

	/*
	* 定制排序
	* */
	@Test
	public void test3(){
	// 按照 User 的姓名的从小到大的顺序排列
	Comparator comparator = new Comparator() {
	@Override
	public int compare(Object o1, Object o2) {
	if(o1 instanceof User && o2 instanceof User){
	User u1 = (User)o1;
	User u2 = (User)o2;

	return u1.name.compareTo(u2.name);
	}
	throw new RuntimeException("输入的类型不匹配");
	}
	};
	TreeSet set = new TreeSet(comparator);

	set.add(new User("Tom",12));
	set.add(new User("Rose",23));
	set.add(new User("Jerry",2));
	set.add(new User("Eric",18));
	set.add(new User("Tommy",44));
	set.add(new User("Jim",23));
	set.add(new User("Maria",18));
	//set.add(new User("Maria",28));

	Iterator iterator = set.iterator();
	while(iterator.hasNext()){
	System.out.println(iterator.next());
	}
	}

# 5.4.3 练习

public class User implements Comparable {
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    /**
     * 按照年龄从小到大排序，年龄相同，按照姓名从大到小排序
     *
     * @param o
     * @return
     */
    @Override
    public int compareTo(Object o) {
        if (this == o) {
            return 0;
        }
        if (o instanceof User) {
            User user = (User) o;
            if (this.age - user.age != 0) {
                return this.age - user.age;
            } else {
                return -this.name.compareTo(user.name);
            }
        } else {
            throw new RuntimeException("输入的类型不匹配");
        }
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

** 练习 1：** 在一个 List 集合中存储了多个无大小顺序并且有重复的字符串，定义一个方法，让其有序 (从小到大排序)，并且不能去除重复元素。

提示：考查 ArrayList、TreeSet

	/**
	*
	* @Description
	* @author 尚硅谷 - 宋红康
	* @date 2022 年 4 月 7 日上午 12:50:46
	*
	*/
	public class SortTest {
	public static void main(String[] args) {
	ArrayList list = new ArrayList();
	list.add("ccc");
	list.add("ccc");
	list.add("aaa");
	list.add("aaa");
	list.add("bbb");
	list.add("ddd");
	list.add("ddd");
	sort(list);
	System.out.println(list);
	}

	/*
	* 对集合中的元素排序，并保留重复
	*/
	public static void sort(List list) {
	TreeSet ts = new TreeSet(new Comparator() {
	@Override
	public int compare(Object o1, Object o2) { // 重写 compare 方法
	String s1 = (String)o1;
	String s2 = (String)o2;
	int num = s1.compareTo(s2); // 比较内容
	return num == 0 ? 1 : num; // 如果内容一样返回一个不为 0 的数字即可
	}
	});

	ts.addAll(list); // 将 list 集合中的所有元素添加到 ts 中
	list.clear(); // 清空 list
	list.addAll(ts); // 将 ts 中排序并保留重复的结果在添加到 list 中
	}
	}

** 练习 2：**TreeSet 的自然排序和定制排序

定义一个 Employee 类。
该类包含：private 成员变量 name,age,birthday，其中 birthday 为 MyDate 类的对象；
并为每一个属性定义 getter, setter 方法；
并重写 toString 方法输出 name, age, birthday
MyDate 类包含:
private 成员变量 year,month,day；并为每一个属性定义 getter, setter 方法；
创建该类的 5 个对象，并把这些对象放入 TreeSet 集合中（下一章：TreeSet 需使用泛型来定义）
分别按以下两种方式对集合中的元素进行排序，并遍历输出：
1). 使 Employee 实现 Comparable 接口，并按 name 排序
2). 创建 TreeSet 时传入 Comparator 对象，按生日日期的先后排序。

代码实现：

	public class MyDate implements Comparable{
	private int year;
	private int month;
	private int day;

	public MyDate() {
	}

	public MyDate(int year, int month, int day) {
	this.year = year;
	this.month = month;
	this.day = day;
	}

	public int getYear() {
	return year;
	}

	public void setYear(int year) {
	this.year = year;
	}

	public int getMonth() {
	return month;
	}

	public void setMonth(int month) {
	this.month = month;
	}

	public int getDay() {
	return day;
	}

	public void setDay(int day) {
	this.day = day;
	}

	@Override
	public String toString() {
	// return "MyDate{" +
	// "year=" + year +
	// ", month=" + month +
	// ", day=" + day +
	// '}';
	return year + "年" + month + "月" + day + "日";
	}

	@Override
	public int compareTo(Object o) {
	if(this == o){
	return 0;
	}
	if(o instanceof MyDate){
	MyDate myDate = (MyDate) o;
	int yearDistance = this.getYear() - myDate.getYear();
	if(yearDistance != 0){
	return yearDistance;
	}
	int monthDistance = this.getMonth() - myDate.getMonth();
	if(monthDistance != 0){
	return monthDistance;
	}

	return this.getDay() - myDate.getDay();
	}
	throw new RuntimeException("输入的类型不匹配");
	}
	}

	public class Employee implements Comparable{
	private String name;
	private int age;
	private MyDate birthday;


	public Employee() {
	}

	public Employee(String name, int age, MyDate birthday) {
	this.name = name;
	this.age = age;
	this.birthday = birthday;
	}

	public String getName() {
	return name;
	}

	public void setName(String name) {
	this.name = name;
	}

	public int getAge() {
	return age;
	}

	public void setAge(int age) {
	this.age = age;
	}

	public MyDate getBirthday() {
	return birthday;
	}

	public void setBirthday(MyDate birthday) {
	this.birthday = birthday;
	}

	@Override
	public String toString() {
	return "Employee{" +
	"name='" + name + '\'' +
	", age='" + age + '\'' +
	", birthday=" + birthday +
	'}';
	}

	@Override
	public int compareTo(Object o) {
	if(o == this){
	return 0;
	}
	if(o instanceof Employee){
	Employee emp = (Employee) o;
	return this.name.compareTo(emp.name);
	}
	throw new RuntimeException("传入的类型不匹配");
	}
	}

	public class EmployeeTest {
	/*
	自然排序：
	创建该类的 5 个对象，并把这些对象放入 TreeSet 集合中
	* 需求 1：使 Employee 实现 Comparable 接口，并按 name 排序
	* */
	@Test
	public void test1(){
	TreeSet set = new TreeSet();

	Employee e1 = new Employee("Tom",23,new MyDate(1999,7,9));
	Employee e2 = new Employee("Rose",43,new MyDate(1999,7,19));
	Employee e3 = new Employee("Jack",54,new MyDate(1998,12,21));
	Employee e4 = new Employee("Jerry",12,new MyDate(2002,4,21));
	Employee e5 = new Employee("Tony",22,new MyDate(2001,9,12));

	set.add(e1);
	set.add(e2);
	set.add(e3);
	set.add(e4);
	set.add(e5);

	// 遍历
	Iterator iterator = set.iterator();
	while(iterator.hasNext()){
	System.out.println(iterator.next());
	}
	}

	/*
	* 定制排序：
	* 创建 TreeSet 时传入 Comparator 对象，按生日日期的先后排序。
	* */
	@Test
	public void test2(){
	Comparator comparator = new Comparator() {
	@Override
	public int compare(Object o1, Object o2) {
	if(o1 instanceof Employee && o2 instanceof Employee){
	Employee e1 = (Employee) o1;
	Employee e2 = (Employee) o2;
	// 对比两个 employee 的生日的大小
	MyDate birth1 = e1.getBirthday();
	MyDate birth2 = e2.getBirthday();
	// 方式 1：
	// int yearDistance = birth1.getYear() - birth2.getYear();
	// if(yearDistance != 0){
	// return yearDistance;
	// }
	// int monthDistance = birth1.getMonth() - birth2.getMonth();
	// if(monthDistance != 0){
	// return monthDistance;
	// }
	//
	// return birth1.getDay() - birth2.getDay();

	// 方式 2：
	return birth1.compareTo(birth2);
	}

	throw new RuntimeException("输入的类型不匹配");

	}
	};
	TreeSet set = new TreeSet(comparator);

	Employee e1 = new Employee("Tom",23,new MyDate(1999,7,9));
	Employee e2 = new Employee("Rose",43,new MyDate(1999,7,19));
	Employee e3 = new Employee("Jack",54,new MyDate(1998,12,21));
	Employee e4 = new Employee("Jerry",12,new MyDate(2002,4,21));
	Employee e5 = new Employee("Tony",22,new MyDate(2001,9,12));

	set.add(e1);
	set.add(e2);
	set.add(e3);
	set.add(e4);
	set.add(e5);

	// 遍历
	Iterator iterator = set.iterator();
	while(iterator.hasNext()){
	System.out.println(iterator.next());
	}

	}
	}

# 6. Map 接口

现实生活与开发中，我们常会看到这样的一类集合：用户 ID 与账户信息、学生姓名与考试成绩、IP 地址与主机名等，这种一一对应的关系，就称作映射。Java 提供了专门的集合框架用来存储这种映射关系的对象，即 java.util.Map 接口。

小结

HashMap 中元素的特点：

key 无序、不可重复，构成一个 HashSet 集合
因此 key 所在类要重写 hashCode() 和 equals()
value 无序、可重复，构成一个 Collection 集合
因此 value 所在类要重写 equals()
entry=（key，value）无序、不可重复，构成一个 Set 集合
为了避免麻烦，一般对于要添加到集合中的元素所在类，同时重写 hashCode() 和 equals()
宁滥勿缺

Map 接口的各个实现类对比：

Map 接口的实现类	HashMap	LinkedHashMap	TreeMap	~~Hashtable~~	Properties
地位	主要实现类	HashMap 的子类		古老实现类	~~Hashtable~~ 的子类
底层实现	哈希表	哈希表 + 双向链表	红黑树	哈希表	哈希表
数据结构	一维数组 + 单向链表（+ 红黑树）	一维数组 + 单向链表（+ 红黑树） + 双向链表	红黑树	一维数组 + 单向链表	一维数组 + 单向链表
键、值是否允许为 null	是	是	键不能为 null，值可以为 null	键和值都不能为 null	键和值都不能为 null
是否线程安全	否	否	否	是，因此效率低	是，因此效率低
特点	查找、插入、删除速度快，但不保证元素的顺序	保证元素的插入 / 访问顺序	可以按照 key 中的指定属性的大小顺序进行遍历：①自然排序；②定制排序	线程安全，效率低	键和值都是 String 类型
性能	①查找、插入、删除速度快；②迭代遍历速度慢（因为和容量有关，需要遍历底层数组，以及每个数组元素对应的链表 / 红黑树，数组的长度就是 HashMap 的容量）	①插入、删除速度慢；②迭代遍历比 HashMap 快（因为只和实际数据有关，和容量无关）	查找、插入、删除速度慢（因为要维护红黑树的平衡、顺序）
内存	占用大，保存数组		占用小，保存节点
使用场景	快速的查找和插入，不要求元素的顺序	需要保持元素的插入顺序或者访问顺序	适用于需要有序的键值对集合	适用于需要线程安全的场景	以键值对的方式存储配置信息
补充说明	在 JDK8 引入红黑树	双向链表: 记录元素的添加顺序	①自然排序（key 所在类实现了 Comparable 接口）；②定制排序（在创建 TreeMap 时传入 Comparator 对象）；
要求 key	key 所在类要重写 `hashCode()` 和 `equals()`	与 HashMap 相同	key 必须是同一个类的对象	与 HashMap 相同	key 是 String 类
要求 value	value 所在类要重写 `equals()`	与 HashMap 相同	无	与 HashMap 相同	value 是 String 类
判断 key 相等的标准	hashCode 值相等；equals () 返回 true；	与 HashMap 相同	`containsKey()` ：当实现了 key 的排序后，需要两个 key 通过 compareTo () 方法或者 compare () 方法返回 0	与 HashMap 相同	String 中重写的 equals () 返回 true
判断 value 相等的标准	equals () 返回 true；	与 HashMap 相同		与 HashMap 相同	String 中重写的 equals () 返回 true

面试题

区别 HashMap 和 Hashtable（考虑线程安全、键值是否可以是 null）
区别 HashMap 和 LinkedHashMap（考虑底层实现的数据结构、使用场景）
HashMap 的底层实现（① new HashMap(); 的过程；② put(key,value); 的过程）

# 6.1 Map 接口概述

Map 与 Collection 并列存在。用于保存具有 映射关系 的数据：key-value
- Collection 集合称为单列集合，元素是孤立存在的（理解为单身）。
- Map 集合称为双列集合，元素是成对存在的 (理解为夫妻)。
Map 中的 key 和 value 都可以是任何引用类型的数据。但常用 String 类作为 Map 的 “键”。
Map 接口的常用实现类： HashMap 、 LinkedHashMap 、 TreeMap 和 Properties 。其中，HashMap 是 Map 接口使用 频率最高 的实现类。

# 6.2 Map 中 key-value 特点

这里主要以 HashMap 为例说明。HashMap 中存储的 key、value 的特点如下：

Map 中的 key用Set来存放 ， 不允许重复 ，即同一个 Map 对象所对应的类，须重写 hashCode () 和 equals () 方法
key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value，不同 key 对应的 value可以重复 。value 所在的类要重写 equals () 方法。
key 和 value 构成一个 entry。所有的entry 之间是 无序的 、 不可重复的 。

# 6.2 Map 接口的常用方法

因为无序，所以没有插入操作，只有增、删、改、查、长度、遍历（ keySet() 、 values() 、 entrySet() ）

添加、修改操作：
- Object put(Object key,Object value)：将指定 key-value添加到 (或修改)当前 map 对象中
- void putAll(Map m): 将 m 中的所有 key-value 对存放到当前 map 中
删除操作：
- Object remove(Object key)：移除指定 key 的 key-value 对，并返回 value
- void clear()：清空当前 map 中的所有数据
元素查询的操作：
- Object get(Object key)：获取指定 key 对应的 value
- boolean containsKey(Object key)：是否包含指定的 key
- boolean containsValue(Object value)：是否包含指定的 value
- int size()：返回 map 中 key-value 对的个数
- boolean isEmpty()：判断当前 map 是否为空
- boolean equals(Object obj)：判断当前 map 和参数对象 obj 是否相等
元视图操作的方法：
- Set keySet()：返回所有 key 构成的Set 集合
- Collection values()：返回所有 value 构成的Collection 集合
- Set entrySet()：返回所有 key-value 对构成的Set 集合

举例：

	/**
	* 通过 HashMap 测试 Map 接口中的方法：
	* - 添加、修改
	* --（1）put (Object key, Object value)
	* --（2）putAll (Map m)
	* - 删除
	* --（1）clear ()
	* --（2）remove (Object key)
	* - 查询
	* --（1）get (Object key)
	* --（2）containsKey (Object key)
	* --（3）containsValue (Object value)
	* --（4）isEmpty ()
	* --（5）size ()
	* - 遍历
	* --（1）keySet ()
	* --（2）values ()
	* --（3）entrySet ()
	* - 遍历方式有三种：
	* --（1）增强 for 循环
	* --（2）迭代器（因为 Collection 继承了 Iterable 接口，而 Set 也继承了 Collection，因此都有 iterator () 方法）
	* --（3）JDK8 中的 lambda 表达式
	* -- 注意：在遍历 entrySet () 时，需要将 entrySet 中的元素强制转换为 Map.Entry 内部接口类型，才能调用 getKey () 和 getValue () 方法
	*/
	@Test
	public void test4() {
	HashMap hashMap = new HashMap();
	hashMap.put("许仙", "白娘子");
	hashMap.put("董永", "七仙女");
	hashMap.put("牛郎", "织女");
	hashMap.put("许仙", "小青"); //key 重复，value 覆盖

	// 添加、修改
	hashMap.put("猪八戒", "沙僧");
	hashMap.put("猪八戒", "唐僧"); //key 重复，value 覆盖
	System.out.println(hashMap); // 无序：{许仙 = 小青，董永 = 七仙女，猪八戒 = 唐僧，牛郎 = 织女}

	HashMap hashMap1 = new HashMap();
	hashMap1.put("孙悟空", "猪八戒");
	hashMap1.put("唐僧", "沙僧");
	hashMap.putAll(hashMap1);
	System.out.println(hashMap); // 无序：{许仙 = 小青，董永 = 七仙女，孙悟空 = 猪八戒，猪八戒 = 唐僧，牛郎 = 织女，唐僧 = 沙僧}

	// 删除
	hashMap.clear();
	System.out.println(hashMap); // {}

	hashMap.put("许仙", "白娘子");
	hashMap.put("董永", "七仙女");
	hashMap.put("牛郎", "织女");
	hashMap.put("许仙", "小青"); //key 重复，value 覆盖
	System.out.println(hashMap.remove("许仙")); // 返回被删除的 value：小青
	System.out.println(hashMap); // 无序：{董永 = 七仙女，牛郎 = 织女}

	// 查询
	System.out.println(hashMap.get("董永")); // 七仙女
	System.out.println(hashMap.containsKey("董永")); //true
	System.out.println(hashMap.containsValue("沙僧")); //false
	System.out.println(hashMap.isEmpty()); //false
	System.out.println(hashMap.size()); //2

	// 遍历：（1）增强 for 循环
	Set keySet = hashMap.keySet(); // 返回所有 key 构成的 Set 集合
	for (Object key : keySet) {
	System.out.println(key); // 无序：董永牛郎
	}

	Collection values = hashMap.values(); // 返回所有 value 构成的 Collection 集合
	for (Object value : values) {
	System.out.println(value); // 无序：七仙女织女
	}

	Set entrySet = hashMap.entrySet(); // 返回所有 key-value 对构成的 Set 集合
	for (Object mapping : entrySet) {
	Map.Entry entry = (Map.Entry) mapping; // 向下转型：Object -> Map.Entry
	System.out.println(entry.getKey() + "->" + entry.getValue()); // 无序：董永 -> 七仙女牛郎 -> 织女
	}

	// 遍历：（2）迭代器
	Iterator keyIterator = hashMap.keySet().iterator();
	while (keyIterator.hasNext()) {
	Object key = keyIterator.next();
	System.out.println(key); // 无序：董永牛郎
	}

	Iterator valueIterator = hashMap.values().iterator();
	while (valueIterator.hasNext()) {
	Object value = valueIterator.next();
	System.out.println(value); // 无序：七仙女织女
	}

	Iterator entryIterator = hashMap.entrySet().iterator();
	while (entryIterator.hasNext()) {
	Map.Entry entry = (Map.Entry) entryIterator.next(); // 强制向下转型：Object -> Map.Entry（Entry 是 Map 接口中的内部接口，在 Map 的各种实现类中都有实现，例如 HashMap 中的 Node 静态内部类实现了 Entry 接口）
	System.out.println(entry.getKey() + "->" + entry.getValue()); // 无序：董永 -> 七仙女牛郎 -> 织女。其中 getKey () 和 getValue () 方法都是 Map.Entry 接口中定义的抽象方法，因此在各种实现类中都有实现
	}

	// 遍历：（3）JDK8 中的 lambda 表达式
	hashMap.keySet().forEach(key -> System.out.println(key)); // 无序：董永牛郎
	hashMap.values().forEach(value -> System.out.println(value)); // 无序：七仙女织女
	hashMap.forEach((key, value) -> System.out.println(key + "->" + value)); // 无序：董永 -> 七仙女牛郎 -> 织女
	}

举例：

	@Test
	public void test1(){
	// 创建 map 对象
	HashMap map = new HashMap();

	// 添加元素到集合
	map.put("黄晓明", "杨颖");
	map.put("李晨", "李小璐");
	map.put("李晨", "范冰冰"); //key 重复，value 覆盖
	map.put("邓超", "孙俪");
	System.out.println(map);

	// 删除指定的 key-value
	System.out.println(map.remove("黄晓明")); // 返回被删除的 value
	System.out.println(map);

	// 查询指定 key 对应的 value
	System.out.println(map.get("邓超"));
	System.out.println(map.get("黄晓明")); // 不存在则返回 null
	}

举例：

	@Test
	public void test2() {
	HashMap map = new HashMap();
	map.put("许仙", "白娘子");
	map.put("董永", "七仙女");
	map.put("牛郎", "织女");
	map.put("许仙", "小青"); //key 重复，value 覆盖

	System.out.println("所有的key:");
	Set keySet = map.keySet(); // 返回所有 key 构成的 Set 集合
	for (Object key : keySet) {
	System.out.println(key);
	}

	System.out.println("所有的value:");
	Collection values = map.values(); // 返回所有 value 构成的 Collection 集合
	for (Object value : values) {
	System.out.println(value);
	}

	System.out.println("所有的映射关系:");
	Set entrySet = map.entrySet(); // 返回所有 key-value 对构成的 Set 集合
	for (Object mapping : entrySet) {
	//System.out.println(entry);
	Map.Entry entry = (Map.Entry) mapping;
	System.out.println(entry.getKey() + "->" + entry.getValue());
	}
	}

# 6.3 Map 的主要实现类：HashMap

# 6.3.1 HashMap 概述

HashMap 是 Map 接口 使用频率最高 的实现类。
HashMap 是线程不安全的。允许添加 null 键和 null 值。
存储数据采用的哈希表结构，底层使用 一维数组 + 单向链表 + 红黑树 进行 key-value 数据的存储。与 HashSet 一样，元素的存取顺序不能保证一致。
HashMap 判断两个key相等的标准 是：
- 两个 key 的 hashCode 值相等
- 两个 key 的 equals () 返回 true
HashMap 判断两个value相等的标准 是：两个 value 通过 equals () 方法返回 true。

# 6.3.2 练习

** 练习 1：** 添加你喜欢的歌手以及你喜欢他唱过的歌曲

例如：

	public class SingerTest {
	public static void main(String[] args) {
	HashMap singerMap = new HashMap();

	// 声明一组 key-value
	String key1 = "周杰伦";
	ArrayList songList1 = new ArrayList();
	songList1.add("告白气球");
	songList1.add("七里香");
	songList1.add("稻香");
	singerMap.put(key1, songList1); // 添加到 map 中

	// 声明一组 key-value
	String key2 = "林俊杰";
	ArrayList songList2 = new ArrayList();
	songList2.add("一千年以后");
	songList2.add("江南");
	songList2.add("曹操");
	singerMap.put(key2, songList2); // 添加到 map 中

	// 遍历输出：利用迭代器
	Iterator iterator = singerMap.entrySet().iterator();
	while (iterator.hasNext()) {
	Map.Entry entry = (Map.Entry) iterator.next(); // 需要先强转为 Map.Entry，否则无法调用 getKey () 和 getValue ()
	System.out.println("歌手：" + entry.getKey());
	System.out.println("歌曲有：" + entry.getValue());
	}
	}
	}

	// 方式 2：改为 HashSet 实现
	public class SingerTest2 {
	@Test
	public void test1() {

	Singer singer1 = new Singer("周杰伦");
	Singer singer2 = new Singer("陈奕迅");

	Song song1 = new Song("双节棍");
	Song song2 = new Song("本草纲目");
	Song song3 = new Song("夜曲");
	Song song4 = new Song("浮夸");
	Song song5 = new Song("十年");
	Song song6 = new Song("孤勇者");

	HashSet h1 = new HashSet();// 放歌手一的歌曲
	h1.add(song1);
	h1.add(song2);
	h1.add(song3);

	HashSet h2 = new HashSet();// 放歌手二的歌曲
	h2.add(song4);
	h2.add(song5);
	h2.add(song6);

	HashMap hashMap = new HashMap();// 放歌手和他对应的歌曲
	hashMap.put(singer1, h1);
	hashMap.put(singer2, h2);

	for (Object obj : hashMap.keySet()) {
	System.out.println(obj + "=" + hashMap.get(obj));
	}

	}
	}

	// 歌曲
	public class Song implements Comparable{
	private String songName;// 歌名

	public Song() {
	super();
	}

	public Song(String songName) {
	super();
	this.songName = songName;
	}

	public String getSongName() {
	return songName;
	}

	public void setSongName(String songName) {
	this.songName = songName;
	}

	@Override
	public String toString() {
	return "《" + songName + "》";
	}

	@Override
	public int compareTo(Object o) {
	if(o == this){
	return 0;
	}
	if(o instanceof Song){
	Song song = (Song)o;
	return songName.compareTo(song.getSongName());
	}
	return 0;
	}


	}
	// 歌手
	public class Singer implements Comparable{
	private String name;
	private Song song;

	public Singer() {
	super();
	}

	public Singer(String name) {
	super();
	this.name = name;

	}

	public String getName() {
	return name;
	}

	public void setName(String name) {
	this.name = name;
	}

	public Song getSong() {
	return song;
	}

	public void setSong(Song song) {
	this.song = song;
	}

	@Override
	public String toString() {
	return name;
	}

	@Override
	public int compareTo(Object o) {
	if(o == this){
	return 0;
	}
	if(o instanceof Singer){
	Singer singer = (Singer)o;
	return name.compareTo(singer.getName());
	}
	return 0;
	}
	}

练习 2：二级联动

将省份和城市的名称保存在集合中，当用户选择省份以后，二级联动，显示对应省份的地级市供用户选择。

效果演示：

	class CityMap {
	// 静态变量，用于存储省份和城市的对应关系
	public static Map model = new HashMap();

	// 静态代码块，在类加载时执行，只执行一次，用于初始化静态变量
	static {
	model.put("北京", new String[]{"北京"});
	model.put("辽宁", new String[]{"沈阳", "大连", "鞍山", "抚顺", "本溪", "丹东", "锦州"});
	model.put("吉林", new String[]{"长春", "吉林", "四平", "辽源", "通化", "白山", "松原", "白城", "延边"});
	model.put("河北", new String[]{"石家庄", "唐山", "秦皇岛", "邯郸", "邢台", "保定", "张家口", "承德", "沧州", "廊坊", "衡水"});
	model.put("河南", new String[]{"郑州", "开封", "洛阳", "平顶山", "安阳", "鹤壁", "新乡"});
	}
	}

	public class CityTest {
	public static void main(String[] args) {
	// 1. 获取 Map，遍历所有省份
	Map map = CityMap.model;
	Iterator keyIterator = map.keySet().iterator();
	while (keyIterator.hasNext()) {
	System.out.print(keyIterator.next() + "\t\t");
	}
	// 2. 从键盘输入省份，如果输入的省份不存在，则提示重新输入，否则输出该省份的所有城市
	Scanner sc = new Scanner(System.in);
	String[] cities;
	while (true) {
	System.out.println("\n请选择你所在的省份：");
	String province = sc.next();
	cities = (String[]) map.get(province); // 返回的 value 是 Object 类型，需要强转为 String []
	if (cities == null \|\| cities.length == 0) {
	System.out.println("输入的省份不存在，请重新输入！");
	} else {
	break; // 输入正确，跳出循环
	}
	}
	for (String city : cities) {
	System.out.print(city + "\t\t");
	}
	// 3. 从键盘输入城市，如果输入的城市存在于该省份的城市列表中，则输出 “信息登记完毕”，否则提示重新输入
	l: // 标签，用于跳出多重循环
	while (true) {
	System.out.println("\n请选择你所在的城市：");
	String city = sc.next();
	// 遍历城市列表，判断输入的城市是否存在
	boolean flag = false;
	for (String c : cities) {
	if (c.equals(city)) {
	System.out.println("信息登记完毕！");
	flag = true;
	break l; // 跳出多重循环
	}
	}
	if (!flag) {
	System.out.println("输入的城市不存在，请重新输入！");
	}
	}
	sc.close();
	}
	}

练习 3：WordCount 统计

需求：统计字符串中每个字符出现的次数

String str = "aaaabbbcccccccccc";

提示：

char [] arr = str.toCharArray (); // 将字符串转换成字符数组

HashMap hm = new HashMap (); // 创建双列集合存储键和值，键放字符，值放次数

	/**
	*
	* @author 尚硅谷 - 宋红康
	* @date 2022 年 5 月 7 日上午 12:26:59
	*
	*/
	public class WordCountTest {
	public static void main(String[] args) {
	String str = "aaaabbbcccccccccc";
	char[] arr = str.toCharArray(); // 将字符串转换成字符数组
	HashMap map = new HashMap(); // 创建双列集合存储键和值

	for (char c : arr) { // 遍历字符数组
	if (!map.containsKey(c)) { // 如果不包含这个键
	map.put(c, 1); // 就将键和值为 1 添加
	} else { // 如果包含这个键
	map.put(c, (int)map.get(c) + 1); // 就将键和值再加 1 添加进来
	}

	}

	for (Object key : map.keySet()) { // 遍历双列集合
	System.out.println(key + "=" + map.get(key));
	}

	}
	}

# 6.4 Map 实现类之二：LinkedHashMap

LinkedHashMap 是 HashMap 的子类
存储数据采用的哈希表结构 + 链表结构，在 HashMap 存储结构的基础上，使用了一对 双向链表 来 记录添加元素的先后顺序 ，可以保证遍历元素时，与添加的顺序一致。
通过哈希表结构可以保证键的唯一、不重复，需要键所在类重写 hashCode () 方法、equals () 方法。

	public class TestLinkedHashMap {
	public static void main(String[] args) {
	LinkedHashMap map = new LinkedHashMap();
	map.put("王五", 13000.0);
	map.put("张三", 10000.0);
	//key 相同，新的 value 会覆盖原来的 value
	// 因为 String 重写了 hashCode 和 equals 方法
	map.put("张三", 12000.0);
	map.put("李四", 14000.0);
	//HashMap 支持 key 和 value 为 null 值
	String name = null;
	Double salary = null;
	map.put(name, salary);

	Set entrySet = map.entrySet();
	for (Object obj : entrySet) {
	Map.Entry entry = (Map.Entry)obj;
	System.out.println(entry);
	}
	}
	}

# 6.5 Map 实现类之三：TreeMap

TreeMap 存储 key-value 对时，需要根据 key-value 对进行排序。TreeMap 可以保证所有的 key-value 对处于 有序状态 。
TreeSet 底层使用 红黑树 结构存储数据
TreeMap 的 Key 的排序：
- 自然排序 ：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException
- 定制排序 ：创建 TreeMap 时，构造器传入一个 Comparator 对象，该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable 接口
TreeMap 判断 两个key相等的标准 ：两个 key 通过 compareTo () 方法或者 compare () 方法返回 0。

	/**
	* ClassName: TreeMapTest
	* Package: map.treemap
	* Description:
	* - TreeMap 是基于红黑树实现的 Map 接口，可以按照 key 的指定属性进行排序；
	* - 排序方式有两种：①自然排序（key 所在类实现了 Comparable 接口）；②定制排序（在创建 TreeMap 时传入 Comparator 对象）；
	* - TreeMap 中的 key 必须是同一个类的对象，否则会抛出 ClassCastException 异常；
	* - TreeMap 中的 key 不能为 null，但 value 可以是 null；
	* - 在实现了 key 的排序后，containsKey () 是通过 compareTo () 或 compare () 方法是否返回 0 来判断 key 是否存在的；
	*
	* @Author 贺健翔
	* @Create 2023/4/3 15:15
	* @Version 1.0
	*/
	public class TreeMapTest {
	/**
	* 自然排序：key 为 String 类型，其实现了 Comparable 接口，并重写了 compareTo () 方法，按照字符串的自然顺序进行排序；
	*/
	@Test
	public void test1() {
	TreeMap map = new TreeMap();
	map.put("AA", 123);
	map.put("CC", 456);
	map.put("BB", 789);
	System.out.println(map); // 按照 key 的自然顺序进行排序:{AA=123, BB=789, CC=456}
	}

	/**
	* 自然排序：key 为自定义类 User，其实现了 Comparable 接口，并重写了 compareTo () 方法，按照年龄从小到大排序，年龄相同，按照姓名从大到小排序；
	*/
	@Test
	public void test2() {
	TreeMap map = new TreeMap();
	map.put(new User("Tom", 12), 123);
	map.put(new User("Jerry", 32), 456);
	map.put(new User("Mike", 32), 789);
	map.put(new User("Jack", 2), 101);
	System.out.println(map); // 按照 User 的指定属性排序:{User {name='Jack', age=2}=101, User {name='Tom', age=12}=123, User {name='Mike', age=32}=789, User {name='Jerry', age=32}=456}
	}

	/**
	* 定制排序：key 为自定义类 User。需要创建 Comparator 接口的实现类实例，重写 compare () 方法，按照年龄从小到大排序，年龄相同，按照姓名从大到小排序，并将该实例传入 TreeMap 的构造器中；
	*/
	@Test
	public void test3() {
	Comparator comparator = new Comparator() {
	@Override
	public int compare(Object o1, Object o2) {
	if (o1 instanceof User && o2 instanceof User) {
	User user1 = (User) o1;
	User user2 = (User) o2;
	if (user1.getAge() - user2.getAge() != 0) {
	return user1.getAge() - user2.getAge();
	} else {
	return -user1.getName().compareTo(user2.getName());
	}
	} else {
	throw new RuntimeException("输入的类型不匹配");
	}
	}
	};
	TreeMap map = new TreeMap(comparator);
	map.put(new User("Tom", 12), 123);
	map.put(new User("Jerry", 32), 456);
	map.put(new User("Mike", 32), 789);
	map.put(new User("Jack", 2), 101);
	System.out.println(map); // 按照 User 的指定属性排序:{User {name='Jack', age=2}=101, User {name='Tom', age=12}=123, User {name='Mike', age=32}=789, User {name='Jerry', age=32}=456}
	}

	/**
	* 如果实现了 TreeMap 的 key 排序，在判断 containsKey () 时，只要 compareTo () 或 compare () 返回 0，就认为 key 相同；
	* 例如，下面实现定制排序，按照年龄从小到大排序。
	* 但是，如果输入的 key 的年龄与 TreeMap 中的 key 的年龄相同，但是姓名不同，那么 containsKey () 方法会认为 key 相同，返回 true；
	*/
	@Test
	public void test4() {
	Comparator comparator = new Comparator() {
	@Override
	public int compare(Object o1, Object o2) {
	if (o1 instanceof User && o2 instanceof User) {
	User user1 = (User) o1;
	User user2 = (User) o2;
	return user1.getAge() - user2.getAge();
	}
	throw new RuntimeException("输入的类型不匹配");
	}
	};
	TreeMap map = new TreeMap(comparator);
	map.put(new User("Tom", 12), 123);
	map.put(new User("Jerry", 32), 456);
	map.put(new User("Mike", 32), 789);
	map.put(new User("Jack", 2), 101);
	System.out.println(map.containsKey(new User("asdsada", 12))); // true
	}
	}

	class User implements Comparable {
	private String name;
	private int age;

	public User(String name, int age) {
	this.name = name;
	this.age = age;
	}

	public String getName() {
	return name;
	}

	public void setName(String name) {
	this.name = name;
	}

	public int getAge() {
	return age;
	}

	public void setAge(int age) {
	this.age = age;
	}

	/**
	* 按照年龄从小到大排序，年龄相同，按照姓名从大到小排序
	*
	* @param o
	* @return
	*/
	@Override
	public int compareTo(Object o) {
	if (this == o) {
	return 0;
	}
	if (o instanceof User) {
	User user = (User) o;
	if (this.age - user.age != 0) {
	return this.age - user.age;
	} else {
	return -this.name.compareTo(user.name);
	}
	} else {
	throw new RuntimeException("输入的类型不匹配");
	}
	}

	@Override
	public String toString() {
	return "User{" +
	"name='" + name + '\'' +
	", age=" + age +
	'}';
	}
	}

# 6.6 Map 实现类之四：Hashtable

Hashtable 是 Map 接口的 古老实现类 ，JDK1.0 就提供了。不同于 HashMap，Hashtable 是线程安全的。
Hashtable 实现原理和 HashMap 相同，功能相同。底层都使用哈希表结构（数组 + 单向链表），查询速度快。
与 HashMap 一样，Hashtable 也不能保证其中 Key-Value 对的顺序
Hashtable判断两个 key 相等、两个 value 相等的标准，与 HashMap 一致。
与 HashMap 不同，Hashtable 不允许使用 null 作为 key 或 value。

面试题：Hashtable 和 HashMap 的区别

HashMap:底层是一个哈希表（jdk7:数组+链表;jdk8:数组+链表+红黑树）,是一个线程不安全的集合,执行效率高
Hashtable:底层也是一个哈希表（数组+链表）,是一个线程安全的集合,执行效率低

HashMap集合:可以存储null的键、null的值
Hashtable集合,不能存储null的键、null的值

Hashtable和Vector集合一样,在jdk1.2版本之后被更先进的集合(HashMap,ArrayList)取代了。所以HashMap是Map的主要实现类，Hashtable是Map的古老实现类。

Hashtable的子类Properties（配置文件）依然活跃在历史舞台
Properties集合是一个唯一和IO流相结合的集合

# 6.7 Map 实现类之五：Properties

Properties 类是 Hashtable 的子类，该对象用于处理属性配置文件
由于属性文件里的 key、value 都是字符串类型，所以 Properties 中要求 key 和 value 都是字符串类型
存取数据时，建议使用setProperty(String key,String value) 方法和getProperty(String key) 方法

	@Test
	public void test01() {
	Properties properties = System.getProperties();
	String fileEncoding = properties.getProperty("file.encoding");// 当前源文件字符编码
	System.out.println("fileEncoding = " + fileEncoding);
	}
	@Test
	public void test02() {
	Properties properties = new Properties();
	properties.setProperty("user","songhk");
	properties.setProperty("password","123456");
	System.out.println(properties);
	}

	@Test
	public void test03() throws IOException {
	Properties pros = new Properties();
	pros.load(new FileInputStream("jdbc.properties"));
	String user = pros.getProperty("user");
	System.out.println(user);
	}

	/**
	* Properties 类的使用，主要用于读取配置文件
	* @throws IOException
	*/
	@Test
	public void test04() throws IOException {
	File file = new File("info.properties"); // 要提前创建好
	System.out.println(file.getAbsolutePath());

	FileInputStream fis = new FileInputStream(file); // 文件输入流（读取文件）

	Properties properties = new Properties(); // 属性类
	properties.load(fis); // 加载文件输入流

	// 读取文件中的内容
	String name = properties.getProperty("name");
	String pwd = properties.getProperty("password");
	System.out.println(name + "：" + pwd);
	}

# 7. Collections 工具类

Arrays 类提供了对数组的操作，Collections 类提供了对 Set、List 和 Map 等集合的操作。

Arrays 类：
sort ()：对数组进行排序。
binarySearch ()：使用二分查找算法在数组中查找指定元素。
fill ()：将数组的所有元素都赋为指定值。
asList ()：将数组转换为 List。
Collections 类：
sort ()：对 List 进行排序。
binarySearch ()：使用二分查找算法在 List 中查找指定元素。
reverse ()：反转 List 中元素的顺序。
shuffle ()：随机排列 List 中的元素。
fill ()：将 List 中的所有元素都赋为指定值。

面试题：区分 Collection 和 Collections。

Collection 是一个集合接口，用于存储 “单列数据”，分为 List 子接口和 Set 子接口
Collections 是一个集合工具类，提供了对 Set、List、Map 集合的操作

# 7.1 常用方法

Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法（均为 static 方法）：

# 7.1.1 排序操作

reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

# 7.1.2 查找

Object max(Collection)：根据元素的自然顺序，返回给定集合中的最右元素
Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最右元素
Object min(Collection)：根据元素的自然顺序，返回给定集合中的最左元素
Object min(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最左元素
int binarySearch(List list,T key) 在 List 集合中查找某个元素的下标，但是List 的元素必须是 T 或 T 的子类对象，而且必须是可比较大小的，即支持自然排序的。而且集合也事先必须是有序的，否则结果不确定。
int binarySearch(List list,T key,Comparator c) 在 List 集合中查找某个元素的下标，但是List 的元素必须是 T 或 T 的子类对象，而且集合也事先必须是按照 c 比较器规则进行排序过的，否则结果不确定。
int frequency(Collection c，Object o)：返回指定集合中指定元素的出现次数

# 7.1.3 复制、替换

void copy(List dest,List src)：将 src 中的内容复制到 dest 中

易报错 IndexOutOfBoundsException: Source does not fit in dest ，原因是src.size() > dest.size()

	@Test
	public void test1() {
	List src = Arrays.asList(1, 2, 3, 4, 5);

	// 错误的写法
	List dest1 = new ArrayList();
	// Collections.copy (dest1, src); // 报错：IndexOutOfBoundsException，因为 dest1.size () 为 0，而 src.size () 为 5

	// 正确的写法
	List dest2 = Arrays.asList(new Object[src.size()]); // 不能使用 new ArrayList ()，因为这样 dest2.size () 为 0
	Collections.copy(dest2, src);
	System.out.println(dest2); // [1, 2, 3, 4, 5]
	}

boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值
提供了多个unmodifiableXxx()方法，该方法返回指定 Xxx 的不可修改的视图。将集合变成只读。

# 7.1.4 添加

boolean addAll(Collection c,T... elements) 将所有指定元素添加到指定 collection 中。

# 7.1.5 同步

Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程安全的集合，从而可以解决多线程并发访问集合时的线程安全问题：

# 7.2 举例

	package com.atguigu.collections;

	import org.junit.Test;

	import java.text.Collator;
	import java.util.*;

	public class TestCollections {
	@Test
	public void test01(){
	/*
	public static <T> boolean addAll (Collection<? super T> c,T... elements)
	将所有指定元素添加到指定 collection 中。Collection 的集合的元素类型必须 >=T 类型
	*/
	Collection<Object> coll = new ArrayList<>();
	Collections.addAll(coll, "hello","java");
	Collections.addAll(coll, 1,2,3,4);

	Collection<String> coll2 = new ArrayList<>();
	Collections.addAll(coll2, "hello","java");
	//Collections.addAll (coll2, 1,2,3,4);//String 和 Integer 之间没有父子类关系
	}

	@Test
	public void test02(){
	/*
	* public static <T extends Object & Comparable<? super T>> T max (Collection<? extends T> coll)
	* 在 coll 集合中找出最大的元素，集合中的对象必须是 T 或 T 的子类对象，而且支持自然排序
	*
	* public static <T> T max (Collection<? extends T> coll,Comparator<? super T> comp)
	* 在 coll 集合中找出最大的元素，集合中的对象必须是 T 或 T 的子类对象，按照比较器 comp 找出最大者
	*
	*/
	List<Man> list = new ArrayList<>();
	list.add(new Man("张三",23));
	list.add(new Man("李四",24));
	list.add(new Man("王五",25));

	/*
	* Man max = Collections.max (list);// 要求 Man 实现 Comparable 接口，或者父类实现
	* System.out.println (max);
	*/

	Man max = Collections.max(list, new Comparator<Man>() {
	@Override
	public int compare(Man o1, Man o2) {
	return o2.getAge()-o2.getAge();
	}
	});
	System.out.println(max);
	}

	@Test
	public void test03(){
	/*
	* public static void reverse (List<?> list)
	* 反转指定列表 List 中元素的顺序。
	*/
	List<String> list = new ArrayList<>();
	Collections.addAll(list,"hello","java","world");
	System.out.println(list);

	Collections.reverse(list);
	System.out.println(list);
	}
	@Test
	public void test04(){
	/*
	* public static void shuffle (List<?> list)
	* List 集合元素进行随机排序，类似洗牌，打乱顺序
	*/
	List<String> list = new ArrayList<>();
	Collections.addAll(list,"hello","java","world");

	Collections.shuffle(list);
	System.out.println(list);
	}
	@Test
	public void test05() {
	/*
	* public static <T extends Comparable<? super T>> void sort (List<T> list)
	* 根据元素的自然顺序对指定 List 集合元素按升序排序
	*
	* public static <T> void sort (List<T> list,Comparator<? super T> c)
	* 根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
	*/
	List<Man> list = new ArrayList<>();
	list.add(new Man("张三",23));
	list.add(new Man("李四",24));
	list.add(new Man("王五",25));

	Collections.sort(list);
	System.out.println(list);

	Collections.sort(list, new Comparator<Man>() {
	@Override
	public int compare(Man o1, Man o2) {
	return Collator.getInstance(Locale.CHINA).compare(o1.getName(),o2.getName());
	}
	});
	System.out.println(list);
	}
	@Test
	public void test06(){
	/*
	* public static void swap (List<?> list,int i,int j)
	* 将指定 list 集合中的 i 处元素和 j 处元素进行交换
	*/
	List<String> list = new ArrayList<>();
	Collections.addAll(list,"hello","java","world");

	Collections.swap(list,0,2);
	System.out.println(list);
	}
	@Test
	public void test07(){
	/*
	* public static int frequency (Collection<?> c,Object o)
	* 返回指定集合中指定元素的出现次数
	*/
	List<String> list = new ArrayList<>();
	Collections.addAll(list,"hello","java","world","hello","hello");
	int count = Collections.frequency(list, "hello");
	System.out.println("count = " + count);
	}
	@Test
	public void test08(){
	/*
	* public static <T> void copy (List<? super T> dest,List<? extends T> src)
	* 将 src 中的内容复制到 dest 中
	*/
	List<Integer> list = new ArrayList<>();
	for(int i=1; i<=5; i++){//1-5
	list.add(i);
	}

	List<Integer> list2 = new ArrayList<>();
	for(int i=11; i<=13; i++){//11-13
	list2.add(i);
	}

	Collections.copy(list, list2);
	System.out.println(list);

	List<Integer> list3 = new ArrayList<>();
	for(int i=11; i<=20; i++){//11-20
	list3.add(i);
	}
	//java.lang.IndexOutOfBoundsException: Source does not fit in dest
	//Collections.copy(list, list3);
	//System.out.println(list);

	}

	@Test
	public void test09(){
	/*
	* public static <T> boolean replaceAll (List<T> list，T oldVal，T newVal)
	* 使用新值替换 List 对象的所有旧值
	*/
	List<String> list = new ArrayList<>();
	Collections.addAll(list,"hello","java","world","hello","hello");

	Collections.replaceAll(list, "hello","song");
	System.out.println(list);
	}
	}

# 7.3 练习