集合 - 《Java SE 笔记》

一、集合
- 1.1 集合的理解和好处
- 1.2 集合的框架体系（重要，记住）
二、Collection 接口
三、List 接口
四、Set 接口
五、Map 接口
六、总结：开发中如何选择集合实现类（记住）
七、Collections 工具类
八、本章作业

一、集合

1.1 集合的理解和好处

前面我们保存多个数据使用的是数组，那么数组有不足的地方，我们分析一下：

长度开始时必须指定，而且一旦指定，不能更改
保存的必须为同一类型的元素
使用数组进行增加元素时比较麻烦

集合：

可以动态保存任意多个对象，使用比较方便
提供一系列方便的操作对象的方法：add、remove、set、get 等
使用集合添加，删除新元素更加方便简洁

1.2 集合的框架体系（重要，记住）

Java的集合类很多，主要分为两大类：

解读：

集合主要是两组（单列集合、双列集合）
Collection 接口有两个重要的子接口 List Set，它们的实现子类都是单列集合
Map 接口的实现子类是双列集合，存放 Key-Value

二、Collection 接口

2.1 Collection 接口实现类的特点

Collection 实现子类可以存放多个元素，每个元素可以是 Object
有些 Collection 的实现类，可以存放重复的元素，有些不可以
有些 Collection 的实现类，有些是有序的（List），有些不是有序（Set）
Collection 接口没有直接的实现子类，是通过它的子接口 Set 和 List 来实现的

2.2 Collection 接口常用方法

method	功能
add	添加单个元素
remove	删除指定元素
contains	查找元素是否存在
size	获取元素个数
isEmpty	判断是否为空
clear	清空
addAll	添加多个元素
containsAll	查找多个元素是否都存在
removeAll	删除多个元素

2.3 Collection 接口遍历元素方式1 - 使用 Iterator（迭代器）

基本介绍

Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素。
所有实现了 Collection 接口的集合都有一个 iterator() 方法，用于返回一个实现了 Iterator 接口的对象，即可以返回一个迭代器。
Iterator 结构图
Iterator 仅用于遍历集合，Iterator 本身并不存放对象。

迭代器的执行原理
Iterator iterator = coll.iterator(); //得到一个集合的迭代器
//hasNext()：判断是否还有下一个元素
while( iterator.hasNext() ) {
//next()：①指针下移 ②将下移以后集合位置上的元素返回
System.out.println(iterator.next());
}
集合 - 图3

Iterator 接口的方法

method	功能
hasNext()	判断是否还有下一个元素
next()	①指针下移 ②将下移以后集合位置上的元素返回
remove()	将迭代器返回的元素删除

注意：在调用 iterator.next() 方法前必须要调用 iterator.hasNext() 进行检测，如果不调用，且下一条记录无效，直接调用 next() 会抛出 NoSuchElemenException 异常。

public static void main(String[] args) {
        Collection col = new ArrayList();
        col.add(new Book("三国演义","罗贯中",179.8));
        col.add(new Book("红楼梦","曹雪芹",189.8));
        col.add(new Book("西游记","吴承恩",199.8));
        System.out.println("col=" + col);
        //遍历输出
        //1. 先得到 col 对应的迭代器
        Iterator iterator = col.iterator();
        //2. 使用 while 循环遍历 (可使用快捷键快速生成: itit)
        //显示所有快捷键的快捷提示键 CTRL + J
        while (iterator.hasNext()) { //判断是否还有数据
            //返回下一个元素，类型用 Object 接收
            Object obj = iterator.next();
            System.out.println("obj=" + obj);
        }
        //3. 当退出while循环后，这时 iterator迭代器，它指向最后的元素
        try {
            iterator.next();  //再取，这时会报错
        } catch (Exception e) {
            System.out.println("NoSuchElementException: " + e.getMessage());
        }
        //4. 如果希望再次遍历，需要重置迭代器
        iterator = col.iterator();
        System.out.println("----第二次遍历----");
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);
        }
    }

2.4 Collection 接口遍历对象方式2 - for循环增强

增强 for 循环，可以代替 iterator 迭代器，特点：增强 for 就是简化版的 iterator，本质也一样。只能用于遍历集合或数组。

基本语法
for (元素类型元素名 : 集合名或数组名) {
访问元素
}

public static void main(String[] args) {
        Collection col = new ArrayList();
        col.add(new Book("三国演义","罗贯中",179.8));
        col.add(new Book("红楼梦","曹雪芹",189.8));
        col.add(new Book("西游记","吴承恩",199.8));
        System.out.println("col=" + col);
        //使用增强 for 循环遍历集合
        for (Object book : col) {
            System.out.println("book=" + book);
        }
        //增强 for 也可以在数组使用
        int[] nums = {1,5,-1,6,10,8};
        for (int i : nums) {
            System.out.println("i=" + i);
        }
    }

解读：

使用增强 for，遍历 Collection 集合
增强 for，底层仍然是迭代器
增强 for，可以理解成简化版本的迭代器遍历
快捷键：I

2.5 小练习

请编写程序

创建 3个 Dog {name, age} 对象，放入到 ArrayList 中，赋给 List 引用
用迭代器和增强 for 循环两种方式来遍历
重写 Dog 的 toString 方法，输出 name 和 age

三、List 接口

3.1 List 接口基本介绍

List 接口是 Collection 接口的子接口

List 集合类中元素有序（即添加顺序和取出顺序一致）、且可重复
List 集合中每个元素都有其对应的顺序索引，即支持索引。
List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
JDK API 中 List 接口的实现类有：

常用的有：ArrayList、LinkedList 和 Vector

3.2 List 接口的常用方法

List 集合里添加了一些根据索引来操作集合元素的方法

void add(int index, Object ele)：在 index 位置插入 ele 元素
boolean addAll(int index, Collection eles)：从 index 位置开始将 eles 中的所有元素添加进来
Object get(int index)：获取指定 index 位置的元素
int indexOf(Object obj)：返回 obj 在集合中首次出现的位置
int lastIndexOf(Object obj)：返回 obj 在集合中最后一次出现的位置
Object remove(int index)：移除指定 index 位置的元素，并返回此元素
Object set(int index, Object ele)：设置指定 index 位置的元素为 ele，相当于替换

List subList(int fromIndex, int toIndex)：返回从 fromIndex 位置到 toIndex-1 位置的子集合

@SuppressWarnings({"all"})
 public static void main(String[] args) {
     List list = new ArrayList();
     list.add("张三丰");
     list.add("贾宝玉");
     //void add(int index, Object ele)：在 index 位置插入 ele 元素
     list.add(1,"刘备");
     System.out.println("list=" + list);
     //boolean addAll(int index, Collection eles)：从 index 位置开始 将 eles 中的所有元素添加进来
     List list2 = new ArrayList();
     list2.add("tom");
     list2.add("jerry");
     list.addAll(1,list2);
     System.out.println("list=" + list);
     //Object get(int index)：获取指定 index 位置的元素
     System.out.println(list.get(3));
     //int indexOf(Object obj)：返回 obj 在集合中首次出现的位置
     list.add("tom");
     System.out.println(list.indexOf("tom"));
     //int lastIndexOf(Object obj)：返回 obj 在集合中最后一次出现的位置
     System.out.println(list.lastIndexOf("tom"));
     //Object remove(int index)：移除指定 index 位置的元素，并返回 此元素
     System.out.println("移除的元素：" + list.remove(4) + "\n集合剩余元素：" + list);
     //Object set(int index, Object ele)：设置指定 index 位置的元素为 ele，相当于替换
     list.set(4,"林黛玉");
     System.out.println("list = " + list);
     //List subList(int fromIndex, int toIndex)：返回从 fromIndex 位置 到 toIndex-1 位置 的子集合
     List list3 = list.subList(1,3);
     System.out.println("list3 = " + list3);
 }

3.3 List 的三种遍历方式 [ArrayList, LinkedList, Vector]

方式一：使用 iterator
Iterator iter = col.iterator();
while(iter.hasNext()){
Object o = iter.next();
}
方式二：使用增强 for
for(Object o : col) {
System.out.println(o);
}

方式三：使用普通 for
for(int i = 0; i < list.size(); i++) {
Object object = list.get(i);
System.out.println(object);
}

@SuppressWarnings({"all"})
 public static void main(String[] args) {
     //List 接口的实现子类 Vector LinkedList
//        List list = new ArrayList();
     List list = new Vector();
//        List list = new LinkedList();
     list.add("jack");
     list.add("tom");
     list.add("鱼香肉丝");
     list.add("北京烤鸭");
     //遍历
     System.out.println("---迭代器---");
     Iterator iterator = list.iterator();
     while (iterator.hasNext()) {
         Object next = iterator.next();
         System.out.println(next);
     }
     System.out.println("---增强for---");
     for (Object o : list) {
         System.out.println(o);
     }
     System.out.println("---普通for---");
     for (int i = 0; i < list.size(); i++) {
         System.out.println(list.get(i));
     }
 }

3.4 ArrayList 的注意事项

permits all elements, including null, ArrayList 可以加入 null，并且多个
ArrayList 是由数组来实现数据存储的
ArrayList 基本等同于 Vector，除了 ArrayList 是线程不安全的（执行效率高）
所以在多线程情况下，不建议使用 ArrayList

3.5 ArrayList 的底层操作机制源码分析（重点、难点）

ArrayList 中维护了一个 Object 类型的数组 elementDate
transient Object[] elementDate; // transient 短暂的，表示该属性不会被序列化
当创建ArrayList对象时，如果使用的是无参构造器，则初始 elementDate 容量为0，第1次添加，则扩容elementDate 为10，如果需要再次扩容，则扩容 elementDate为1.5倍。
如果使用的是指定大小的构造器，则初始 elementDate 容量为指定大小，如果需要扩容，则直接扩容为 elementDate 的1.5倍。 ```java package com.hspedu.collection.list;

import java.util.ArrayList;

/**

@author HarborGao

@version 1.0 */ public class ArrayListSource { @SuppressWarnings({“all”}) public static void main(String[] args) {

 //源码解读
 //使用无参构造器创建ArrayList对象
 /**
  * 创建了一个空的elementData数组 Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  *   public ArrayList() {
  *      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  *   }
  */
 ArrayList list = new ArrayList();
 //使用有参(int)构造器创建ArrayList对象
 //ArrayList list = new ArrayList(8);
 //使用 for 给list 集合添加1-10数据
 /**
  * 执行 list.add
  * (1) 先确定是否要扩容
  * (2)然后执行添加过程
  *    public boolean add(E e) {
  *       ensureCapacityInternal(size + 1);  // Increments modCount!!
  *       elementData[size++] = e;
  *       return true;
  *    }
  *
  * 确定 minCapacity
  * (1) 第一次扩容 为10
  * (2)
  *     private static int calculateCapacity(Object[] elementData, int minCapacity) {
  *         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  *             return Math.max(DEFAULT_CAPACITY, minCapacity);
  *         }
  *         return minCapacity;
  *     }
  *     private void ensureCapacityInternal(int minCapacity) {
  *         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  *     }
  *
  * modCount++ 记录当前集合被修改次数
  * 如果elementData的大小不够 就调用grow(minCapacity)扩容
  *     private void ensureExplicitCapacity(int minCapacity) {
  *         modCount++;
  *
  *         // overflow-conscious code
  *         if (minCapacity - elementData.length > 0)
  *             grow(minCapacity);
  *     }
  *
  * 扩容操作
  * 使用扩容机制来确定要扩容到多大
  * 第一次 newCapacity = 10
  * 后续再扩容 按照1.5倍扩容
  * 扩容使用的是 Arrays.copyOf()
  *     private void grow(int minCapacity) {
  *         // overflow-conscious code
  *         int oldCapacity = elementData.length;
  *         int newCapacity = oldCapacity + (oldCapacity >> 1);
  *         if (newCapacity - minCapacity < 0)
  *             newCapacity = minCapacity;
  *         if (newCapacity - MAX_ARRAY_SIZE > 0)
  *             newCapacity = hugeCapacity(minCapacity);
  *         // minCapacity is usually close to size, so this is a win:
  *         elementData = Arrays.copyOf(elementData, newCapacity);
  *     }
  */
 for (int i = 0; i <= 10; i++) {
     list.add(i);
 }
 //使用 for 给list 集合添加11-15数据
 for (int i = 11; i <= 15; i++) {
     list.add(i);
 }
 list.add(100);
 list.add(200);

} } ```

3.6 Vector 的基本介绍

Vector 类的定义说明
public class Vector
extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable { }
Vector底层也是一个对象数组，protected Object[] elementData;
Vector是线程同步的，即线程安全，Vector类的操作方法带有 synchronized
在开发中，需要线程同步安全时，考虑使用 Vector

3.7 Vector 和 ArrayList 的比较

	底层结构	版本	线程安全（同步）效率	扩容倍数
ArrayList	可变数组	jdk 1.2	不安全、效率高	如果是有参构造：1.5倍如果是无参： 1. 第一次 10 2. 之后都按1.5倍扩容
Vector	可变数组	jdk 1.0	安全、效率不高	如果是无参，默认 10，之后都按2倍扩容如果指定大小，则每次直接按照2倍扩容

package com.hspedu.collection_.list_;
import java.util.Vector;
/**
 * @author HarborGao
 * @version 1.0
 */
public class Vector01 {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        //无参构造器
        Vector vector = new Vector();
        for (int i = 0; i < 10; i++) {
            vector.add(i);
        }
        vector.add(100);
        System.out.println(vector);
    }
    /**
     * 源码解读：
     * 1. 创建对象 new Vector() 使用无参构造器  底层实现：
     *     public Vector() {
     *         this(10); //调用有参构造，传入默认容量大小 10
     *     }
     *     //补充：如果创建对象的时候指定容量，就直接调用有参构造器
     *     public Vector(int initialCapacity) {  //initialCapacity 指定容量
     *         this(initialCapacity, 0);  // 调用Vector(int initialCapacity, int capacityIncrement)构造器
     *     }
     *     public Vector(int initialCapacity, int capacityIncrement) {
     *         super();
     *         if (initialCapacity < 0)
     *             throw new IllegalArgumentException("Illegal Capacity: "+
     *                                                initialCapacity);
     *         this.elementData = new Object[initialCapacity];
     *         this.capacityIncrement = capacityIncrement; //将0传给capacityIncrement
     *     }
     * 2. 添加数据 vector.add(i);
     *     public synchronized boolean add(E e) {
     *         modCount++;
     *         ensureCapacityHelper(elementCount + 1);  //确定容量是否足够存下这一个数据
     *         elementData[elementCount++] = e;  //把当前数据存到 elementData[elementCount]
     *         return true;
     *     }
     *     private void ensureCapacityHelper(int minCapacity) {  //容量确定具体方法实现
     *         // overflow-conscious code
     *         if (minCapacity - elementData.length > 0)  //所需最小容量 - 当前集合容量 大于0说明当前集合容量不够，需要额外容量
     *             grow(minCapacity);  //容量不够就扩容
     *     }
     * 3. 集合容量不够，进行扩容操作
     *     private void grow(int minCapacity) {
     *         // overflow-conscious code
     *         int oldCapacity = elementData.length;
     *         //由于capacityIncrement = 0 所以newCapacity = oldCapacity + oldCapacity
     *         int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
     *         if (newCapacity - minCapacity < 0)
     *             newCapacity = minCapacity;
     *         if (newCapacity - MAX_ARRAY_SIZE > 0)
     *             newCapacity = hugeCapacity(minCapacity);
     *         elementData = Arrays.copyOf(elementData, newCapacity);
     *     }
     */
}

3.8 LinkedList 的全面说明

LinkedList 底层实现了双向链表和双端队列特点
可以添加任意元素（元素可以重复），包括null
线程不安全，没有实现同步

3.9 LinkedList 的底层操作机制

LinkedList 底层维护了一个双向链表
LinkedList 中维护了两个属性 first 和 last 分别指向首结点和尾结点
每个结点（Node对象），里面又维护了prev、next、item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个结点，最终实现双向链表
LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高

3.10 LinkedList 底层结构

LinkedList 增删改查案例

package com.hspedu.collection_.list_;
import java.util.LinkedList;
import java.util.ListIterator;
/**
 * @author HarborGao
 * @version 1.0
 */
public class LinkedListSource {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println("linkedList=" + linkedList);
        /**
         *  add结点 源码解读
         *  1. 创建对象 new LinkedList()
         *     public LinkedList() {}  //无参构造器
         *  2. 这时 linkedList的属性：first = null  last = null
         *  3. 执行 添加
         *     public boolean add(E e) {
         *         linkLast(e);
         *         return true;
         *     }
         *  4. 将新的结点，加入到双向链表的最后
         *     void linkLast(E e) {
         *         final Node<E> l = last;
         *         final Node<E> newNode = new Node<>(l, e, null);  // l相当于赋给prev指向上一个last,null相当于赋给next
         *         last = newNode;  //last指向新的末尾结点
         *         if (l == null)  //创建第一个结点时
         *             first = newNode;  //first 指向第一个结点
         *         else  //不是第一个结点
         *             l.next = newNode;  //旧的末尾结点的next指向新的末尾结点
         *         size++;
         *         modCount++;
         *     }
         */
        //演示结点的删除
        Object remove = linkedList.remove();//删除首结点,并返回其保存的数据
        System.out.println(remove);
        System.out.println("linkedList=" + linkedList);
        linkedList.remove(1); //删除指定结点,并返回其保存的数据
        /**
         * remove()结点源码解读
         * 1. remove() 相当于 removeFirst()
         *     public E remove() {
         *         return removeFirst();
         *     }
         * 2. 完成首结点的删除
         *     public E removeFirst() {
         *         final Node<E> f = first;  //标记首结点
         *         if (f == null)
         *             throw new NoSuchElementException();
         *         return unlinkFirst(f);  //调用首结点解除连接方法
         *     }
         *     private E unlinkFirst(Node<E> f) {
         *         // assert f == first && f != null;
         *         final E element = f.item;  //保存首结点保存的数据
         *         final Node<E> next = f.next;
         *         f.item = null;
         *         f.next = null; // help GC
         *         first = next;  //首结点指针后移，让后一个结点称为首结点
         *         if (next == null)  //判断首结点后面还有没有结点
         *             last = null;
         *         else
         *             next.prev = null;  //将新的首结点的 prev 不再指向旧的首结点,而指向 null
         *         size--;
         *         modCount++;
         *         return element;
         *     }
         *
         *  remove(int index)结点源码解读
         *  1. 调用 remove(int index)
         *     public E remove(int index) {
         *         checkElementIndex(index);  //判断要删除的结点是否存在
         *         return unlink(node(index));  //调用删除方法,完成后返回数据
         *     }
         *  2. 调用 nlink(node(index)) 完成删除,并返回被删除结点所保存的数据
         *     E unlink(Node<E> x) {
         *         // assert x != null;
         *         final E element = x.item;  //保存要删除结点所保存的数据
         *         final Node<E> next = x.next;  //找到要删除结点后面的那一个结点
         *         final Node<E> prev = x.prev;  //找到要删除结点前面的那一个结点
         *
         *         if (prev == null) {  //如果前面的那一个结点不存在
         *             first = next;  //first指向删除结点后面的那一个结点
         *         } else {
         *             prev.next = next;  //若存在，让其next指针指向它(被删除结点)后面的那一个结点
         *             x.prev = null;  //释放被删除结点的prev指针
         *         }
         *
         *         if (next == null) {  //如果后面的那一个结点不存在
         *             last = prev;  //last指向删除结点前面的那一个结点
         *         } else {
         *             next.prev = prev;  //若存在，让其prev指针指向它(被删除结点)前面的那一个结点
         *             x.next = null;  //释放被删除结点的next指针
         *         }
         *
         *         x.item = null;  //释放被删除结点所保存的数据
         *         size--;
         *         modCount++;
         *         return element;
         *     }
         */
        for (int i = 0; i < 6; i++) {
            linkedList.add(i);
        }
        linkedList.set(0,"韩顺平教育");  //修改指定索引位置的数据
        System.out.println("===增强for遍历===");
        for (Object obj : linkedList) {
            System.out.println(obj);
        }
        System.out.println("===迭代器遍历===");
        ListIterator listIterator = linkedList.listIterator();
        while (listIterator.hasNext()) {
            Object next =  listIterator.next();
            System.out.println(next);
        }
        System.out.println("===普通for遍历===");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
        Object object = linkedList.get(0);  //获取指定索引位置的数据
        System.out.println("object = " + object);
        System.out.println(linkedList.getFirst());  //获取首结点的数据
        System.out.println(linkedList.getLast());   //获取尾结点的数据
    }
}

3.11 ArrayList 和 LinkedList 的比较

	底层结构	增删的效率	改查的效率
ArrayList	可变数组	较低通过数组扩容	较高
Vector	双向链表	较高通过链表追加	较低

如何选择 ArrayList 和 LinkedList ：

如果我们改查的操作多，选择 ArrayList
如果我们增删的操作多，选择 LinkedList
一般来说，在程序中，80% - 90%都是查询，因此大多数情况下会选择 ArrayList
在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是 ArrayList，另一个模块是 LinkedList

四、Set 接口

4.1 Set 接口基本介绍

无序（添加和取出的顺序不一致），没有索引
不允许重复元素，所以最多包含一个 null
JDK API 中 Set 接口的实现类有：

4.2 Set 接口的常用方法

和 List 接口一样，Set 接口也是 Collection 的子接口，因此，常用方法和 Collection 接口一样。

4.3 Set 接口的遍历方式

同 Collection 的遍历方式一样，因为 Set接口是Collection接口的子接口

可以使用迭代器
增强 for 遍历
不能使用索引的方式来获取

4.4 HashSet的全面说明

HashSet 实现了 Set 接口
HashSet 实际上是 HashMap
public HashSet() {
map = new HashMap<>();
}
可以存放 null 值，但只能存一个
HashSet 不保证元素有序，取决于 hash 后，再确定索引的结果（即不保证存放元素的顺序和取出顺序一致）
不会有重复元素/对象
在执行 add() 方法后，会返回一个 boolean值，从而确定是否添加成功

4.5 HashSet 底层机制说明

分析 HashSet 底层是HashMap，HashMap 底层是（数组+链表+红黑树）

HashSet 底层是 HashMap
添加一个元素时，先得到 hash 值，再转成索引值
找到存储数据表 table，看这个索引位置是否已经存放的有元素
如果没有，直接加入
如果有，调用 equals() 比较，如果相同，就放弃添加，如果不相同，依次向后比较，直至都不相同，添加到最后
在 Java8中，如果一条链表的个数大于等于 TREEIFY_THRESHOLD(默认8)，并且table的大小大于等于 MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（转成红黑树）

集合 - 图7

package com.hspedu.set_;
import java.util.HashSet;
@SuppressWarnings({"all"})
public class HashSetSource {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");//到此位置，第1次add分析完毕.
        hashSet.add("php");//到此位置，第2次add分析完毕
        hashSet.add("java");
        System.out.println("set=" + hashSet);
        /*
        老韩对HashSet 的源码解读
        1. 执行 HashSet()
            public HashSet() {
                map = new HashMap<>();
            }
        2. 执行 add()
           public boolean add(E e) {//e = "java"
                return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();
           }
         3.执行 put() , 该方法会执行 hash(key) 得到key对应的hash值 算法h = key.hashCode()) ^ (h >>> 16)
             public V put(K key, V value) {//key = "java" value = PRESENT 共享
                return putVal(hash(key), key, value, false, true);
            }
         4.执行 putVal
         final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                Node<K,V>[] tab; Node<K,V> p; int n, i; //定义了辅助变量
                //table 就是 HashMap 的一个数组，类型是 Node[]
                //if 语句表示如果当前table 是null, 或者 大小=0
                //就是第一次扩容，到16个空间.
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;
                //(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
                //并把这个位置的对象，赋给 p
                //(2)判断p 是否为null
                //(2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)
                //(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = newNode(hash, key, value, null);
                else {
                    //一个开发技巧提示： 在需要局部变量(辅助变量)时候，在创建
                    Node<K,V> e; K k; //
                    //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
                    //并且满足 下面两个条件之一:
                    //(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象
                    //(2)  p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同
                    //就不能加入
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                    //再判断 p 是不是一颗红黑树,
                    //如果是一颗红黑树，就调用 putTreeVal , 来进行添加
                    else if (p instanceof TreeNode)
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else {//如果table对应索引位置，已经是一个链表, 就使用for循环比较
                          //(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
                          //    注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
                          //    , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
                          //    注意，在转成红黑树时，要进行判断, 判断条件
                          //    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
                          //            resize();
                          //    如果上面条件成立，先table扩容.
                          //    只有上面条件不成立时，才进行转成红黑树
                          //(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break
                        for (int binCount = 0; ; ++binCount) {
                            if ((e = p.next) == null) {
                                p.next = newNode(hash, key, value, null);
                                if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            p = e;
                        }
                    }
                    if (e != null) { // existing mapping for key
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;
                //size 就是我们每加入一个结点Node(k,v,h,next), size++
                if (++size > threshold)
                    resize();//扩容
                afterNodeInsertion(evict);
                return null;
            }
         */
    }
}

package com.hspedu.set_;
import java.util.HashSet;
import java.util.Objects;
@SuppressWarnings({"all"})
public class HashSetIncrement {
    public static void main(String[] args) {
        /*
        HashSet底层是HashMap, 第一次添加时，table 数组扩容到 16，
        临界值(threshold)是 16*加载因子(loadFactor)是0.75 = 12
        如果table 数组使用到了临界值 12,就会扩容到 16 * 2 = 32,
        新的临界值就是 32*0.75 = 24, 依次类推
         */
        HashSet hashSet = new HashSet();
//        for(int i = 1; i <= 100; i++) {
//            hashSet.add(i);//1,2,3,4,5...100
//        }
        /*
        在Java8中, 如果一条链表的元素个数到达 TREEIFY_THRESHOLD(默认是 8 )，
        并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树),
        否则仍然采用数组扩容机制
         */
//        for(int i = 1; i <= 12; i++) {
//            hashSet.add(new A(i));//
//        }
        /*
            当我们向hashset增加一个元素，-> Node -> 加入table , 就算是增加了一个size++
         */
        for(int i = 1; i <= 7; i++) {//在table的某一条链表上添加了 7个A对象
            hashSet.add(new A(i));//
        }
        for(int i = 1; i <= 7; i++) {//在table的另外一条链表上添加了 7个B对象
            hashSet.add(new B(i));//
        }
    }
}
class B {
    private int n;
    public B(int n) {
        this.n = n;
    }
    @Override
    public int hashCode() {
        return 200;
    }
}
class A {
    private int n;
    public A(int n) {
        this.n = n;
    }
    @Override
    public int hashCode() {
        return 100;
    }
}

练习：定义一个Employee类，该类包含：private 成员属性 name,age
要求: 创建 3 个 Employee 对象放入 HashSet 中
当 name 和 age 的值相同时，认为是相同员工，不能添加到 HashSet 集合中
知识点：IDEA alt+insert 可快速重写 equals() and hashCode()

package com.hspedu.collection_.set_;
import java.util.HashSet;
import java.util.Objects;
public class HashSetExercise {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add(new Employee("Tom",26));
        hashSet.add(new Employee("Tom",26));
        System.out.println(hashSet);
    }
}
class Employee {
    private String name;
    private int age;
    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age && Objects.equals(name, employee.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

4.6 LinkedHashSet 的全面说明

LinkedHashSet 是 HashSet 的子类
LinkedHashSet 底层是一个 LinkedHashMap，底层维护了一个(数组+单向链表) + 双向链表
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序（图），这使得元素看起来是以插入顺序保存的
LinkedHashSet 不允许添加重复元素

4.7 LinkedHashSet 底层机制说明

在 LinkedHashSet 中维护了一个 hash 表和双向链表（ LinkedHashSet 有head 和 tail）
每一个结点有 before 和 after 属性，这样可以形成双向链表
在添加一个元素时，先求 hash 值，再求索引，确定该元素在 table 的位置，然后将添加的元素加入到双向链表（如果已经存在，不添加【原则和 HashSet 一样】）
因此，我们遍历 LinkedHashSet 也能确保插入顺序和遍历顺序一致

底层源码解读：

LinkedHashSet 是 HashSet 的子类，实现了 Set 接口
public class LinkedHashSet extends HashSet implements Set, Cloneable, java.io.Serializable{ … }
LinkedHashSet 的构造器均继承父类
1. 无参构造器
  public LinkedHashSet() {
  super(16, .75f, true);
  }
2. 单参构造器
  public LinkedHashSet(int initialCapacity) {
  super(initialCapacity, .75f, true);
  }
3. 双参构造器
  public LinkedHashSet(int initialCapacity, float loadFactor) {
  super(initialCapacity, loadFactor, true);
  }

五、Map 接口

5.1 Map接口实现类的特点

这里讲的是 JDK8 的Map接口特点

Map 与 Collection 并列存在。用于保存具有映射关系的数据：Key-Value（双列元素）
Map 中的 key 和 value 可以是任何引用类型的数据，会封装到 HashMap$Node 对象中
Map 中的 key 不允许重复，当存入相同的 key，等价于替换
Map 中的 value 可以重复
Map 中的 key 可以为 null，value 也可以为 null，注意 key 只能有一个 null ，value可以有多个
常用 String类作为 Map 的 key（其他类型也可以）
key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value
Map 存放数据的 key-value 示意图，一对 k-v 是放在一个 Node 中的，又因为 Node 实现了 Entry 接口，所以有些书上也说一对 k-v 就是一个 Entry

集合 - 图8
说明：

key，value 实际是保存在Node结点中的
Node 实现了 Map.Entry 接口
同时为了方便调用，Map的子类会实现 KeySet，Values 内部类，EntrySet 集合，重写Map的keySet ，values，entrySet 方法
keySet 是 Set 类型的，KeySet 用于保存指向 Key 的指针
values 是 Collection 类型的，Values 用于保存指向 Value 的指针
entrySet 是 Set 类的，EntrySet 集合存放的元素的类型是Entry
Set> entrySet();

5.2 Map 接口的常用方法

Map 体系的继承图
集合 - 图9

Map 接口常用方法

put：添加
remove：根据键删除映射关系
get：根据键获取值
size：获取元素个数
isEmpty：判断个数是否为0
clear：清除
containsKey：查找键是否存在

5.3 Map 接口的遍历方法

第一种方案
通过 KeySet 取出所有的 key，再通过key取出对应的value

Set keyset = map.keySet();
System.out.println("----增强for----");
//(1) 增强for
for(Object key : keyset) {
 System.out.println(key + " - " + map.get(key));
}
System.out.println("\n----迭代器----");
//(2) 迭代器
Iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
 Object key =  iterator.next();
 System.out.println(key + " - " + map.get(key));
}

第二种方案
通过 Values 取出所有的 value

System.out.println("\n----增强for----");
Collection values = map.values();
for (Object value : values) {
 System.out.println(value);
}
System.out.println("\n----迭代器----");
Iterator iterator1 = values.iterator();
while (iterator1.hasNext()) {
 Object value =  iterator1.next();
 System.out.println(value);
}

第三种方案

通过 entrySet 遍历获取 k-v

Set kv = map.entrySet();
System.out.println("\n----EntrySet增强for----");
for (Object entry : kv) {
    Map.Entry m = (Map.Entry) entry;  //将entry转成 Map.Entry
    System.out.println(m.getKey() + " - " + m.getValue());
}
System.out.println("\n----EntrySet迭代器----");
Iterator iterator2 = kv.iterator();
while (iterator2.hasNext()) {
    Object entry =  iterator2.next();
    Map.Entry m = (Map.Entry) entry;
    System.out.println(m.getKey() + " - " + m.getValue());
}

知识点：

containsKey：查找键是否存在
keySet：获取所有的键
entrySet：获取所有的关系 k-v
values：获取所有的值

5.4 HashMap 的全面说明

Map 接口的常用实现类：HashMap、Hashtable、Properties
HashMap 是 Map 接口使用频率最高的实现类
HashMap 是以 key-value对的方式来存储数据(HashMap$Node类型)
key不能重复，但是值可以重复，允许使用 null键和 null值
如果添加相同的 key，则会覆盖原来的key-value，等同于修改(key不会替换，value会替换)
与HashSet 一样，不保证映射的顺序，因为底层是 hash表的方式来存储的（jdk8的 HashMap底层数组+链表+红黑树）
HashMap 没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized

5.5 HashMap 底层机制及源码剖析

扩容机制

HashMap 底层维护了 Node类型的数组table，默认为 null
当创建对象时，将加载因子(loadFactor) 初始化为 0.75
当添加 key-value 时，通过 key 的哈希值得到在 table的索引。然后判断该索引处是否有元素，如果没有元素直接添加；若有元素，继续判断该元素的key和准备加入的key是否相等，如果相等，则直接替换value；如果不相等，需要判断是树结构还是链表结构，然后依次向后比较，如果都不想等，加在最后。如果添加时发现容量不够，则需要扩容。
第1次添加，需要扩容table容量为16，临界值(threshold)为12（16*0.75）
以后再扩容，则需扩容table容量为原来的2倍(32,64…)，临界值为原来的2倍(24,48…)，以此类推
在 java8 中，如果一条链表的元素个数大于等于 TREEIFYTHRESHOLD(默认是8)，并且 table的大于等于 MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（转成红黑树） ```java package com.hspedu.map;

import java.util.HashMap;

@SuppressWarnings({“all”}) public class HashMapSource1 { public static void main(String[] args) { HashMap map = new HashMap(); map.put(“java”, 10);//ok map.put(“php”, 10);//ok map.put(“java”, 20);//替换value

    System.out.println("map=" + map);//
    /*老韩解读HashMap的源码+图解
    1. 执行构造器 new HashMap()
       初始化加载因子 loadfactor = 0.75
       HashMap$Node[] table = null
    2. 执行put 调用 hash方法，计算 key的 hash值 (h = key.hashCode()) ^ (h >>> 16)
        public V put(K key, V value) {//K = "java" value = 10
            return putVal(hash(key), key, value, false, true);
        }
     3. 执行 putVal
     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;//辅助变量
            //如果底层的table 数组为null, 或者 length =0 , 就扩容到16
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //取出hash值对应的table的索引位置的Node, 如果为null, 就直接把加入的k-v
            //, 创建成一个 Node ,加入该位置即可
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;//辅助变量
            // 如果table的索引位置的key的hash相同和新的key的hash值相同，
             // 并 满足(table现有的结点的key和准备添加的key是同一个对象  || equals返回真)
             // 就认为不能加入新的k-v
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)//如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    //如果找到的结点，后面是链表，就循环比较
                    for (int binCount = 0; ; ++binCount) {//死循环
                        if ((e = p.next) == null) {//如果整个链表，没有和他相同,就加到该链表的最后
                            p.next = newNode(hash, key, value, null);
                            //加入后，判断当前链表的个数，是否已经到8个，到8个，后
                            //就调用 treeifyBin 方法进行红黑树的转换
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash && //如果在循环比较过程中，发现有相同,就break,就只是替换value
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value; //替换，key对应value
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;//每增加一个Node ,就size++
            if (++size > threshold[12-24-48])//如size > 临界值，就扩容
                resize();
            afterNodeInsertion(evict);
            return null;
        }
          5. 关于树化(转成红黑树)
          //如果table 为null ,或者大小还没有到 64，暂时不树化，而是进行扩容.
          //否则才会真正的树化 -> 剪枝
          final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();
        }
     */
}

}


模拟 HashMap 出发扩容、树化情况，并用 Debug验证
```java
package com.hspedu.map_;
import java.util.HashMap;
import java.util.Objects;
@SuppressWarnings({"all"})
public class HashMapSource2 {
    public static void main(String[] args) {
        HashMap hashMap = new HashMap();
        for(int i = 1; i <= 12; i++) {
            hashMap.put(i, "hello");
        }
        hashMap.put("aaa", "bbb");
        System.out.println("hashMap=" + hashMap);//12个 k-v
        //布置一个任务，自己设计代码去验证，table 的扩容
        //0 -> 16(12) -> 32(24) -> 64(64*0.75=48)-> 128 (96) ->
        //自己设计程序，验证-》 增强自己阅读源码能力. 看别人代码.
    }
}
class A  {
    private int num;
    public A(int num) {
        this.num = num;
    }
    //所有的A对象的hashCode都是100
//    @Override
//    public int hashCode() {
//        return 100;
//    }
    @Override
    public String toString() {
        return "\nA{" +
                "num=" + num +
                '}';
    }
}

5.6 Hashtable 的全面说明

存放的元素是键值对：即 K-V
Hashtable 的键和值都不能为 null，否则会抛出 NullPointerException
Hashtable 使用方法基本上和 HashMap 一样
Hashtable 是线程安全的(synchronized)，HashMap 是线程不安全的

5.7 Hashtable 和 HashMap 对比

	版本	线程安全（同步）	效率	null键 null值
HashMap	1.2	不安全	高	允许
Hashtable	1.0	安全	较低	不允许

5.8 Properties 基本介绍

Properties 类继承自 Hashtable 类并且实现了 Map接口，也是使用一种键值对的形式来保存数据
它的使用特点和Hashtable类似
Properties 还可以用于从 xxx.properties 文件中，加载数据到 Properties 类对象，并进行读取和修改
说明：工作后 xxx.properties 文件通常作为配置文件，这个知识点在IO流举例

基本使用

package com.hspedu.map_;
import java.util.Properties;
@SuppressWarnings({"all"})
public class Properties_ {
    public static void main(String[] args) {
        //老韩解读
        //1. Properties 继承  Hashtable
        //2. 可以通过 k-v 存放数据，当然key 和 value 不能为 null
        //增加
        Properties properties = new Properties();
        //properties.put(null, "abc");//抛出 空指针异常
        //properties.put("abc", null); //抛出 空指针异常
        properties.put("john", 100);//k-v
        properties.put("lucy", 100);
        properties.put("lic", 100);
        properties.put("lic", 88);//如果有相同的key ， value被替换
        System.out.println("properties=" + properties);
        //通过k 获取对应值
        System.out.println(properties.get("lic"));//88
        //删除
        properties.remove("lic");
        System.out.println("properties=" + properties);
        //修改
        properties.put("john", "约翰");
        System.out.println("properties=" + properties);
    }
}

5.9 TreeMap 和 TreeSet

TreeSet 底层是TreeMap

package com.hspedu.map_;
import java.util.Comparator;
import java.util.TreeMap;
@SuppressWarnings({"all"})
public class TreeMap_ {
    public static void main(String[] args) {
        //使用默认的构造器，创建TreeMap, 是无序的(也没有排序)
        /*
            老韩要求：按照传入的 k(String) 的大小进行排序
         */
//        TreeMap treeMap = new TreeMap();
        TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //按照传入的 k(String) 的大小进行排序
                //按照K(String) 的长度大小排序
                //return ((String) o2).compareTo((String) o1);
                return ((String) o2).length() - ((String) o1).length();
            }
        });
        treeMap.put("jack", "杰克");
        treeMap.put("tom", "汤姆");
        treeMap.put("kristina", "克瑞斯提诺");
        treeMap.put("smith", "斯密斯");
        treeMap.put("hsp", "韩顺平");//加入不了
        System.out.println("treemap=" + treeMap);
        /*
            老韩解读源码：
            1. 构造器. 把传入的实现了 Comparator接口的匿名内部类(对象)，传给给TreeMap的comparator
             public TreeMap(Comparator<? super K> comparator) {
                this.comparator = comparator;
            }
            2. 调用put方法
            2.1 第一次添加, 把k-v 封装到 Entry对象，放入root
            Entry<K,V> t = root;
            if (t == null) {
                compare(key, key); // type (and possibly null) check
                root = new Entry<>(key, value, null);
                size = 1;
                modCount++;
                return null;
            }
            2.2 以后添加
            Comparator<? super K> cpr = comparator;
            if (cpr != null) {
                do { //遍历所有的key , 给当前key找到适当位置
                    parent = t;
                    cmp = cpr.compare(key, t.key);//动态绑定到我们的匿名内部类的compare
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else  //如果遍历过程中，发现准备添加Key 和当前已有的Key 相等，就不添加
                        return t.setValue(value);
                } while (t != null);
            }
         */
    }
}

package com.hspedu.set_;
import java.util.Comparator;
import java.util.TreeSet;
@SuppressWarnings({"all"})
public class TreeSet_ {
    public static void main(String[] args) {
        //老韩解读
        //1. 当我们使用无参构造器，创建TreeSet时，仍然是无序的
        //2. 老师希望添加的元素，按照字符串大小来排序
        //3. 使用TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)
        //   并指定排序规则
        //4. 简单看看源码
        //老韩解读
        /*
        1. 构造器把传入的比较器对象，赋给了 TreeSet的底层的 TreeMap的属性this.comparator
         public TreeMap(Comparator<? super K> comparator) {
                this.comparator = comparator;
            }
         2. 在 调用 treeSet.add("tom"), 在底层会执行到
             if (cpr != null) {//cpr 就是我们的匿名内部类(对象)
                do {
                    parent = t;
                    //动态绑定到我们的匿名内部类(对象)compare
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else //如果相等，即返回0,这个Key就没有加入
                        return t.setValue(value);
                } while (t != null);
            }
         */
//        TreeSet treeSet = new TreeSet();
        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //下面 调用String的 compareTo方法进行字符串大小比较
                //如果老韩要求加入的元素，按照长度大小排序
                //return ((String) o2).compareTo((String) o1);
                return ((String) o1).length() - ((String) o2).length();
            }
        });
        //添加数据.
        treeSet.add("jack");
        treeSet.add("tom");//3
        treeSet.add("sp");
        treeSet.add("a");
        treeSet.add("abc");//3
        System.out.println("treeSet=" + treeSet);
    }
}

六、总结：开发中如何选择集合实现类（记住）

在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择，分析如下

先判断存储的类型（一组对象【单列】或一组键值对【双列】）
一组对象【单列】：Collection接口
1. 允许重复：List
  1. 增删多：LinkedList【底层维护了一个双向链表】
  2. 改查多：ArrayList【底层维护了 Object类型的可变数组】
2. 不允许重复：Set
  1. 无序：HashSet【底层是HashMap，维护了一个哈希表即(数据+链表+红黑树)】
  2. 排序：TreeSet
  3. 插入和取出排序一致：LinkedHashSet 维护数组+链表+双向链表
一组键值对【双列】：Map
1. 键无序：HashMap【底层是：哈希表 jdk7：数组+链表 jdk8：数组+链表+红黑树】
2. 键排序：TreeMap
3. 键插入和取出顺序一致：LinkedHashMap
4. 读取文件：Properties

七、Collections 工具类

7.1 Collections 工具类介绍

Collections 是一个操作 Set、List 和 Map 等集合的工具类
Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作

7.2 排序操作

method	功能
reverse(List)	反转 List 中元素的顺序
shuffle(List)	对List集合元素进行随机排序
sort(List)	根据元素的现有顺序对指定List集合元素按升序排序
sort(List, Comparator)	根据指定的Comparator 产生的顺序对List集合进行排序
swap(List, int i, int j)	将指定 List集合中的 i 处元素和 j处元素进行交换

package com.hspedu.collections_;
import java.util.*;
@SuppressWarnings({"all"})
public class Collections_ {
    public static void main(String[] args) {
        //创建ArrayList 集合，用于测试.
        List list = new ArrayList();
        list.add("tom");
        list.add("smith");
        list.add("king");
        list.add("milan");
        list.add("tom");
//        reverse(List)：反转 List 中元素的顺序
        Collections.reverse(list);
        System.out.println("list=" + list);
//        shuffle(List)：对 List 集合元素进行随机排序
//        for (int i = 0; i < 5; i++) {
//            Collections.shuffle(list);
//            System.out.println("list=" + list);
//        }
//        sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
        Collections.sort(list);
        System.out.println("自然排序后");
        System.out.println("list=" + list);
//        sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
        //我们希望按照 字符串的长度大小排序
        Collections.sort(list, new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //可以加入校验代码.
                return ((String) o2).length() - ((String) o1).length();
            }
        });
        System.out.println("字符串长度大小排序=" + list);
//        swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
        //比如
        Collections.swap(list, 0, 1);
        System.out.println("交换后的情况");
        System.out.println("list=" + list);
    }
}

7.3 查找、替换

method	功能
Object max(Collection)	根据元素的自然排序，返回给定集合中的最大元素
Object max(Collection, Comparator)	根据Comparator指定的顺序，返回给定集合中的最大元素
Object min(Collection)	根据元素的自然排序，返回给定集合中的最小元素
Object min(Collection, Comparator)	根据Comparator指定的顺序，返回给定集合中的最小元素
int frequency(Collection, Object)	返回指定集合中指定元素的出现次数
void copy(List dest, List src)	将 src 中的内容复制到 dest 中 *
boolean replaceAll(List list, Object oldVal, Object newVal)	使用新值替换 List对象中的所有旧值

//Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
System.out.println("自然顺序最大元素=" + Collections.max(list));
//Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
//比如，我们要返回长度最大的元素
Object maxObject = Collections.max(list, new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        return ((String)o1).length() - ((String)o2).length();
    }
});
System.out.println("长度最大的元素=" + maxObject);
//Object min(Collection)
//Object min(Collection，Comparator)
//上面的两个方法，参考max即可
//int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
System.out.println("tom出现的次数=" + Collections.frequency(list, "tom"));
//void copy(List dest,List src)：将src中的内容复制到dest中
ArrayList dest = new ArrayList();
//为了完成一个完整拷贝，我们需要先给dest 赋值，大小和list.size()一样 *
for(int i = 0; i < list.size(); i++) {
    dest.add("");
}
//拷贝
Collections.copy(dest, list);
System.out.println("dest=" + dest);
//boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值
//如果list中，有tom 就替换成 汤姆
Collections.replaceAll(list, "tom", "汤姆");
System.out.println("list替换后=" + list);

八、本章作业

编程题

按要求实现：

封装个新闻类，包含标题和内容属性，提供get、set方法，重写toString方法，打印对象时只打印标题
只提供一个带参数的构造器，实例化对象时，只初始化标题;并且实例化两个对象:

新闻一:新冠确诊病例超千万，数百万印度教信徒赴恒河“圣浴”引民众担忧
新闻二:男子突然想起2个月前钓的鱼还在网兜里，捞起一看赶紧放生

将新闻对象添加到ArrayList集合中，并且进行倒序遍历;
在遍历集合过程中，对新闻标题进行处理，超过15字的只保留前15个，然后在后边加”…”
在控制台打印遍历出经过处理的新闻标题;

编程题

使用ArrayList完成对对象Car {name, price}的各种操作

add:添加单个元素
remove:删除指定元素
contains:查找元素是否存在
size:获取元素个数
isEmpty:判断是否为空
clear:清空
addAll:添加多个元素
containsAll:查找多个元素是否都存在
removeAll: 删除多个元素

使用增强for和迭代器来遍历所有的car，需要重写Car的toString方法
Car car = new Car(“宝马” 400000);
Car car2 = new Car(“宾利”，5000000);

编程题

按要求完成下列任务

使用HashMap类实例化一个Map类型的对象m,键(String) 和值(int)
分别用于存储员工的姓名和工资，存入数据如下:

jack- -650元; tom- -1200元; smith- 2900元;

将jack的工资更改为2600元
为所有员工工资加薪100元
遍历集合中所有的员工
遍压集合中所有的工资

简答题

试分析 HashSet 和 TreeSet 分别如何实现去重的？

(1) HashSet的去重机制：
hashCode() + equals()底层先通过存入对象，进行运算得到一个hash值，通过hash值得到对应的索引，如果发现table索引所在的位置，没有数据，就直接存放。如果有数据，就进行equals比较[遍历比较]，如果比较后，不相同,就加入，否则就不加入
(2) TreeSet的去重机制:如果你传入了一个Comparator匿名对象，就使用实现的compare去重，如果方法返回0，就认为是相同的元素/数据，就不添加，如果你没有传入一个Comparator 匿名对象，则以你添加的对象实现的 Compareable 接口的 compareTo 去重.

代码分析题：

下面代码运行会不会抛出异常，并从源码层面说明原因. [考察读源码+接口编程+动态绑定]
TreeSet treeSet = new TreeSet();
treeSet.add(new Person();

会抛出异常，如果创建TreeSet没有使用 Comparator 构造器，则在添加内容时进行的比较会将对象自动转成 Comparable 接口类型，如果add 的对象没有实现Comparable 接口，就会抛出 ClassCastException

下面的代码输出什么? *

提示：这道题很有意思，稍不注意就掉进陷阱
已知: Person类按照 id 和 name 重写了 hashCode 和 equals 方法，问下面代码输出什么?
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);
System.out.println(set);
set.add(new Person(1001,”CC”));
System.out.println(set);
set.add(new Person(1001,” AA”));
System.out.println(set);

package com.hspedu.homework_.homework06;
import java.util.HashSet;
import java.util.Objects;
/**
 * @author HarborGao
 * @version 1.0
 */
@SuppressWarnings({"all"})
public class Homework06 {
    public static void main(String[] args) {
        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";
        System.out.println(set);  //发现 会输出变动之后的 p1，原因就是上面的引用
        set.remove(p1);  //由于重写了 hashCode,所以查找的时候会按照更改后的p1的id和name计算hash，从而找到错误的索引，所以删除失败
        System.out.println(set);
        set.add(new Person(1001,"CC"));  //由于p1存放在更改前的索引，所以这个新对象可以成功加入集合
        System.out.println(set);
        set.add(new Person(1001,"AA"));//会找到p1所在的索引，但由于p1已经改动，所以equals对比后也会加入这个新元素
        System.out.println(set);
    }
}
class Person {
    int id;
    String name;
    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Person{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id && Objects.equals(name, person.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

学习参考（致谢）：

B站 @程序员鱼皮 Java学习一条龙
B站 @韩顺平零基础30天学会Java