Java-Day-17

集合

先前用于保存多个数据使用的是 —— 数组
- 长度开始必须指定，且不能更改
- 保存的必须为同一类型的元素
- 使用数组进行增删元素的代码较为麻烦
  - 例：扩容的要先建新数组，再拷贝原数据、添加新对象
引出集合
- 可以动态保存任意多个对象，使用比较方便
- 提供了一系列方便的操作对象的方法：add、remove、set、get
- 使用集合添加，删除新元素更加简洁明了
集合的框架体系 ( 集合主要分为两大类 )
- 单列集合 ( 存放：单对象 ) —— Collection 两个重要子接口的实现子类
- 双列集合 ( 存放：键值对式，K - V ) —— Map 的接口的实现子类

Collection 接口和常用方法

public interface Collection extends Iterable
- ：泛型参数可以代表任何类型
Collection
- 其实现子类可以存放多个元素，每个元素可以是 Object
- 有些 Collection 的实现类，可以存放重复的元素，有些不可以
- 有些 Collection 的实现类，有些是有序的 ( List )，有些不是有序 ( Set )
- Collection 接口没有直接的实现子类，是通过它的子接口 Set 和 List 来实现的

Collection 接口常用方法

( 接口不能实例化，所以用 ArrayList 进行编写 )

List list = new ArrayList();
//        add：添加单个元素
list.add("zhu");
list.add(10); // 自动装箱：list.add(new Integer(10))
list.add(true); // 自动装箱
System.out.println("list = " + list);
//        remove：删除指定元素
list.remove(0); // 删除第一个元素
System.out.println("list = " + list);
list.remove(true); // 删除指定元素
System.out.println("list = " + list);
//        contains：查找元素是否存在
System.out.println(list.contains("zhu")); // 不存在就返回 false
//        size：获取元素个数
System.out.println(list.size()); // 1
//        isEmpty：判断是否为空
System.out.println(list.isEmpty()); // 为空才返回 true
//        addAll：添加多个元素
ArrayList list1 = new ArrayList();
list1.add("ya");
list1.add(820);
list.addAll(list1);
System.out.println("list = " + list);
//        containsAll：查找多个元素是否都存在
System.out.println(list.containsAll(list1)); // 存在就 true
//        removeAll：删除多个元素
list.removeAll(list1);
System.out.println("list = " + list);
//        clear：清空
list.clear();
System.out.println("list = " + list); // list = []

Collection 接口遍历元素方式 1 —— 使用 Iterator ( 迭代器 )
- 但凡是实现类 Collection 接口的子类都可以获取一个迭代器
- Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素
- 所有实现了 Collection 接口的集合类都有一个 iterator() 方法，用以返回一个实现了 iterator 接口的对象，即可以返回一个迭代器
- Iterator 的结构
- Iterator 仅用于遍历集合，Iterator 本身并不存放对象
Collection 接口遍历元素方式 2 —— 使用 for循环增强
- 增强 for 循环可以代替 iterator 迭代器，特点：增强 for 就是简化版的 iterator，只能用于遍历集合或数组
- 看源码，底层仍然是迭代器

Iterator 迭代器

遍历元素

执行原理

while 生成迭代器快捷键：itit + enter 回车

// 例：
Collection coll = new ArrayList();
coll.add(new 对象(...));
// ......
    
// 得到一个集合的迭代器
Iterator iterator = coll.iterator();
// 此对象中方法 hasNext()：判断是否还有下一个元素
while(iterator.hasNext()){
    // next()：指针下移
    // 将下移后集合位置上的元素返回，直到最后一个元素
    // 因为此处举例是对象，就用Object(编译类型，运行类型还要看上述 new 的对象)
    Object obj = iterator.next();
    System.out.println(obj);
}

注意 next() 前一定要加 hasNext()，否则若是下一条记录无效，就会抛出异常

显示所有快捷键的快捷键：ctrl + j
next 结束后，iterator 迭代器指向到了最后的元素，这时想要再次遍历就要重置迭代器
```
iterator = coll.iterator();
// itit
// while... 重复第二次遍历
```

增强 for 循环

基本语法：

生成快捷键：I ( 大写 i ) + enter

// 集合例：
Collection coll = new ArrayList();
// 由体系框架可知，可以直接 List list = new ArrayList();
coll.add(new 对象(...));
// ......

for(Object obj : coll) {
    System.out.println(obj);
}

// 数组例：
int[] nums = {1,2,3,4};

for(int i : nums){
    System.out.println(i);
}

List 接口和常用方法

List 接口是 Collection 接口的子接口
- List 集合类中的元素有序 ( 即添加和取出的顺序一致 )、而且可重复
- List 集合中的每个元素都有其对应的顺序索引，即支持索引
- List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素
  - 例：list.get(3); // 取到第4个元素 ( 索引是从 0 开始的 )
- JDK 中 List 的接口的实现类有很多，常用的是 ArrayList、LinkedList 和 Vector

常用方法

public static void main(String[] args) throws ParseException {
    List list = new ArrayList();
    list.add("朱哇");
    list.add("朱呀");
    list.add("朱哇"); // 元素可重复
    //        插入，在index的位置插入一个对象，添加想插入的位置序号
    list.add(1, "我插");
    System.out.println(list);
    //        插入多个对象
    List list1 = new ArrayList();
    list1.add("dada");
    list1.add("llaa");
    list.addAll(1, list1);
    System.out.println(list);
    //        获取指定位置的元素，索引从零开始
    System.out.println(list.get(3));
    //        返回obj在集合中首次出现的位置
    System.out.println(list.indexOf("朱哇"));
    //        返回obj在集合中最后一次出现的位置
    System.out.println(list.lastIndexOf("朱哇"));
    //        移除指定index位置的元素，并可以选择接收即返回此元素
    System.out.println(list.remove(5));
    System.out.println(list);
    //        设置指定位置的元素为...，相当于替换，不存在的位置就会越界异常，最后插入也不行
    list.set(1, "dalada");
    System.out.println(list);
    //        返回从fromIndex到toIndex位置的子集合，注意返回的是前闭后开的，即 [0,2)
    List returnlist = list.subList(0, 2);
    System.out.println(returnlist);
    
    //        Iterator iterator = list.iterator();
    //        while (iterator.hasNext()) {
    //            Object next =  iterator.next();
    //            System.out.println("迭代器依次输出：" + next);
    //        }

List 的三种遍历方法：iterator、增强 for、for 循环

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    Object next =  iterator.next();
    System.out.println("迭代器依次输出：" + next);
}


for (Object obj :list) {
    System.out.println(obj);
}


for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

练习：对 Book 对象的价格从大到小进行冒泡排序

public static void sort(List list){
    int listSize = list.size();
    for (int i = 0; i < listSize - 1; i++){
        for (int j = 0; j < listSize - 1 - i; j++){
            Book book1 = (Book)list.get(j);
            Book book2 = (Book)list.get(j+1);
            //                将书价格从小到大排序
            if (book1.getPrice() > book2.getPrice()){
                list.set(j, book2);
                list.set(j + 1, book1);
            }
        }
    }
}

ArrayList

了解认识

源码：permits all elements, including null
- 即可以加入多个 null，并且可以有多个 null
ArrayList 底层是由数组来实现数据存储的
ArrayList 基本等同于 Vector，除了 ArrayList 是线程不安全 ( 源码没有注解线程互斥，但执行效率高 )，所以多线程不建议用 ArrayList

底层结构和源码分析

ArrayList 中维护了一个 Object 类型的数组 elementData
- transient Object[] elementData; // transient：短暂的，表示该属性不会被序列化
- 每次 add 添加都要确定是否要扩容，然后再执行赋值
当创建 ArrayList 对象时，如果使用的是无参构造器 ( ArrayList() )，则初始 elementData 容量为 0 ( 实则空数组 )，第一次添加，则扩容 elementData 为 10，如果需要再次扩容，则扩容 elementData 为 1.5 倍 ( 即：0 — 10 — 15 — 22 )
- 第一次 add ( 因为 int 类型，还会判断是否超出 int 大小，进行装箱操作 )
- add 方法里每次都要来确认 ( ensureCapacityInternal )，第一次扩容是 ensureCapacityInternal：ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
- calculateCapacity() 里 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 确认 elementData 是否为空 ( 第一次为空 )，空的话就 Math.max 扩为 10 ( 默认 DEFAULT_CAPACITY = 10 )，返回
- 然后 ensureExplicitCapacity() 确定扩容 ( modCount 记录修改次数，防止多线程异常 )，在此方法里判断是否容量过大溢出，如果不够，这里 grow() 真正扩容，足够的话就不需要扩容了
- grow 里 1.5倍：new = old + ( old >> 1 )，if 修正使得第一次扩为 10 ( 否则 0 倍数还是 0 )，扩容机制确定后 Arrays.copyOf() 保留原数据赋给新扩容的 ( 新扩的就是 null 补上 )
- 最后一步步返回给 add()，list.size = 1
- 后面重复以上步骤：不过后面不需再 calculateCapacity() 里判空，直接返回 size + 1 给
- 但 Idea Debug 的时候，默认显示的数据是简化后的，如：逐条增加时可能会把新扩的 null 给加以隐藏不显示
- 若是想不加以简化隐藏的话就要加以设置 ( 将下图两处取消勾选 )
如果使用的是指定大小的构造器 ( ArrayList(int) )，则初始 elementData 容量为指定大小，如果需要扩容，则直接扩容 elementData 为其现有的 1.5 倍，依此类推
- 源码似无参，只多了一步 this.elementData = new Object[initialCapacity]; 直接把指定的大小赋给 initialCapacity
- 扩容时同样 minCapacity - elementData.length > 0 进行判断，然后 grow()，直接 1.5 倍扩容，不需要修正

Vector

了解认识

类定义

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector 底层也是一个对象数组，protected Object[] elementData
Vector 是线程同步的，即线程安全，类中的操作方法带有 synchronized ( 代表支持线程同步和互斥 )，
在开发过程中，需要线程同步安全时，考虑使用 Vector

底层结构和源码分析

无参构造器，源码直接 this(10)，即仍然回到了有参构造器直接给其扩为 10，之后的代码机制有参、无参就都相同了
过程很类似，都是先自动装箱 ......
扩容两倍：int newCapacity = oldCapacity + (oldCapacity >> 1);，有的版本是用了三元运算符 ( 可选择扩容大小？)

ArrayList 与 Vector 对比

	底层结构	出现版本	线程安全 ( 同步 )、效率	扩容倍数
ArrayList	可变数组	jdk 1.2	不安全，效率高	有参 1.5 倍扩，无参先给 10，再 1.5倍
Vector	可变数组	jdk 1.0	安全，效率不高	有参 2 倍扩，无参直接给 10，再 2 倍

LinkedList

了解认识

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

底层结构和源码分析

LinkedList 底层维护了一个双向链表
LinkedList 中维护了两个属性 first 和 last，分别指向首节点和尾节点
每个节点 ( Node 对象 ) 里面有维护了 prev ( previous )、next、item 三个属性，其中 item 真正存放数据，通过 prev 指向前一个节点，通过 next 指向后一个节点 ( 这样只需要改变其指向就能简单实现增删 )，最终实现双向链表
所以 LinkedList 的元素的添加和删除不是通过数组完成的，相对来说效率较高
代码模拟一简单双向链表 ( 注意：这里是为了便于了解，重点详细仍在于数据结构部分 )

简单来看双链表每部分都是由 first、item、last 来组成的

public class test1 {
    public static void main(String[] args) throws ParseException {
//        一个简单的双向链表：

        Node a = new Node("a");
        Node b = new Node("b");
        Node zyz = new Node("zyz");

        a.next = b;
        b.next = zyz;
        zyz.prev = b;
        b.prev = a;

        Node first = a; // 双向链表的头节点为a
        Node last = zyz; // 双向链表的尾节点为zyz



        System.out.println("演示从头到尾的遍历");
        while (true) {
            if (first == null){
                break;
            }
            System.out.println(first);
            first = first.next;
        }
        System.out.println("演示从尾到头的遍历");
        while (true) {
            if (last == null){
                break;
            }
            System.out.println(last);
            last = last.prev;
        }

        System.out.println("链表的添加：增改四个节点—插入到zyz前面");
        Node dalada = new Node("dalada");
        b.next = dalada;
        zyz.prev = dalada;
        dalada.next = zyz;
        dalada.prev = b;

        System.out.println("演示从头到尾的遍历");
        first = a;  // 重置first指向，从最后再放回到开头
        while (true) {
            if (first == null){
                break;
            }
            System.out.println(first);
            first = first.next;
        }
        System.out.println("演示从尾到头的遍历");
        last = zyz;
        while (true) {
            if (last == null){
                break;
            }
            System.out.println(last);
            last = last.prev;
        }
    }
}

// 定义，用其表示双向链表的一个节点
class Node {
    public Object item; // 真正存放数据
    public Node next;
    public Node prev;
    public Node(Object name){
        this.item = name;
    }
    public String toString(){
        return "Node name = " + item;
    }
}

增删改查 ( CRUD ) 案例

public static void main(String[] args) throws ParseException {
    //        添加
    LinkedList linkedList = new LinkedList();
    linkedList.add("a");
    linkedList.add("b");
    System.out.println(linkedList);
    /* 增加的源码：
         * 先 public LinkedList() {} 初始化，size = 0，其余 null
         * int 装箱
         * 执行添加 linkLast(e);
         * 方法里面将first和last都指向了这第一个双链表新节点newNode
         * newNode = new Node<>(prev, item, next)，prev为保留的第一个节点，item存，next暂设null
         * last指向新节点newNode (每次都拿last来进行过渡，以此类推)
         */

    //        删除(这里用默认删除第一个节点的删除方法)
    linkedList.remove();
    /* 删除的源码：
         * remove 调用了 removeFirst() 方法，在此方法里再调用unlinkFirst() 方法真正删除
         * 取到第一个节点内容和第一个节点的next，并全为null，断一连接线
         * first = 提前赋的第一个节点的next
         * 第一个节点的next的prev赋null，再断一连接线
         * 最后返回删除的内容，可选择不接收不用
         */

    //        修改某个节点
    linkedList.set(1, "zyz");

    //        获取某个节点对象
    Object o = linkedList.get(1);
    System.out.println(o);

    //        因为是实现了List接口，所以遍历方式同有三种方式
}

ArrayList 与 linkedList 对比

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

所以改查的操作多时，选择 ArrayList，索引定位
增删的操作多的话，选择 linkedList，可直接追加
一般项目都是查询多，所以大部分都是用 ArrayList，也可以根据业务灵活选择
两者都是线程不安全的

Set 接口的常用方法

无序 ( 添加和取出顺序不一致 )，没有索引

//        以Set接口的实现类HashSet来讲解Set接口的方法
//        xx接口对象 ——叫法即—— xx接口实现类的对象
Set set = new HashSet();
set.add("zyz");
set.add("b");
set.add("zyz");
System.out.println(set); // [b, zyz]
//        不能存放重复元素，不会报错，而是添加不进去

但注意，虽然无序，即添加顺序和取出顺序极大概率不一致，但是只要取出了，这个取出的顺序是不会变的，不会取一次变一次

不允许重复元素，所以最多包含一个 null
JDK API 中 Set 接口的实现类有很多，常用就是 HashSet 和 TreeSet
关于常用方法，因为和 List 接口一样都是属于 Collection 的子接口，所以常用方法和 Collection 接口一样
遍历方式可以使用迭代器、增强 for，但是不能使用索引的方式来获取了 ( 无 get() 方法 )
常用方法：add、remove、iterator ......
- 全部方法可通过类图查看

HashSet

了解

实现 Set 接口

实际上底层是 HashMap

public HashSet() {
    map = new HashMap<>();
}

元素 / 对象不可重复，且可放但仅限一个 null
- 重复添加的话，System 控制台就会显示返回 false
不保证元素有序，取决于 hash，即不保证存与取顺序一致

小练习

HashSet hashSet = new HashSet();
//        System.out.println(hashSet.add("zyz")); // true
//        System.out.println(hashSet.add("z")); // true
//        System.out.println(hashSet.add("zyz")); // false

hashSet.add("zyz");
hashSet.add("zyz"); // 不能加入
hashSet.add(new Dog("大黄")); // 地址不同，即只是名同的两个对象
hashSet.add(new Dog("大黄")); // 所以都能加入进去
System.out.println(hashSet);

//        经典出错，要看底层源码
hashSet.add(new String("crud")); // 加入
hashSet.add(new String("crud")); // ？——不能加入
System.out.println(hashSet);

底层机制说明

HashSet 底层是 HashMap，HashMap 底层是 ( 数组 + 链表 + 红黑树 )

为理解，模拟简单的数组 ( 零位置可存一个 Node 节点，并携有 next ... ) + 链表结构

public class test1 {
    public static void main(String[] args) {
//        模拟一个 HashSet 的底层
//        1. 创建一个数组，数组类型 Node[]
//        2. 有的直接把 Node[] 数组称为 表
        Node[] table = new Node[16];
//        3. 创建节点，假设算法所得zyz的索引为2
        Node zyz = new Node("zyz", null);
        table[2] = zyz;
        Node dala = new Node("dala", null);
//        把 dala 节点挂载到 zyz 后面
        zyz.next = dala;
        Node duang = new Node("duang", null);
        dala.next = duang;
        System.out.println(table);
    }
}

// 节点，存储数据，可以指向下一个节点，从而形成链表
class Node {
   Object item;
   Node next;
    public Node(Object item, Node next) {
        this.item = item;
        this.next = next;
    }
}

在索引为2的位置就形成了一个链表,完成了数据存储的高效性，后期学到红黑树，就更进一步提高了效率 ( 红黑树 > 链表 > 数组存储 )

底层分析 HashSet 的添加元素底层是如何实现 ( hash() + equals() )

HashSet 底层是 HashMap
添加一个元素时，先得到 hash 值，然后转换成索引值 ( 某算法所得 )
找到存储数据表 table，看这个索引位置是否已经存放有元素
如果没有元素，就直接加入
如果有，调用 equals ( 方法怎么比较可由程序员 ) 比较，如果相同就放弃添加 ( 元素不能重复的原因 )，如果不同，则添加到最后 ( 似 next )
在 Java8 中，如果一条链表的元素个数到了 TREEIFY_THRESHOLD ( 默认是 8 )，而且 table 的大小 >= MIN_TREEIFY_CAPACITY ( 默认 64 )，就会进行树化 ( 成红黑树 )

源码剖析

@SuppressWarnings({"all"}) // 抑制淡黄色警告,可不加
public class test1 {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("zyz");
        hashSet.add("java");
        System.out.println("set =" + hashSet);

        /*
        第一次:hashSet.add("java");
        1. HashSet():
            public HashSet() {
                map = new HashMap<>();
            }
        2. add():
            public boolean add(E e) { // E:泛型
                return map.put(e, PRESENT)==null;
            }
        3. put():
            public V put(K key, V value) { // K:(传的值)"java" V:(PRESENT)静态Object,占位
                return putVal(hash(key), key, value, false, true);
            }
            static final int hash(Object key) {
                int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            } // 此算法可理解为尽可能得到不同的值来避免元素的碰撞
            该方法会通过执行 hash(key) 得到对应的hash值(!!注:并不完全等于hashCode()!!)
        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[]
//                 因为HashSet底层是HashMap,理解好因为HashSet实际上就是要理解好HashMap
//                 此时table是null或大小为0,就是第一次扩容
                if ((tab = table) == null || (n = tab.length) == 0)
//                 tab是null的时候,resize底层实际主要代码:
//                 newCap = DEFAULT_INITIAL_CAPACITY;  // 默认开空间:16
//                 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  // 算临界值newThr:0.75*16=12,即当用到12时就开始准备扩容(缓冲,防大量数据)
//                 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//                 table = newTab; // table变为16空间大小
//                 return newTab;
//                 此时n就为16了
                    n = (tab = resize()).length;
//                 拿到K算出的hash后计算在table表的哪个索引位置,并赋值给p
                if ((p = tab[i = (n - 1) & hash]) == null)
//                 判断p如果是空:还没有存放元素,就创建一个节点Node,key=传来的值,value=PRESENT
//                 就放tab[i]里,"java"值的节点就放到了3位置,然后就是后面的
                    tab[i] = newNode(hash, key, value, null);
                else {
                    Node<K,V> e; K k;
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                    else if (p instanceof TreeNode)
                        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);
                                if (binCount >= TREEIFY_THRESHOLD - 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;
                    }
                }
//                修改次数+1
                ++modCount;
//                第一次的话就是判断 1>12(临界值),是否要扩容
                if (++size > threshold)
                    resize();
//                空的,对于先在的HashMap来说可以忽略
                afterNodeInsertion(evict);
//                返回空就代表成功了,因为返回到add()会判断==null
                return null;
            }

        5. 第二次:hashSet.add("zyz");
        HashSet()--add()--put()--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已经创建好了,== 16
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;
//                再次得到存放到table的位置
                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = newNode(hash, key, value, null);
                else {
                    ......
                }
//                debug到这里就可以看出"zyz"存到了table的10位置,
//                修改次数+1
                ++modCount;
//                2 > 12 跳过扩容
                if (++size > threshold)
                    resize();
                afterNodeInsertion(evict);
                return null;
            }
        6.第三次:hashSet.add("java");
          核心代码!! 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;  // 定义辅助变量
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;
//                    因为K还是"java",所以肯定不再是空,p是3(上次计算过了)
                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = newNode(hash, key, value, null);
//                    所以直接到下述代码
                else {
//                    开发技巧提示,在需要的地方再创建局部变量(辅助变量)
                    Node<K,V> e; K k; // 定义辅助变量
//                    如果当前索引位置(3)对应的链表的第一个元素和准备添加的key的哈希值相同
                    if (p.hash == hash &&
//                    并且想加入的key和p指向Node节点的key是同一个对象/不同对象但内容相同,就不能加入了
// 					  equals方法时程序员选择性重写
                        ((k = p.key) == key || (key != null && key.equals(k))))
//                    此情况下跳到后面的下一个if
                        e = p;
//                    如果上述不成立 else 判断p是不是一个红黑树
//                    如果是一个红黑树的话就调用putTreeVal()方法进行添加
                    else if (p instanceof TreeNode)
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//                    也不是红黑树就再来table索引位置进链表内进行比较,如果next每个元素都不相同就挂在最后,但只要有相同的就break掉
                    else {
//                    for的死循环,非添就退
                        for (int binCount = 0; ; ++binCount) {
//                    next指向空了(e处),就代表到最后了,直接挂上(第一个链首已经在前面的if语句比较过了)
                            if ((e = p.next) == null) {
//                    挂上newNode
                                p.next = newNode(hash, key, value, null);
//                    加入到链表后立即判断链表是否达到8个节点(binCount从0开始到为7时),就调用treeifyBin()将链表转成红黑树
                                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
//                    treeifyBin()里会先判断:if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//                    MIN_TREEIFY_CAPACITY == 64,若是没到64就先不树化,先通过resize()扩容来进行解决
//                    单条到8,总到64,都满足了就树化
                                break;
                            }
//                    有相同时,直接break
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;

//                     在此p每次都做下移,回到for循环处,依此类推
                            p = e;
                        }
                    }
//                     因为"java"相同就来此(前面e=p了),不会返回null的话就失败
                    if (e != null) { // existing mapping for key
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
//                修改次数+1
                ++modCount;
//                第一次的话就是判断 1>12(临界值),是否要扩容， 
                if (++size > threshold)
                    resize();
//                空的,对于先在的HashMap来说可以忽略
                afterNodeInsertion(evict);
//                返回空就代表成功了,因为返回到add()会判断==null
                return null;
            }
         */
    }
}

第一次添加时 table 大小扩容为 16 ( 0 ~ 15 )，临界值 = 16 * 0.75 ( loadFactor ) = 12
若是到临界 ( 阈值 threshold ) 的 12 了就扩到 16 * 2 = 32，新的临界值就是 32 * 0.75 = 24，依此类推 ( 到 24 就扩为 64 ...... )，2倍扩，0.75倍临界
Java8 中，有一条个数到 8，table 到 64 就树化为红黑树，否则总没到 64 的话就仍采用数组扩容机制，16 大小的话就变大小为 32 ( 单条 9 )、再 64 ( 单条 10 )，此时再增单条就不会再扩容了，就是 TreeNode 红黑树了
注意，只要成功能添加就 size 加一，不管是不是同一个 table 索引下的都是同一个 size 加一，即，只要添加到了 12 ( 就算不同索引 )，table 就会扩容为 32

小练习：定义一个 Employee 类，要求 name 和 age 值都相同时，就认为是相同员工，不能重复添加到 HashSet 集合中

public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add(new Employee("老猪", 18));
        hashSet.add(new Employee("老八", 20));
        hashSet.add(new Employee("老猪", 18));
//        没重写时，此时三个都加进去了,三个不同对象,哈希值都不同

//        想办法将名称和年龄相同的,就要在 Employee 类里重写
//        重写后控制台输出就只有两个加进去了
        System.out.println(hashSet);
    }


class Employee {
    private String name;
    private int age;

    public Employee(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;
    }
    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

//        想办法如果 name 和 age 相同,就返回相同的 hash 值
    @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);
    }
}

自动导入的话：
- HashSet的底层，注意：调用equals的前提是，在HashSet的一处索引位置处，有两个索引值为一样的元素 ( 就是哈希值一样 )
- 如果勾选的值相同，使用 equals() 就返回 true
- 如果勾选的值相同，使用 hashCode() 就返回同样的结果 ( 同哈希值 )

LinkedHashSet

了解

是 HashSet 的子类同实现了 Set 接口

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable { }

LinkedHashSet 底层是一个 LinkedHashMap ( HashMap 的子类 )，其维护了一个数组 + 双向链表 ( HashSet 是单向链表 )
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用双向链表来维护元素的次序，所以元素看起来是以插入顺序保存的
- 可理解为就算进入数组的索引不同，一个在 3 位置，一个在 4 位置，但放在 3 位置的节点的 prev 指向 4 位置节点，而 4 位置的 next 又指向了 3 位置的节点，这样就算是无序插入，但因为双向链表的缘故，也使得其可有序 ( 这样的话但凡不是第一个和最后一个添加进来的元素就都有四个指向 + 被指向 )
LinkedHashSet 不允许添加重复元素

底层机制说明

在 LinkedHashSet 中维护了一个 hash 表和双向链表 ( LinkedHashSet 有 head 和 tall )
每一个节点有 before 和 after 属性，这样就可以形成双向链表
在添加一个元素时，先求 hash 值，再求索引，从而确定元素在 table 的位置 ( 原则和 hashset 一致 )

这样的话，遍历 LinkedHashSet 也能确保插入顺序和遍历顺序一致

public static void main(String[] args) {
    Set set = new LinkedHashSet();
    set.add(new String("A"));
    set.add(123);
    set.add(123);
    set.add("zyz");
    System.out.println(set);
    //        1.Debugger查看： 
    //        public LinkedHashSet() {
    //              super(16, .75f, true); // 方法在HashSet里
    //           }
    //        第一次添加时，直接将数组table扩容到16，存放节点类型是LinkedHashMap$Entry($Entry:内部类Entry)
    //        数组是HashMap$Node[]，存放元素/数据是 LinkedHashMap$Entry
    //
    //        table = {HashMap$Node[]}
    //        > 0 = {LinkedHashMap$Entry}
    //        >......
    //
    //        2. LinkedHashMap 内部类完成的继承关系，Node为HashMap静态类
    //        static class Entry<K,V> extends HashMap.Node<K,V> {
    //               Entry<K,V> before, after;
    //               Entry(int hash, K key, V value, Node<K,V> next) {
    //               super(hash, key, value, next);
    //           }
    //        }
    //        3. 再次添加，after指向下一个对象，不管是不是同一数组索引，head指头，tail指尾
    //        add() 都是走父类HashSet的步骤，即上一部分所讲
}

小练习：定义一个 Car类，要求 name 和 price 值都相同时，就认为是相同元素，不能重复添加，方法同上 HashSet 练习
```
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 需要hashCode返回同hash，且equals，两者缺一不可
```