一、引言

数组的缺点：

1. 数组长度初始化时必须指定，而且一旦指定，不能修改；
2. 数组中保存的元素必须为同一类型的元素；
3. 使用数组进行增删时复杂度较高

List和Set继承关系图：

Map的继承关系图：

Collection接口有两个重要的子接口：List和Set，他两的实现子类都是单列集合。
Map接口的实现子类都是双列集合。

二、API介绍

2.1 Collection接口

public interface Collection<E> extends Iterable<E>

2.1.1 本接口的实现类的特点

2.1.2 本接口常用方法

由于接口不能被实例化，只有实现了接口的类才能被实例化。
List中存储的是对象，而不是基本数据类型。

List list = new ArrayList();
list.add("tom");
list.add(10);    // 这句相当于list.add(new Integer(10))，有个自动装箱的过程
list.add(true);

2.1.3 本接口遍历方式

1、迭代器遍历

迭代器执行原理：

迭代器实例：

IDEA中显示所有快捷键可以按Ctrl + J，即可跳出所有的快捷键。
注意：当退出while循环后，这时iterator迭代器指向最后的元素。如果强行再执行iterator.next()，会报NoSuchElementException异常。如果希望再次遍历，需要重置迭代器，即iterator = col.iterator()；
2、增强for循环

注意：增强for底层仍然是迭代器，查看源码就知道了。

2.2 List接口

2.2.1 List接口介绍

List接口的父接口和实现类：

注意：List集合中所有元素的添加顺序和取出顺序一致，且元素可重复。索引从0开始。

2.2.2 List接口常用API

2.2.3 List遍历方式

三种遍历方式都可以，即List

2.3 ArrayList

ArrayList是线程不安全的，源码中方法之前并没有加关键字synchronized关键字，此关键字专门做线程互斥的。

2.3.1 ArrayList扩容机制

重点，难点

1、

2.3.2 ArrayList底层分析

在进行Debug之前，在IDEA中设置以下debug的格式，不然进不去源码。

然后来到Data Views下的Java，去掉图中的√，可以看到好多信息，值为null的也能看到。

①、无参构造建对象

1、创建一个测试方法，进行Debug调试

// 使用ArrayList的无参构造器创建对象
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < 12; i++){
    list.add(i);
}

Ⅰ、第一次扩容

程序跳转到ArrayList.java中的164行，即ArrayList的无参构造方法，DEFAULTCAPACITY_EMPTY_ELEMENTDATA其实是本文件中的一个Object类型的空数组，elementData也是一个Object类型的空数组，即初始化elementData的容量为0，

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

👇

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData;

然后程序会对int基本数据类型进行装箱，程序会跳转到Integer.java文件的valueOf方法，valueOf方法执行完后，会再次回来for里面，然后再进去到add方法。

进入到add方法后，第一行有一个确定扩容的方法，进去看看。

来到ensureCapacityInternal方法，进入if中，常量DEFAULT_CAPACITY为10（下下图所示），if后得到的minCapacity为10，这是第一次扩容。


程序来到ensureExplicitCapacity方法，modCount是用来记录集合被修改的次数，为了防止有多个线程同时去修改容量，初始值为0。if中表示如果最小容量减去当前数组实际的大小>0，则真正执行grow方法去扩容。


扩容：程序来到grow()方法，oldCapacity为原始容量（初始为0），newCapacity为扩容后的容量，就是对原始容量1.5倍扩容，其实第一次传进来的oldCapacity为0，那1.5倍扩后，newCapacity还是为0，第一次有点特殊。

• 如果得到的新容量newCapacity比minCapacity（值为10），那新容量就干脆使用minCapacity，所以第一次进来并不是按照1.5倍扩容的，而是把minCapacity赋值给newCapacity，那么从第二次开始就用1.5倍扩容机制。
• 如果当前新容量比最大值MAX_ARRAY_SIZE还要大，就去hugeCapacity()方法中去处理。
• 最后一行代码，执行扩容，使用的是数组复制，这种方式可以保留原来数组中的数据，比如10个数据扩容到15，那先复制原数组中前10个数据到新数组，再在后面增加5个空间，值为null。

最终，得到的数组elementData里面包含10个数据，全为null值，第一次扩容成功。

grow方法执行完后，向上返回，来到add方法中第二行，此时elementData数组容量为10，size为0，此行代码表示将e这个元素放到elementData数组的0下标位置，size再自增。add方法的返回值为true，表示添加成功。

第一次的minCapacity由1变成10，来自下面这一步 minCapacity = Math._max_(**_DEFAULT_CAPACITY_**, minCapacity); 而 扩容的前提是下面这个条件满足，即当前至少需要的容量比此时数组elementData的实际容量还要大，就得去grow()方法扩容elementData了。 **if **(minCapacity - **elementData**.**length **> 0)

Ⅱ、第二次扩容

当第一次扩的容量10个全部用完后，如果再次往里面添加，那么又会进入到grow()方法里面去扩容。

👇

Ⅲ、测试代码

    @Test
    public void test01() {
        ArrayList<Integer> list = new ArrayList<>();
        // 第一次扩容，容量为10
        for(int i = 1; i <= 10; i++){
            list.add(i);
        }
        // 第二次扩容，容量为10*1.5=15
        for(int i = 11; i <= 15; i++){
            list.add(i);
        }
        // 第三次扩容，容量为15*1.5=22
        list.add(16);
        list.add(17);
    }

②、指定大小构造器

如果使用的是指定大小的构造器来建对象，则初始的elementData数组容量为指定的大小，如果需要扩容，则直接扩容elementData为1.5倍。

ArrayList<Integer> list = new ArrayList<>(8);

Debug，程序跳转到ArrayList的有参构造器，传入的参数为8，则只会执行if中的语句，创建了一个容量为8的Object类型的数组，并赋值给elementData。那么此时得到的list的size还是为0，只不过它的容量为8而已。


同样，对其执行添加操作，过程如下：



然后，程序向上返回，添加，返回true。
当list的size刚好达到初始设置容量8了，如果再往里面添加，则会采取1.5倍扩容了。




向上返回，执行添加操作，返回true。

2.4 Vector

Vector是List接口的实现子类，

如果某个集合在操作过程中只有一个线程来操作，那么此时用ArrayList是最合适的，因为效率比较高。如果某个集合在操作时有好多个线程来操作，那么建议使用Vector，因为它是线程安全的。

2.4.1 Vector 扩容机制

2.4.2 Vector底层分析

①、无参构造

对以下代码进行Debug，分析Vector的扩容机制。

        @Test
        public void test01(){
            Vector<Object> vector = new Vector<>();
            for (int i = 0; i < 10; i++) {
                vector.add(i);
            }
        }

1、程序首先跳转到Vector类的无参构造，无参构造内this(10)会调用Vector的单参构造，单参构造内又会去调用双参构造，说明Vector初始时如果是无参构造创建对象，那么默认容量就是10。

👇

2、接着程序向上返回，回到for循环里面添加元素。然后，vector也会来到valueOf()方法，对基本数据类型自动装箱，转成引用数据类型返回，回到for循环，下一次就跳转到add操作了。


3、来到add()方法，modCount表示对集合操作的次数，程序跳转到ensureCapacityHelper方法。

4、ensureCapacityHelper内部也有一个grow方法，执行真正的扩容操作，由于刚开始elementData数组就有初始值10，当vector容量没有达到10时，不会执行grow方法。

5、程序返回到add方法中，执行添加操作，并返回true。

6、当vector中刚好有10个元素了，如果再往里面添加，则会执行扩容机制了。此时至少需要11个空间来存放，单目前只有10个空间，故要进入grow方法中进行扩容。



7、grow方法如下，每次量满后，再添加的话都是两倍扩容。

②、有参构造一

Vector<Object> vector = new Vector<>(6);
//上面这行代码走的是如下构造器

跟上面无参构造类似，也是达到容量（无参初始容量是10，有参初始容量为括号中的数）后，再执行添加操作，会调用grow()方法进行扩容（容量够时，是不会调用grow方法的）。

👇

👇

👇

👇

👇

以上流程就是当初始容量设为6，且vector中容量已满，再往内部添加第7个时，就会调用grow()方法进行两倍扩容，容量扩到12。

③、有参构造二

// 创建对象时直接指定初始容量为6，每次扩容大小为5
Vector<Object> vector = new Vector<>(6, 5);

Debug过程如下所示：
1、调用如下双参构造器

2、程序来到for里面，执行add操作，首先将基本数据类型自动装箱。



3、进入add方法，初始容量为6，未填满之前，不用扩容，即grow方法不执行。


4、添加元素到elementData数组，并返回true。

5、添加6个元素后，再来看看如何扩容。



6、添加第7个元素时，至少需要7个容量，但elementData数组长度为6，就得调用grow方法扩容。由于刚开始使用的是双参构造器，指定了每次扩容的大小，故扩容后的大小不是原容量的两倍了，而是oldCapacity+capacityIncrement的值（具体看三目运算符）

2.5 LinkedList

2.5.1 简介

手写链表，定义一个类，表示Node对象

class Node{
    public Object item;
    public Node next;
    public Node pre;
    public Node(Object name) {
        this.item = name;
    }
}

编写测试类

@Test
public void test(){
    Node jack = new Node("jack");
    Node tom = new Node("tom");
    Node mary = new Node("mary");
    jack.next = tom;
    tom.next = mary;
    mary.pre = tom;
    tom.pre = jack;
    Node first = jack;
    Node last = mary;
    while(true){
        if(first == null)    break;
        sout(first);
        first = first.next;
    }
    while(true){
        if(last == null)    break;
        sout(last);
        last = last.pre;
    }
}

2.5.2 LinkedList底层

①、添加操作

    @Test
    public void test01(){
        LinkedList<Object> list = new LinkedList<>();
        list.add(10);
        list.add(100);
    }

分析以上代码执行过程，了解链表。
1、首先调用LinkedList的无参构造器，得到的list对象封装了四个属性，参考下图红色方框。

2、接着，对基本类型进行自动装箱并返回，再调用add方法

3、来到add方法，add方法内调用linkLast方法，linkLast中有一个创建结点newNode的过程（一个结点含有三个属性，item、next和prev），此时newNode的值item为e，next和prev都是null。那么插入第一个结点的时候，first和last都指向这个newNode，size表示此时链表长度，modCount表示修改链表的次数（防止多个线程一起操作链表）。


4、回到add方法，返回true，第一个结点添加操作结束。

5、继续添加第二个结点，自动装箱，调用add方法。

6、add内调用linkLast方法执行插入操作。


7、那么此时first指向第一个元素，last指向第二个（最后一个）元素，第一个元素的prev为空，最后一个元素为next为空。

②、删除操作

    @Test
    public void test01(){
        LinkedList<Object> list = new LinkedList<>();
        list.add(10);
        list.add(100);
        list.add(50);
        list.add(10);
        // 默认remove()方法删除链表第一个
        list.remove();
        list.remove(2);
    }

1、在remove()方法处断点，remove方法会去调用removeFirst方法，此方法又会去调用unlinkFirst()，传入参数为首元节点（是个Node类型）

2、unlinkFirst(Node f)方法如下，返回值为所删节点的item值，不断往上返回。


3、按照下标删除，首先判断下标index是否满足条件。

list.remove(2);

4、检查完index后，得调用unlink()方法，但括号里面还有一个方法，node(int index)：表示找到下标为index的结点。查找过程如下面大图所示：

• 如果下标index 小于 表长一半，则令x指向first，不断右移x，直到移到index位置；
• 如果下标index 大于等于 表长一半，则令x指向last，不断左移x，直到移到index位置；

5、执行unlink方法，删除x结点，返回值为删除节点的值。

2.5.3 ArrayList vs LinkedList

2.6 Set接口

2.6.1 基本介绍

2.6.2 基本使用

@Test
public void test(){
    Set<Object> set = new HashSet<>();
    set.add("zhangsan");
    set.add("lisi");
    set.add("wangwu");
    set.add("zhaoliu");
    set.add(zhangsan);
    set.add(null);
    set.add(null);
    System.out.println(set);
}
// 运行结果：[null, lisi, zhaoliu, zhangsan, wangwu]

注意：

• set接口的实现类对象，不能存放重复的元素，可以添加null值，但只能添加一个；
• se接口的实现类对象，存放数据是无序的【添加的顺序和取出的顺序不同】；
• 虽然取出的顺序不是添加的顺序，但是它是固定的，即每次遍历set得到的结果都相同；
• set中没有索引index，不能索引遍历（传统for循环），set中没有get(index)这个方法。

// set的遍历方式：迭代器 + 增强for
Iterator iterator = set.iterator();
while(iterator.hasNext()) {
    Object obj = iterator.next();
    sout(obj);
}
for(Object obj : set){
    sout(obj);
}

2.7 HashSet

在执行add方法后，会返回一个boolean值，如果添加成功，返回true，否则，返回false。

        Set<Object> set = new HashSet<>();
        System.out.println(set.add("张三"));
        System.out.println(set.add("李四"));
        System.out.println(set.add("王五"));
        System.out.println(set.add("马六"));
        System.out.println(set.add("Tom"));
        System.out.println(set.add("Cat"));
        System.out.println(set.add("张三"));        // false ，其余全是true
        System.out.println(set);    //    [李四, 张三, 马六, Tom, 王五, Cat]

由于HashSet底层是HashMap，HashMap底层是（数组+链表+红黑树），下面先来模拟一下HashSet的底层：

// 结点，存储数据
class Node{
    Object item;
    Node next;
    public Node(Object item, Node next){
        this.item = item;
        this.next = next;
    }
}
public class HashSetStructure{
    @Test
    public void test(){
        // 创建一个数组，数组类型是Node[]
        Node[] table = new Node[16];
        // 创建结点
        Node tom = New Node("tom", null);
        table[1] = tom;
        Node jack = New Node("jack", null);
        tom.next = jack;
        Node rose = New Node("rose", null);
        jack.next = rose;
        Node lucy = New Node("lucy", null);
        rose.next = lucy;
    }
}

2.7.1 底层分析(重难点)

对以下代码进行Debug分析。

    @Test
    public void test(){
        Set<Object> set = new HashSet<>();
        System.out.println(set.add("张三"));
        System.out.println(set.add("李四"));
        System.out.println(set.add("王五"));
        System.out.println(set.add("张三"));
        System.out.println(set.add("Tom"));
        System.out.println(set.add("Cat"));
        System.out.println(set.add("张三"));
        System.out.println(set);
    }

①、添加第一个

1、首先HashSet初始化，其实底层是HashMap。

2、返回到主方法，开始添加值。来到add方法，首先调用put方法，key为”张三”，value为定义的Object类型对象PRESENT。put方法中调用putVal方法，这里有一个hash(key)：

    static final int hash(Object key) {
        int h;
        // 这么写的目的是为了让不同的key尽量得到不同的哈希值，避免碰撞做了这个算法
        // 得到的哈希值并不是key的hashCode，还对hashCode进行^ (h >>> 16)这一处的
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

• 如果传进来的key不为null，则求出key的hashcode并返回；
• 如果传进来的key为null，则返回0；

map.put()方法返回的值如果是空，则代表插入成功，则add方法往上返回true；否则，如果put方法返回的不是null，则代表插入失败，那么add方法往上返回false。



3、来到V putVal()方法，这个方法是精髓。

    /**
        hash：hash(key)返回的哈希值；key：添加的值，如"张三"；value：Object类型变量
        key：插入的值，如“张三”
        value：Object类型
    */
    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结点的数组，初始时为null
        // 如果当前table为null或大小为0，则执行resize进行第一次扩容，扩容后大小为16
        if ((tab = table) == null || (n = tab.length) == 0)
            // 第一次resize()返回的值为16，tab是一个容量为16的Node型数组，n为16
            n = (tab = resize()).length;
        // 根据key得到的hash去计算该key应该存放在table表的哪个索引位置i
        // 并把此索引位置i的对象赋给辅助变量p
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 如果p为null，表示此索引还未存放元素，就创建一个Node结点，把结点放在tab[i]位置
            // 该结点hash为key的哈希值，key为“张三”，value为Object类的值，next指向null
            tab[i] = newNode(hash, key, value, null);
        else {
                ....添加第一个元素时这里不会执行，我把它省了。
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改次数加一
        ++modCount;
        // size加1，如果此时size达到threshold（第一次为12）时，执行resize进行扩容
        if (++size > threshold)
            resize();
        // 这是个空方法，在这里主要是为了让HashMap的子类去实现这个方法，
        afterNodeInsertion(evict);
        // 返回null代表插入成功
        return null;
    }

上面代码调用的方法如下：

    final Node<K,V>[] resize() {
        // 将table赋给一个Node类型数组oldTab，初始table为null
        Node<K,V>[] oldTab = table;
        // 第一次oldCap为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // threshold是一个全局变量，初始为0
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 以下if结构，第一次会进入到else中
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 将等式右边的常量（默认初始容量）16赋给newCap
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 0.75 * 16 = 12，得到的newThr是12，即总共16个空间中，如果使用了12个的话，就要开始
            // 扩容了，防止多个线程同时执行添加操作，就会导致阻塞，所以就设置了个加载因子0.75.
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 将12赋值给threshold，临界值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // newTab数组现在容量为16了，因为newCap的值为16
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 把newTab赋值给table，此时table的容量也为16，不过全为null
        table = newTab;
        // oldTab为null，这里if不会执行，直接返回newTab
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        // 返回newTab，容量为16，值为null
        return newTab;
    }

newNode构造方法：

    // 创建一个新节点
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

②、添加第二个

以上是添加第一个元素时执行的流程，下面分析添加第二个元素时的操作：
1、来到HashSet的add方法，跳转到HashMap的put()方法，因为HashSet底层就是HashMap。put方法会去调用putVal方法，括号里面有个hash(key)表示将传入的值key转化成哈希值。



2、来到了putVal方法，流程如下，插入成功则返回true【以下隐藏了else】

③、添加重复元素

以上是添加第二个元素时执行的流程，下面分析添加重复元素时的操作：
1、继续插入”张三”元素，来到putVal方法：

        // p所指的那个tab[i]为空，执行if，否则，有元素了，就执行else
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 初始化变量
            Node<K,V> e; K k;
            // 如果p指向的tab[i]的hash值跟待插的值的hash值相等，且p指向的tab[i]的key值跟待插入的
            // key相等，或待插的key非空且equals那个p指向的tab[i]的key值，则把p的值赋给e
            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，说明map中已存在该元素，返回此tab[i]的value，即oldValue
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }

2、由于putVal方法返回的是oldValue，那么下面的add方法就返回false了，插入失败。

小结一下： 在插入重复元素时，比较的规则如下【全在HashMap.java中的putVal方法中】：

1. 先获取待插元素的哈希值hash；
2. 对哈希值进行运算，得出一个索引值i即为要存放在哈希表tab中的下标；
3. 如果该位置tab[i]没有其他元素，则直接存放；如果tab[i]中已有其他元素，则需要进行hash值和equals判断，如果相等，则不再添加，否则不相等，则以链表的方式添加。

注意：equals方法可以由程序员重写来确定的，不能简单理解为就是比较他两的内容。因为每个类都可以有自己的equals方法，equals方法具体怎么比较，有自己来决定。举个例子，比如在添加一个Person对象时，你可以认为person的名字和年龄相同，就是同一个人，或者person的名字和薪水相同，就是同一个人。不能简单地理解为是字符串比较，因为String类重写了equals方法，如果两字符串内容相同，就是同一个String，但并不是所有的类都是按照这个标准来的。

HashSet的底层是HashMap。另外，第一次添加时，table数组会扩容到16，加载因子（loadFactor）为0.75，那么临界值threshold=16loadFactor=12，即如果table数组+链表中使用了临界值12个容量，就会扩容两倍，新的容量为162=32，那么新的临界值为320.75=24，依此类推。
在jdk 1.8中，如果一条链表（以数组为头结点）的元素个数到达TREEIFY_THRESHOLD（默认是8），并且table数组的大小 >=_*MIN_TREEIFY_CAPACITY_（默认64），就会进行树化（红黑树），否则仍然采用数组的达到threshold后二倍扩容机制。

④、链表机制

现在来分析链表的连接机制。
想办法让添加的数据全部都连在同一个链表上，那么最关键的是算出来的hash(key)要一样的，然后得到同样的table索引i，只要保证hash值相同，添加数据的内容不同就可以连成一个链表。

class Dog {
    private String name;
    private int age;
    public Dog(String name, int age){
        this.name = name;
        this.age = age;
    }
    @Override
    public int hashCode() {
        // 这里改成hashCode返回值是一样的，那每次添加Dog对象就可连在同一个链表
        return 10;
    }
    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

看下putVal中的一段代码：

    // 待插结点通过hash值得到的下标索引如果此时已经有元素了（类似冲突），则执行else
    else {
            Node<K,V> e; K k;
            // 这个if判断的是p所指向的数组中下标为i位置（链表首元节点）和待插入的数据是否一模一样
            //     ，如果一模一样，则执行这个if
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果此时p所指向的数组中下标为i位置的结点已经树化为红黑树了，执行else if
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 把待插结点插入到链表结尾（以p所指向的数组中下标为i位置的结点为头结点）
            else {
                // binCount用于记录以tab[i]为头的链表中结点的下标，就是p的下标（从0开始）
                for (int binCount = 0; ; ++binCount) {
                    // 如果p（p指向首元结点，就是数组中索引）的next为null，这一步后e指向链表第二
                    // 个结点（如果存在），如果第二个节点不存在执行if，不断循环，p和e后移，
                    // 直到e指向null了(这是p指向链表最后一个节点)，才执行此if
                    if ((e = p.next) == null) {
                        // 将待插结点挂载到p的后面
                        p.next = newNode(hash, key, value, null);
                        // 如果此时链表长度大于等于8，即binCount为7时，就要进入if了
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果e不为空，则执行这个if
                    // e从链表第二个结点开始后移，判断待插结点是否跟链表中元素有重复。
                    //如果重复了，就跳出循环，否则，p指向e（相当于p后移）
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

注意： ++modCount; if (++size > threshold)
resize(); 这段代码是HashMap.java中的putVal()方法的，size表示【数组+链表】的元素个数，不是单指插在table表的节点个数，只要插入【数组+链表】的结点达到threshold，就会去调用resize()方法，进行二倍扩容。请看下面实例：

已经往【数组+链表】结构插入了12个值，threshold也为12，如果再插入一个值，那么table表会两倍扩容了。

2.7.2 HashSet练习

题目1：

必须知道的知识：

解答：

// Employee类中已重写hashCode和equals方法，在此认为两对象的name和age相等就是同一个对象
class Employee {
    private String name;
    private int age;
    public Employee(String name, int age) {
        this.name = name;
        this.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);
    }
    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
    @Test
    public void test(){
        Set<Object> set = new HashSet<>();
        Employee tom = new Employee("tom", 15);
        Employee jack = new Employee("jack", 18);
        Employee tom1 = new Employee("tom", 15);
        set.add(tom);
        set.add(jack);
        set.add(tom1);
        System.out.println(set);
    }
输出：
    [Employee{name='jack', age=18}, Employee{name='tom', age=15}]
可以看到tom1对象没有添加进去，Employee类中重写了hashCode和equals方法后，则认为name和age一样的
两对象是同一个，故认为重复，第二个重复的加不进去。如果不重写hashCode和equals方法，则能加进去，如：
    [Employee{name='tom', age=15}, Employee{name='jack', age=18}, Employee{name='tom', age=15}]

题目2：

解答：

class Employee_ {
    private String name;
    private int sal;
    private MyDate birthday;
    public Employee_(String name, int sal, MyDate birthday) {
        this.name = name;
        this.sal = sal;
        this.birthday = birthday;
    }
    // 重写hashCode和equals方法，当name和birthday相同时，认为是相同员工，不能添加到HashSet集合
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee_ employee_ = (Employee_) o;
        return Objects.equals(name, employee_.name) && Objects.equals(birthday, employee_.birthday);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, birthday);
    }
    @Override
    public String toString() {
        return "Employee_{" +
                "name='" + name + '\'' +
                ", sal=" + sal +
                ", birthday=" + birthday +
                '}';
    }
}
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;
    }
//    重写hashCode和equals方法，当年月日一样，则认为是同一个人，为Employee_类做准备
    @Override
    public int hashCode() {
        return Objects.hash(year, month, day);
    }
    @Override
    public String toString() {
        return "MyDate{" +
                "year=" + year +
                ", month=" + month +
                ", day=" + day +
                '}';
    }
}
    @Test
    public void test() {
        Employee_ e1 = new Employee_("curry", 1000, new MyDate(2000, 10, 1));
        Employee_ e2 = new Employee_("curry", 1000, new MyDate(2000, 10, 1));
        Employee_ e3 = new Employee_("curry", 5000, new MyDate(2000, 10, 1));
        HashSet<Object> set = new HashSet<>();
        set.add(e1);
        set.add(e2);
        set.add(e3);
        System.out.println(set);
    }
// 输出结果：
    [Employee_{name='curry', sal=1000, birthday=MyDate{year=2000, month=10, day=1}}]
    只有第一个添加成功

2.8 LinkedHashSet

LinkedHashSet示意图：

2.8.1 底层分析

首先进行初始化得到set对象，LinkedHashSet底层还是调用了LinkedHashMap。

调用add()方法，再继续调用put方法，put再调用核心方法putVal，这个流程跟HashSet一模一样。

上面putVal会调用afterNodeInsertion(boolean evict)方法，

添加第二个元素，值跟第一个添加的一样，那么在putVal方法中执行过程如下。

添加完5个元素后，双向链表基本建成，head指向双向链表的首元节点（第一个插入的结点），tail指向双向链表的尾结点（最后一次插入的结点），

2.9 Map

回顾一下HashSet，HashSet底层使用的是HashMap，即HashSet在保存数据时也是基于Key-Value键值对存储的，只是在HashSet中，所有添加的Key的Value都是一个常量，即源码中的PRESENT 。
private static final Object _PRESENT _= new Object();

2.9.1 Map接口特点及API

Map存放数据的key-value，一对key-value是放在一个HashMap$Node中的，又因为Node实现了Entry接口，有些书上也说一对key-value就是一个Entry。
Map<String, Integer> map = new HashMap<>();对这句话Debug，过程如下：
先调用HashMap的无参构造，加载因子为0.75，

执行 map.put("张三", 28);这句代码，先把int类型28自动装箱成Integer类型，再进入HashMap.java中的put方法，然后再调用putVal方法，这跟HashSet添加一个样。



创建结点，调用newNode()方法newNode(int hash, K key, V value, Node<K,V> next)，newNode再去初始化，调用构造器进行实例化。Node类是一个静态内部类，即每次添加键值对时，key-value都是保存在一个Node里面的（Node内部有四个属性），

注意： 为了方便程序员遍历，即获取map中所有的key和所有的values，Set集合里面存放了所有的key，Collection接口的一个实现子类里面存放了所有的values。但真正的key和value如上图所示，是放在HashMap$Node里面的，而Set集合和Collection集合只是指向了对应Node而已。

Map体系继承图：

Map接口常用方法：

2.9.2 Map接口遍历方式

回顾一下： JDK设计者为了使程序员遍历Map比较方便，可以使用一个Set把Map中的key取出来，但Set其实指向的是HashMap$Node结点中的key，value也可以使用一个Collection取出来，同样，Collection也指向的是hashMap&Node结点中的value。

        Map<String, Integer> map = new HashMap<>();
        map.put("张三", 28);
        map.put("lisi", 36);
        map.put("奥巴马", 55);
        map.put(null, 18);
        map.put("curry", 33);
        map.put("god", null);

遍历方式一：for (Object key : keySet){}

        Set<String> keySet = map.keySet();
        // 增强for遍历keySet
        for (Object key : keySet) {
            System.out.println(key + ": " + map.get(key));
        }

遍历方式二：keySet.iterator();

         // 迭代器遍历keySet
        Iterator<String> iterator = keySet.iterator();
        while(iterator.hasNext()){
            String key = iterator.next();
            System.out.println(key + ": " + map.get(key));
        }

遍历方式三：map.entrySet();

        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

遍历方式四：entrySet.iterator();

        Iterator<Map.Entry<String, Integer>> iterator = entrySet.iterator();
        while(iterator.hasNext()){
            Map.Entry<String, Integer> entry = iterator.next();
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

2.9.3 HashMap小结

2.10 HashTable