Java复习（集合）涉及源码

Java复习（集合）

（前情提要：暂时不使用泛型，学习于韩顺平老师）

（黄色标注是学习的时候的想法以及总结；三问号表示想法未加验证，不可轻信；）

主要内容：

Java集合框架概述
Collection接口方法
Iterator迭代器接口
Collection子接口一：List
Collection子接口二：Set
Map接口
Collection工具类

一、Java集合框架概述

第一个想法：集合是用于存储数据的，那么最最基本的方法就是对数据的增、删、查、改。

（概述只是让我们有一个大概地认识，真实记住还是接下来的学习）

一方面，面向对象语言对事务的体现都是都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。另一方面，使用Array存储对象方面具有一些弊端，而 Java 集合就像一种容器，可以动态地把多个对象地引用放入容器中。

数组在内存存储方面地特点：
- 数组初始化以后，长度就确定了
- 数组声明类型时，就决定了进行元素初始化时的类型
数组在存储数据方面地弊端：
- 数组初始化以后，长度就不可变了，不便于扩展
- 数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。同时不能直接获取存储元素个数。
- 数组存储地数据是有序地、可以重复地。—>存储数据地特点单一

Java 集合类可以用于存储数量不等地多个对象，还可用于保存具有映射关系地关联数组。

package com.zhang.java1;


public class CollectionTest {
}

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

Collection接口：单列数据，定义了存储一组对象的方法的集合

List：元素有序、可重复的集合
Set：元素无序、不可重复的集合

Map接口：双列数据，保存具有映射关系 “key-value 对” 的集合

Java 集合两大接口继承树

虚线代表实现

Collecion接口继承树：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PXihO5OV-1635075954196)(D:Program FilesJava复习集合image-20210515130307857.png)]

Map接口继承树：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fawrCjGE-1635075954205)(D:Program FilesJava复习集合集合.assetsimage-20211022173103537.png)]

package com.zhang.java1;


public class CollectionTest {
}

二、Collection接口方法（有15个）

为什么不直接学习 List接口的方法和 Set接口的方法？

因为 List接口和 Set接口都是继承 Collection接口的，所以 Collection接口下的api，也就是方法，适用于 List接口和 Set接口。

Collection接口方法

添加（并集）
add(Object e)：将元素e添加到集合中
addAll(Collection coll)：将集合coll的元素添加到集合中
获取有效元素的个数
int size()
清空集合中
void clear()
判断是否为空集合
boolean isEmpty()
是否包含某个元素
（这两个方法使用的思想其实是高中时期学的包含 ⊆ ，底层使用的是equals()方法）

（存入的元素需要重写equals()方法）
boolean contains(Object obj)：通过元素的equals方法来判断是否是同一对象
boolean containsAll(Collection c)：也是调用元素的equals方法来比较的。拿两个集合的元素挨个比较，封装类自动选择Collection c 版本的。
删除（差集）
一定要重写equals()方法，不得话同内容，不同地址，也删除不掉。

底层使用的是equals()方法，和contains()方法差不多，只不过一个是查到返回true，一个是查到就删除

boolean remove(Object obj)：通过元素的equals方法判断是否是要删除的哪个元素。只会删除找到的第一个元素，只删除一个。
boolean removeAll(Colleciotn coll)：取当前集合的差集
取两个集合的交集

差不多就是用三次差集，两次并集：(A+B)-((A-B)+(B-A)) 按照这个思想，底层使用的应该就是removeAll()，而removeAll()底层使用的就是equals()方法？？？

boolean retainAll(Collection c)：把交集的结果存在当前集合中，不影响集合C
集合是否相等

对List集合来说，排序也是对比的条件
Boolean equals(Object obj)

转成对象数组
Object[] toArray()
拓展：

	@Test
    public void test4(){
        //拓展：数组也可以转化为集合：调用Arrays类的静态方法asList(); （数组对应的Collection集合是List集合）
        List list = Arrays.asList(new String[]{"aa", "bb", "cc"});
        System.out.println(list);
        //陷阱（看泛型可避免）
        List ints = Arrays.asList(new int[]{123, 456});
        System.out.println(ints.size());//1  直接使用int[]有可能会将整个数组当成一个集合元素
        List list1 = Arrays.asList(123, 456);
        System.out.println(list1);//[123, 456]  直接写数字则不会
        List list2 = Arrays.asList(new Integer[]{123, 456});
        System.out.println(list2.size());//2  使用Integer[] 包装数组也可以解决，推荐使用包装类
    }

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

Collection接口总方法测试代码

（复制放在idea里面，可能会看的更清除一点）

package com.zhang.java1;

import org.junit.jupiter.api.Test;

import java.util.*;


public class CollectionTest {
    @Test
    public void test1(){
        //为什么不new Collection()？
        //因为它是一个接口，需要的是实现类，暂且使用它的实现了ArrayList()。
        Collection coll = new ArrayList();

        //1、add(Object e)：将元素e添加导集合coll中
        coll.add("AA");
        coll.add("bb");
        coll.add(123);//自动装箱
        coll.add(new Date());

        //2、size()：获取添加的元素的个数
        System.out.println(coll.size());//4

        //3、addAll(Collection coll2);将coll2集合中的元素添加到当前的集合中，并集
        Collection coll2 = new ArrayList();
        coll2.add(456);
        coll2.add("CC");
        coll.addAll(coll2);
        System.out.println(coll.size());//6
        System.out.println(coll);

        //4、clear()：清空Collection集合中的元素
        coll.clear();

        //5、isEmpty()：判断当前集合是否为空
        System.out.println(coll.isEmpty());

        //6、contains(Object obj)：调用的是equals()方法，如果对比的对象没有重写equals()方法，那就是使用”==“对比，重写的话就是只对比内容
        //我们判断时会调用obj对象所在类的equals()。通常的自定义类的obj都要重写equals()方法
        coll.add(new String("ss"));
        System.out.println(coll.contains(new String("ss")));//true

        //7、containsAll(Collection coll)：查看是否包含coll集合
        coll.add(123);//自动装箱
        coll.add(456);
        Collection coll3 = Arrays.asList(123,456);
        System.out.println(coll.containsAll(coll3));//true
    }

    @Test
    public void test2(){
        Collection coll = new ArrayList();
        //1、add(Object e)：将元素e添加导集合coll中
        coll.add("AA");
        coll.add("bb");
        coll.add(123);
        coll.add(123);//自动装箱
        coll.add(456);
        coll.add(456);

        //7、remove(Object obj):对集合移除obj元素。差集
        //底层使用的是equals()方法，和contains()方法差不多，只不过一个是查到返回true，一个是查到就删除
        coll.remove(123);
        System.out.println(coll);

        //8、removeAll(Collection coll2)：从当前集合中移除coll2中所有元素
        Collection coll2 = Arrays.asList(456,123);
        coll.removeAll(coll2);
        System.out.println(coll);
    }

    @Test
    public void test3(){
        Collection coll = new ArrayList();
        //1、add(Object e)：将元素e添加导集合coll中
        coll.add("AA");
        coll.add("bb");
        coll.add(123);//自动装箱
        coll.add(456);

        //8、retainAll(Collection coll2)：交集：获取当前集合和coll集合的交集，并修改当前集合coll
        //差不多就是用三次差集，两次并集：(A+B)-((A-B)+(B-A)) 按照这个思想，底层使用的应该就是remove()，而remove()底层使用的就是equals()方法
        Collection coll2 = Arrays.asList(123,456,789);
        //coll.retainAll(coll2);
        System.out.println(coll);

        //9、equals(Object obj)：对比两个集合，要向返回true，需要当前集合和形参集合的元素都相同。对List集合来说排序也是对比的条件
        Collection coll1 = new ArrayList();
        //1、add(Object e)：将元素e添加导集合coll中
        coll1.add("AA");
        coll1.add("bb");
        coll1.add(123);//自动装箱
        coll1.add(456);
        System.out.println(coll.equals(coll1));
    }

    @Test
    public void test4(){
        Collection coll = new ArrayList();
        //1、add(Object e)：将元素e添加导集合coll中
        coll.add("AA");
        coll.add("bb");
        coll.add(123);//自动装箱
        coll.add(456);

        //10、hashCode()：返回当前对象的哈希值
        System.out.println(coll.hashCode());

        //11、集合 --> 数组：toArray()
        Object[] array = coll.toArray();
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
        //拓展：数组也可以转化为集合：调用Arrays类的静态方法asList(); （数组对应的Collection集合是List集合）
        List list = Arrays.asList(new String[]{"aa", "bb", "cc"});
        System.out.println(list);
        //陷阱
        List ints = Arrays.asList(new int[]{123, 456});
        System.out.println(ints.size());//1  直接使用int[]有可能会将整个数组当成一个集合元素
        List list1 = Arrays.asList(123, 456);
        System.out.println(list1);//[123, 456]  直接写数字则不会
        List list2 = Arrays.asList(new Integer[]{123, 456});
        System.out.println(list2.size());//2  使用Integer[] 包装数组也可以解决，推荐使用包装类

        //12、iterator()：返回iterator接口的实例，用于遍历集合元素。放在IteratorTest.java中测试
    }

}

三、Iterator迭代器接口（是用来遍历Collection集合的）

Iterator对象称为迭代器（设计模式的一种），主要用于遍历 Collection 集合中的元素。

==GOF给迭代器模式的定义为：提供一种方法访问一个容器（container）对象中各个与那苏，而又不需要暴露该对象的内部细节。迭代器模式，就是为容器而生。==类似于“公交车上的售票员”、“火车上的乘务员”、“空姐”。

Collection接口继承Java.lang.Iterable，该接口有一个iterator()方法，那么所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了Iterator接口的对象。

Iterator 仅用于遍历集合，Iterator 本身并不提供承装对象的能力。如果需要创建Iterator 对象，则必须有一个被迭代的集合。

集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

内部的方法：hasNext() 和 next() 的使用

public class IteratorTest {

    @Test
    public void test1(){
        Collection coll = new ArrayList();
        //1、add(Object e)：将元素e添加导集合coll中
        coll.add("AA");
        coll.add("bb");
        coll.add(123);//自动装箱
        coll.add(new Date());

        Iterator iterator = coll.iterator();
//        //方式一
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        //迭代器也存在异常：NoSuchElementException 没有元素
//        System.out.println(iterator.next());

        //方式二：不推荐
//        for (int i = 0; i < coll.size(); i++) {
//            System.out.println(iterator.next());
//        }

        //方式三（next()和hasNext()搭配用）：推荐
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

    }
}

迭代器Iterator接口的执行原理

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rONs57S1-1635075954210)(D:Program FilesJava复习集合image-20210518114635474.png)]

其中 Iterator iterator = coll.iterator(); 创建的对象更像是创建一个指针，

刚创建出来的 iterator 对象指向是空的，

而 hasNext() 方法判断的是当前 iterator 对象指针的下一个集合位置是否有元素，

当使用 next() 方法的时候 iterator 对象指针下移，并返回下移的集合位置上的元素

package com.zhang.java1;


public class IteratorTest {

    @Test
    public void test1(){
        Collection coll = new ArrayList();
        //1、add(Object e)：将元素e添加导集合coll中
        coll.add("AA");
        coll.add("bb");
        coll.add(123);//自动装箱
        coll.add(new Date());

        Iterator iterator = coll.iterator();

        //错误示范：1.直接使用iterator.next()判断。
        //原因：iterator.next()会下移指针，所以这会判断时候下移一次，输出的时候下移一次，
        //     并且会出现NoSuchElementException 没有元素异常
//        while(iterator.next()!= null){
//            System.out.println(iterator.next());
//        }

        //错误示范：2、在判断中创建iterator迭代器
        //原因：coll.iterator()返回的是一个新的指向开头的指针，
        //所以每判断次都会创建一个新的并执行开头的指针，死循环了。
        while(coll.iterator().next()!= null){
            System.out.println(coll.iterator().next());
        }

    }
}

Iterator中的remove()方法

Iterator可以删除集合的元素，但是是遍历过程中通过迭代器对象的remove()方法，不是集合对象的remove()方法。

如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，在调用remove 都会报 IllegalStateException异常。（也就是指向集合中的元素为 null，就会报异常）

package com.zhang.java1;


public class IteratorTest {
    //测试Iterator中的remove()方法
    @Test
    public void test3(){
        Collection coll = new ArrayList();
        //1、add(Object e)：将元素e添加导集合coll中
        coll.add("AA");
        coll.add("bb");
        coll.add(123);//自动装箱
        coll.add(new Date());

        Iterator iterator = coll.iterator();
        while (iterator.hasNext()){
            Object next = iterator.next();
            if ("bb".equals(next)){
                iterator.remove();
            }
        }
        Iterator iterator1 = coll.iterator();
        while (iterator1.hasNext()){
            System.out.println(iterator1.next());
        }

    }
}

使用 foreach 循环遍历集合元素

Java 5.0 提供了 foreach 循环迭代访问 Collection 和数组。

遍历操作不需获取Collection或数组的长度，无需使用索引访问元素。

遍历集合的底层调用Iterator完成操作

foreach还可以用来遍历数组

package com.zhang.java1;


public class ForTest {
    @Test
    public void test1(){
        Collection coll = new ArrayList();

        //1、add(Object e)：将元素e添加导集合coll中
        coll.add("AA");
        coll.add("bb");
        coll.add(123);//自动装箱
        coll.add(new Date());

        //for(集合内元素的类型 局部变量 ：集合对象)
        //原理：取 coll集合 中的元素赋值给 局部变量0 ，内部使用的也是迭代器（将迭代器看成指针）
        for (Object o : coll) {
            System.out.println(o);
        }
    }

    //对数组进行增强for循环
    @Test
    public void test2(){
        int[] ints =new int[]{1, 2, 3, 4, 5};
        //for(数组内元素的类型 局部变量 ：数组对象)
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

    //笔试练习题
    @Test
    public void test3(){
        String[] strings = new String[] {"mm", "mm", "mm"};
//        for (int i = 0; i < strings.length; i++) {
//            strings[i]="gg";
//        }//gg

        for (String string1 : strings) {
            string1 ="gg";
        }//mm
        for (String string : strings) {
            System.out.println(string);
        }

    }

}

四、Collection子接口一：List

List接概述

鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组。

List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。

List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

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

特点

List集合类中元素是有序（添加和取出顺序一致）、即可重复
每个元素都有对应的索引，支持索引
每个元素都有一个整数型的序号记载存储位置，根据序号存取容器中的元素

特有方法

只要涉及到索引，索引一定要存在，不得话抛异常

addAll(index,Collection)：在特定位置上添加元素，元素不会被覆盖，会被推移到后面。
indexof(Object object)：返回object元素首次出现的位置
lastIndexOf(Object object)：返回object元素最后一次次出现的位置
set(index,Object object)：替换元素，
subList(bdginIndex,EndIndex)：截断集合返回小集合，前闭后开

    @Test
    public void test1(){

        List list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(String.valueOf(i));
        }
        System.out.println(list);
        list.add(1,"韩顺平");
        System.out.println(list);
        System.out.println("5："+list.get(4));
        list.remove(5);
        System.out.println(list);
        list.set(6,"修改第7个元素");
        System.out.println(list);
    }

ArrayList、linkedList、Vector的三种遍历方式

	@Test
    public void ListFor(){
        List list = new ArrayList<>();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        //1、迭代器遍历
        Iterator iterator = list.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //2、增强for
        for (Object o : list) {
            System.out.println(o);
        }
        //3、原生
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

ArrayList注意事项

可以放任何值包括null，并且可以放很多个
由数组实现的数据存储的
等同于Vector，只有一个不同ArrayList线程不安全，操作方法上面没有加锁

底层源码分析

结论：

ArrayList维护了一个Object类型的数组elementData，transient Object[] elementData；//transient 关键字表示瞬间的，加了这个关键字，将不被序列化
当创建ArrayList对象时，如果使用的是无参构造器，则初始化elementData容量为0，第一次添加，则扩容elementData为10，如需要再次扩容，则扩容为原来的1.5倍。
如果使用的是指定大小的构造器，则初始elementData容量为指定的大小，如果需要扩容，则直接扩容为原来的1.5倍

为什么扩容是1.5倍？

准确的来说第一次是10，第二次才是原数组的1.5倍。

扩容操作使用的是对原数组移位来增加的运算，而二进制就是右移1位，就是除以2，加上原数组就是原数组的1.5倍。

并且其中扩容操作完成后，实际的数组操作是使用 Arrays.copyOf() 方法，进行数组的复制。

都是对原生elementData数组的操作

每次添加都有个size计数，size是需要的数量，只有这个数量大于实际长度才会进行扩容操作

一、List子接口二：Vector

Vector介绍

Vector定义：

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

Vector底层也是创建一个对象数组：protected Object elementData[]
Vector是线程同步，即线程安全的，它的操作方法都加入了synchronized关键字
开发中考虑线程同步安全，使用Vector

注意：Vector的扩容是原来的2倍

源码解读

调用无参构造，也会被转接到有参构造方法中，其中参数为10

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8hR6BjPV-1635075954214)(D:Program FilesJava复习集合集合.assetsimage-20211019135853654.png)]

其中的扩容机制

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CLuKqHRe-1635075954216)(D:Program FilesJava复习集合集合.assetsimage-20211019140757963.png)]

扩容算法中如果没有设置capacityIncrement的值，那就直接两倍，设置了增长值，就从增长值加上原先的值

好像其中的增长值不可更改，一直为0，所以vector的默认扩容是原来的两倍

二、List实现类三：linkedList

特点

底层实现了双向链表和双端队列特点
可以添加任何元素包括null，并且可重复
是线程不安全的

底层机制：

linkedList底层维护了一个双向链表
对于linkedList有first和last属性，分别指向首节点和尾节点
对于每个节点对象Node，里面有指向前一个的节点对象和指向后一个的节点对象，还有item存储属性
对于链表增删改非常的方便

底层源码

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jcvOy2gZ-1635075954217)(D:Program FilesJava复习集合集合.assetsimage-20211019143546321.png)]

无参构造创建size为0的linkedList对象，其中first和last只能指向Node。

一个List只要有开始结束，修改次数以及长度即可，其中的其他操作Node节点对象会存储下一个值得指向

add方法：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mOOj0wqf-1635075954218)(D:Program FilesJava复习集合集合.assetsimage-20211019143928575.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-w1B1WO6s-1635075954219)(D:Program FilesJava复习集合集合.assetsimage-20211019144625150.png)]

总统为两步：创建新节点 —> 修改节点和链表

把last老节点引用拿下来放到新节点的前面，设置新节点的后面为null

设置新节点为新的last节点

看老节点是不是为null，为null就是first节点

不为null表示要接在，老last节点的尾部

修改次数加1

remove方法删除第一个元素源码

如果没有给参数，则删除第一个元素

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xSy7AlMV-1635075954220)(D:Program FilesJava复习集合集合.assetsimage-20211019145545836.png)]

获取linkedList的第一个元素的引用，将引用放入unlinkFirst()方法中

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TA02zTMB-1635075954221)(D:Program FilesJava复习集合集合.assetsimage-20211019145654433.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U8LFtIAr-1635075954222)(D:Program FilesJava复习集合集合.assetsimage-20211019150326681.png)]

拿节点 —> 修改节点 —> 修改链表 —> 判断节点

不管如何修改节点，头或者尾指向永远是最后修改的，就算是指向为null也要也要把null当作元素使用

注意：

可以用迭代器，即可以使用增强for循环

ArrayList 和 linkedList的比较：

ArrayList 增删效率较低使用数组扩容，linkedList使用链表追加效率较高
查找ArrayList 效率较高，linkedList效率较

如何选择ArrayList 和 linkedList：

查找多先择ArrayList
增删多选择linkedList
可以灵活选择，一般使用ArrayList ，或者可以一个模块使用ArrayList，另一个模块使用linkedList
线程都不安全

五、Collection接口二：Set

介绍

不重复，无序，更接近高中的集合概念，所以没有索引，但是可以存储null
取出的顺序是固定的，但是存入的顺序不等于取出的顺序
底层使用的是数组加链表的形式存储

继承类图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uwuv3yIT-1635075954223)(D:Program FilesJava复习集合集合.assetsimage-20211019153447417.png)]

Set的实现类一：HashSet

要点：

实现set接口
HashSet的底层其实是HashMap
可以存放一个null值
不保证元素有序，存储取决于hash值，然后再确定索引
不可重复，hash值可以判断是否重复

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DaCBlx2s-1635075954224)(D:Program FilesJava复习集合集合.assetsimage-20211019154930001.png)]

HashSet.add()

添加方法会有一个返回值表示是否添加成功

底层查看HashMap，而HashMap的底层就是（数组+链表+红黑树）

简单来说就是：数组中存放单向链表，当大于一个值的时候链表变成红黑树

模拟底层：

package com.zhang.CollectionDemo;

public class HashSetStructure {
    public static void main(String[] args) {
        Node[] nodes = new Node[10];
        Node a = new Node("a",null);
        nodes[1] = a;
        Node b = new Node("b",null);
        Node c = new Node("c",null);
        a.next = b;
        b.next = c;
        System.out.println(nodes);
    }
}
class Node{
    Object item;
    Node next;
    @Override
    public String toString() {
        return "Node{" +
                "item=" + item +
                ", next=" + next +
                '}';
    }
    public Node() {
    }
    public Node(Object item, Node next) {
        this.item = item;
        this.next = next;
    }
}

数组中存储的是索引，所以直接使用索引修改next值可以影响到数组中的next

添加注意点：

HashSet底层是 HashMap
添加一个元素时，先得到hash值，将hash值转成索引值存储到数组中
根据hash值找存储数据表table，查看位置是否存储元素，没有直接加入
有的话，调用equals比较，如果相同，就放弃添加，如果不相同，就添加到最后
链表元素超过8，并且tale达到64，转化为红黑树，如果只是链表元素超过8，那么对table进行扩容，应该会从新获取hash值

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

我们知道HashSet底层是 HashMap，而 HashMap 的实现是数组+链表+红黑树。

HashSet是怎么样用 HashMap呢？

将数据存储在数组中，而数组中的链表使用static final Object object 对象进行占位，由于占位的对象是static静态的，所以内存自始至终都只有一个Object对象存在。

hash值不是hash值，索引值也不是hash值

其中使用add() 方法，中使用了put() 方法，put 要使用hash对key求hash值？（其中数组存储是使用key的hash值来设置索引的，那hash是怎么算的？）

先查看key是否是null，是返回0，否进行h的赋值，运算为：拿到key.hashCode() 然后与它（无符号右移16位）的值进行异或，为什么要这样运算，尽量避免存储的索引值相同

获取索引值的运算是怎么样的？

获取HashMap数组的最大下标与hash值进行与& 运算获得，而与& 运算就是取hash值得位数

它的节点判断是否相同是怎么判断的？

先判断hash值是否相同，然后使用equals方法判断，或者判断是否是同一个对象

为什么设置的容量默认为16？

因为 resize()方法中默认插入容量为1的左移4位算法

HashMap的树化是在哪里进行的？

是在add()方法增加元素的时候进行的，当进行到链表长度达到9的时候，执行树化，然后在树化里面判断，HashsMap[]数组元素是否达到64个，没达到进行扩容操作，达到进行树化

扩容操作是怎么操作的？

对临界值和容量都进行左移1位，两倍原来的值的扩容操作，而其中扩容完临界值相当于每次扩容完容量的0.75倍

所有的节点数大于临界值会进行扩容操作

真正的add操作

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //定义辅助变量，其中table是HashMap的数组，类型为Node[]
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)//如果长度为0，或者为null就resize()创建table，相当于new table
        n = (tab = resize()).length;//获取创建的table的长度
    if ((p = tab[i = (n - 1) & hash]) == null)//先进行运算获取索引，再赋值给i
        tab[i] = newNode(hash, key, value, null);//索引所在数组没有
    else {
        Node e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))//第一个key的hash全部相等
            e = p;
        else if (p instanceof TreeNode)//其中数组存储的链表已经变成了红黑树，放到红黑树里面对比
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        else {//还在链表循环进行，对链表key的查找
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {//hash值不同或者key不同，并且链表只存储了1个元素
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st，查看长度是否超过8
                        treeifyBin(tab, hash);//超过则树化
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    //当查找到相同的数据时候跳出循环
                    break;
                p = e;//上两次判断意见将p的next给了e，这个是将p指向下一个e.next元素
            }
        }
        if (e != null) { // existing mapping for key已经存在于数组中，专门服务于HashMap中的替换key值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;//修改次数加1
    if (++size > threshold)//查看是否大于临界值，大于的预先扩容
        resize();
    afterNodeInsertion(evict);//留给HashMap的子类进行实现
    return null;//返回null添加成功，返回原来的节点数据，就表示已经存在
}

resize()创建table也就是HashMap的数组的代码：

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧HashMap数组的长度
    int oldThr = threshold;//旧的临界值
    int newCap, newThr = 0;
    if (oldCap > 0) {//HashMap的扩容操作
        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，容量和临界值都扩容2倍，临界值相当于每次扩容完容量的0.75倍
    }
    else if (oldThr > 0) // initial capacity was placed in threshold，使用老的临界值创建数组
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults首次创建操作
        newCap = DEFAULT_INITIAL_CAPACITY;//1左移4位操作，变成16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//临界值扩容，预判达到原先的0.75倍准备扩容，以防止多线程的大量涌入
    }
    if (newThr == 0) {//查看临界值超出界限
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;//将临界值上传
    @SuppressWarnings({"rawtypes","unchecked"})
    Node[] newTab = (Node[])new Node[newCap];//创建16长度的Node数组给
    table = newTab;
    if (oldTab != null) {//数据的copy操作
        for (int j = 0; j < oldCap; ++j) {
            Node 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)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node 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;
                    }
                }
            }
        }
    }
    return newTab;
}

练习题

package com.zhang.CollectionDemo;
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("xxxx",15,new MyDate(2005,6,5)));
        hashSet.add(new Employee("dddd",29,new MyDate(1995,6,5)));
        hashSet.add(new Employee("xxxx",15,new MyDate(2005,6,5)));
        System.out.println(hashSet);
    }
}
class Employee{
    private String name;
    private int age;
    private MyDate myDate;
    public Employee() {
    }
    public Employee(String name, int age, MyDate myDate) {
        this.name = name;
        this.age = age;
        this.myDate = myDate;
    }
    @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(myDate, employee.myDate);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, myDate);
    }
    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + ''' +
                ", age=" + age +
                ", myDate=" + myDate +
                '}';
    }
}
class MyDate{
    private int year;
    private int month;
    private int day;

    public MyDate() {
    }
    public MyDate(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyDate myDate = (MyDate) o;
        return year == myDate.year && month == myDate.month && day == myDate.day;
    }
    @Override
    public int hashCode() {
        return Objects.hash(year, month, day);
    }
    @Override
    public String toString() {
        return "MyDate{" +
                "year=" + year +
                ", month=" + month +
                ", day=" + day +
                '}';
    }
}

Set实现类二：linkedHashSet

总结：

linkedHashSet 是 HashSet 的子类
底层是一个 linkedHashMap ，底层维护了一个数组+双向链表
linkedHashSet 根据元素的 hashCode 值来都决定元素的存储位置，同时使用链表维护元素的次序，着使得元素看起来是以插入顺序来保存的。
linkedHashSet 不允许添加重复元素

源码总结：

在 linkedHashSet 中维护了一个hash表和双向链表（linkedHashSet 有 head 和 tail）
每一个节点有 pre 和 next 属性，形成双向链表
添加一个元素时，相求hash值，在求索引，确定改元素在hashtable的位置，然后添加的元素加入到双向链表
由于双向链表的连接，所以插入顺序和取出顺序一致

与HashSet进行比较：

数据结构比较，其中节点名字为Entry继承于HashMap的Node，从单向链表变成双向链表（加了两个Before和 After的Entry），其他没变。
第一次也是扩容到16个表示，用的应该是1的左移4位操作
table继承了HashMap的table
其中的add()方法或者put()方法会追到HashSet里面去，也就是HashMap里面去

唯一的变化就是节点为Entry继承于HashMap的Node，变成了双向链表，其他的扩容，创建，比较全部沿用HashMap的

Set实现类三：TreeSet

其中最大的特点就是可以排序
使用无参构造器，创建TreeSet，仍然无序

如果需要排序，那么要对构造器，传入一个Comparator比较器（匿名内部类），并指定排序规则

//String中完善的排序规则
public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);//拿到两个字符串最小的长度
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    while (k < lim) {//只对比最小长度，从第一个字符开始对比，只要有一个字符不同就可以返回，这个字符的ASCII值的相减值
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;//两个相同返回0
}

TreeSet有许多的构造器

TreeMap真实的存放源码

public V put(K key, V value) {
    Entry t = root;//获取树的头节点
    if (t == null) {//头节点为null的情况直接添加
        compare(key, key); // type (and possibly null) check防止空值

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry parent;
    // split comparator and comparable paths
    Comparator cpr = comparator;
    if (cpr != null) {//有比较器的情况下
        do {//遍历整个树，直到拿到父节点的左节点，或则右节点
            parent = t;//将父节点赋值给parent，检测完成才对parent进行更新
            cmp = cpr.compare(key, t.key);//key比较头节点
            if (cmp < 0)//头节点比较大，新节点要放左边，拿左子树，以便下一次循环左节点
                t = t.left;
            else if (cmp > 0)//头节点比较小，新节点要放右边，以便下一次循环右节点
                t = t.right;
            else
                return t.setValue(value);//相同的key，则替换值
        } while (t != null);//经历这个循环后，parent一定是null，或者被替换值了
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable k = (Comparable) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry e = new Entry<>(key, value, parent);//创建新元素的节点
    if (cmp < 0)//如果
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

总结

TreeSet的底层是什么？

是TreeMap

TreeSet的构造器中的Comparator比较器传到哪里去了？

Comparator赋值给了TreeMap中的定义的Comparator比较器，并且初始化只干了这件事

底层使用的节点是什么？

TreeSet的底层是　TreeMap，节点是Entry，不同于普通的Entry，它的结构是（key value left right），很像链表

TreeMap底层是怎么实现排序的？

构造方法中需要传递一个Comparator比较器，需要在里面重写排序规则，会被赋值在TreeMap中声明好的Comparator比较器，然后要排序的时候，就将比较的值放入Comparator比较器中。String中已经写好了字符串的排序规则：获得两个字符串的长度，拿最小的长度，循环每个字符，如果不一样相减，如果一样就下一个字符，比较完最后一个字符，还没有结果，直接减字符串长度

TreeMap是怎么进行添加节点的？

底层使用的是do while循环，添加的时候会获取父节点，使用父节点进行key之间的对比，排序规则由Comparator比较器给出，拿到比较值，看是否大于小于0，然后更新临时节点t，下一次循环再更新父节点，如从获得父节点以及可以放入的节点，最后创建新节点放入

TreeMap怎么进行去重？

其中比较头节点是去重的关键，使用了比较器Comparator，如果相同会进行key的赋值

如果TreeMap没有进行比较器Comparator的赋值使用谁的比较器？

因为每一个基本类型的数据，他都会实现比较器Comparator接口所以，进行上转型，就可以获得独属于这个类型的比较器，如果放入没有实现Comparator接口的对象，那么会抛出类型转换异常

六、Map接口

Map的特点：

Map与Collection并列存在。由于保存具有映射关系的数据：Key—Value
Map 中的key 和value 可以是任何引用类型的数据，会封装到HashMap&Node对象中
Map 中的 key 不允许重复，原因和Hashset 一样
value 可以重复
Map 的key 可以是 null，value 也可以为null，注意 key 为null，只能由一个，但是value可以有多个
常用String类作为Map 的 key
key 和 value 之间存在单向一对一关系，即通过指定的key 总能找到对应的 value
添加中key相同value不同，会对value进行覆盖
其中方便遍历会创建一个 entrySet> 类型集合，本质是一个Set集合，其中 Entry 是 Node 的引用
线程不安全

Map接口的常用方法

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

对于遍历方式来说有三种分别对于Entry节点、装key的Set集合和装value的Collection集合：

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

有区别

底层源码和上面的HashSet一致，唯一的区别就是遍历要使用DetrySet集合

为什么加入相同的key的时候，value会变？

其中的key定义为final，而value没有，所以value可以更改

HashMap类中会创建一个entrySet集合，它的存储类型是Entry，那么Entry怎么来的？

因为Node 继承 Entry，所以直接放在entrySet集合里面Node 就会被向上转型，并且里面存放不是真实存在，而是table也就是数组中存放的Node的引用

加载因子和table的HashMap$Node[] 数组什么时候创建的？

new HashMap() 的时候初始化的这时候：table=null，loadfactor=0.75

一、Map实现类：HashTable

HashTable的介绍

存放的元素是键值对：即 k—V
HashTable 的键和值都不能为null，否则会抛出NullPointerException异常
HashTable 使用方式和HashMap基本一样
HashTable 是线程安全的，HashMap 是线程不安全的

总结：

底层是一个HashTable$Entry[] 数组初始大小为11，临界值为8（有初始大小容量11* 0.75的加载因子）

其中的index数组下标计算方法

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();//获取hash值
    int index = (hash & 0x7FFFFFFF) % tab.length;//拿hash值位于无符号整数的最大值255的二进制的长度的数，然后对数组最大长度求余
    @SuppressWarnings("unchecked")
    Entry entry = (Entry)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

详细的扩容：

protected void rehash() {
    int oldCapacity = table.length;//拿到table长度
    Entry[] oldMap = table;//拿到table

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;//扩容：*2+1，获取新的长度
    if (newCapacity - MAX_ARRAY_SIZE > 0) {//查看是否超过最大值，最大值就一直使用
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry[] newMap = new Entry[newCapacity];//创建新的Entry[]数组

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
            Entry e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry)newMap[index];
            newMap[index] = e;
        }
    }
}

源码分析

扩容机制从11的初始值到23是怎么扩容的（其中的加载因子还是0.75）？

扩容操作是将老容量拿来左移一位也就是乘2，然后加1

HashTable的index是怎么来的？

获取key的hash值，然后对hash值和无符号整数最大长度255的二进制与运算，然后对数组的最大长度进行求余运算

二、Map实现类：Properties

介绍：

Properties类继承自Hashtale类并且实现了Mao接口，也是使用一种键值对的形式开保存数据。
使用的特点和HashTable类似
Properties 还可以用于从 xxx.properties 文件中，记载数据到properties类对象，并进行读取和修改

三、Map实现类：TreeMap

介绍：

如TreeSet，不同的只是Static final Object 类型的占位对象没有了，变成了真实的value

七、Collection工具类

介绍：

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

排序方法：

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

package com.zhang.CollectionsDemo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


public class Collections_ {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add("A");
        arrayList.add("B");
        arrayList.add("C");
        arrayList.add("D");
        arrayList.add("E");
        arrayList.add("F");
        //        - reverse(List)：反转 List 中元素的顺序
        Collections.reverse(arrayList);
        System.out.println(arrayList);
        //        - shuffle(List)：对 List 集合元素进行随机排序
        Collections.shuffle(arrayList);
        System.out.println(arrayList);
        //        - sort(List)：根据元素的自然顺序对指定的 List 集合元素按升序排序
        Collections.sort(arrayList);
        System.out.println(arrayList);
        //        - sort(List, Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
        Collections.sort(arrayList, new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o2).compareTo((String)o1);
            }
        });
        System.out.println(arrayList);
        //        - swap(List, int, int)：将指定 List 集合中的 i 处元素和 j 处元素进行交换
        Collections.swap(arrayList,0,1);
        System.out.println(arrayList);
    }
}

查找、替换：

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

package com.zhang.CollectionsDemo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


public class Collections_ {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add("A");
        arrayList.add("A");
        arrayList.add("B");
        arrayList.add("C");
        arrayList.add("D");
        arrayList.add("E");
        arrayList.add("F");
        //        - Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
        System.out.println(Collections.max(arrayList));
        //        - Object max(Collection,Comparator)：根据 Comparator 指定的顺序，返回给定集合中最大元素
        System.out.println(Collections.max(arrayList,new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o2).compareTo((String)o1);
            }
        }));
        //        - Object min(Collection)
        System.out.println(Collections.min(arrayList));
        //        - Object min(Collection,Comparator)
        System.out.println(Collections.max(arrayList,new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o1).compareTo((String)o2);
            }
        }));
        //        - int frequency(Collection,Comparator)：返回指定集合中指定元素的出现次数
        System.out.println(Collections.frequency(arrayList,"A"));
        //        - void copry(List dest,List src)：将src中的内容赋值到dest中
        ArrayList arrayList1 = new ArrayList();
        for (int i = 0; i < arrayList.size(); i++) {
            arrayList1.add("");
        }
        Collections.copy(arrayList1,arrayList);
        System.out.println(arrayList1);
        //        - boolean replaceAll(List list,Object oldVal,Object newVal)：使用新值替换 List 对象的所有旧值
        Collections.replaceAll(arrayList,"A","hahahah");
        System.out.println(arrayList);
    }
}

八、总结—开发中如何选择集合实现类

先判断存储类型（一组对象或一组键值对）
一组对象：Collection接口
1. 允许重复：List
  - 增删多：linkedList [底层维护了一个双向链表]
  - 改查多：ArrayList [底层维护 Object类型的可变数组]
2. 不允许重复：Set
  - 无序：HashSet [底层是HashMap，维护了一个哈希表，即（数组+单向链表+红黑树）]
  - 排序：TreeSet
  - 插入顺序和取出顺序一致：linkedHashSet，维护十足+双向链表
一组键值对：Map
- 键无序：Hash [底层：哈希表（数组+单向链表+红黑树）]
- 键排序：TreeMap
- 键插入和取出顺序一致：linkedHashMap
- 读取文件 Properties

Java复习（集合）涉及源码

Java相关栏目本月热门文章