Java集合的使用

2023-11-18

集合的使用

集合框架的概述
Collection 接口的使用
List 的使用
Set 的使用
Map 的使用
Collections 工具类的使用
面试题

集合框架的概述

集合、数组都是对多个数据进行存储操作的结构，简称 Java 容器。

此时的存储，主要指的是内存层面的存储，不涉及到持久化的存储（比如 .txt、.jpg、数据库等）

数组在存储多个数据的特点

一旦初始化之后长度就是确定的
定义数组的时候需要指明数组的元素类型（声明是什么类型就必须存储什么类型的数据）

比如：String[] arr; int[] arri;

数组在存储多个数据的缺点

长度一旦确定就不能修改了
只能存储单个类型的数据（有利（更加严格管控数据）有弊（有多个类型数据时不方便），根据需求而定）
数组中提供的方法比较有限，对于添加、删除、插入数据等操作，非常不方便，效率也比较低
获取数组中实际元素的个数的需求（比如：一个长度为10的数组中有几个可用元素），数组没有现成的属性或方法可以使用
数组存储数据的特点：有序、可重复；对于无序且不能重复的需求，数组是不能实现的

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

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

Collection接口

单列数据，单列集合，用于存储一个一个的对象

List：存储有序、可重复的数据（常用：ArrayList、LinkedList、Vector）
Set：存储无序、不可重复的数据（常用：HashSet、LinkedHashSet、ThreeSet）

在这里插入图片描述

Map接口

双列集合，用于存储一对（key-value）一对（key-value）的数据

常用：HashMap、LinkedHashMap、ThreeMap、Hashtable、Properties

在这里插入图片描述

Collection 接口的使用

说明

Collection 接口是 List、Set 和 Queue 接口的父接口，该接口里定义的方法既可用于操作 Set 集合，也可用于操作 List 和 Queue 集合。
JDK 不提供此接口的任何直接实现，而是提供更具体的子接口（如：Set 和 List）实现。
在 JDK5 之前，Java 集合会丢失容器中所有对象的数据类型，把所有对象都当成 Object 类型处理；从 JDK 5.0 增加了泛型以后，Java 集合可以记住容器中对象的数据类型。

常用方法

方法	作用
add(Object obj)	添加指定元素到指定集合中（使用了自动装箱）
addAll(Collection coll)	将指定集合中的元素添加到当前集合中
int size()	获取指定集合中元素的个数
void clear()	清空指定集合中所有元素
boolean isEmpty()	判断当前集合是否为空
boolean contains(Object obj)	判断当前集合中是否包含某个元素
boolean containsAll(Collection coll)	判断形参 coll 中的所有元素是否都存在于当前集合中
boolean remove(Object obj)	从当前集合中删除 obj 元素，成功返回 true，失败返回 false
boolean removeAll(Collection coll)	从当前集合中移除 coll 中所有的元素
boolean retainAll(Collection coll)	交集，获取当前集合和 coll 集合的交集，并返回给当前集合
boolean equals(Object obj)	要想返回 true，需要当前集合和形参集合的元素都相同
Object[] toArray()	将集合转成对象数组
hashCode()	获取指定集合对象的哈希值
iterator()	返回 Iterator 接口的实例，用于遍历集合元素

在调用 contains、containsAll、remove、removeAll 的时候都是去调用 equals 方法来找到对应的值的

数组转集合：Arrays.asList();

集合转数组：toArray()

案例一

package com.laoyang.test.day1;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;

/**
 * @ClassName CollectionTest
 * @Description： 集合框架的使用
 * @Author Laoyang
 * @Date 2021/9/28 15:42
 */
public class CollectionTest {
    /**
     * Collection 接口中的方法使用
     */
    @Test
    public void testOne() {
        Collection collection = new ArrayList();
        // add(Object e)：将指定的元素添加到对应的集合中（自动装箱）
        collection.add("小白");
        collection.add(123);

        // addAll(Collection coll)：将指定集合中的元素添加到当前集合中（在部分需求中可用于整合多个集合）
        Collection coll = new ArrayList();
        coll.add("AAa");
        coll.addAll(collection);
        //Collection collection1 = new ArrayList();
        //collection1.addAll(coll);     // 小白   123   AAa

        // size()：获取指定集合中元素的个数
        System.out.println(collection.size());  // 2

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

        // clear()：清空指定集合中所有元素
        System.out.println(collection);  // [小白, 123]
        collection.clear();
        System.out.println(collection);  // []
    }
}

案例二

注意：向 Collection 接口的实现类的对象中添加 obj 数据时，要求 obj 所在类要重写 equals 方法

package com.laoyang.test.day1;

import org.junit.Test;
import java.util.*;

/**
 * @ClassName CollectionMethod
 * @Description： Collection 常用方法
 * @Author Laoyang
 * @Date 2021/9/30 10:15
 */
public class CollectionMethod {
    @Test
    public void testOne() {
        Collection collection = new ArrayList();
        collection.add("AAA");
        collection.add(123);
        collection.add("ABC");
        collection.add(new String("QQ"));
        Person person = new Person();
        collection.add(person);
        collection.add(new Person("Laoyang", 20));

        // contains(Object obj)：判断当前集合中是否包含某个元素
        System.out.println(collection.contains("ABC"));     // true
        System.out.println(collection.contains("CCC"));     // false
        /*
        注意
        String 内部重写了 equals 方法，所以在使用 contains 方法的时候会自动调用重写后的 equals 方法进行判断，因此两个相同值的类比较起来就是 true
        而部分类中是没有重写 equals 方法的，就会默认调用 Object 中的 equals 方法，而 Object 类中的 equals 方法是使用 == 号进行判断的（也就是判断地址值的），因此两个相同值的类比较起来就是 false
        Ps：如果想要让两个相同值的类为 true，则需要手动重写 equals
         */
        System.out.println(collection.contains(new String("QQ")));     // true
        System.out.println(collection.contains(person));     // true
        System.out.println(collection.contains(new Person("Laoyang", 20)));     // false（重写equals方法后为 true）

        System.out.println("----------------------------------");

        // containsAll(Collection coll)：判断形参 coll 中的所有元素是否都存在于当前集合中
        Collection coll = Arrays.asList("QQ", 123, "嘿嘿嘿");  // 只要有一个不一样的就会返回 false
        System.out.println(coll.containsAll(collection));   // false
    }

    @Test
    public void testTwo() {
        Collection collection = new ArrayList();
        collection.add("AAA");
        collection.add(123);
        collection.add("ABC");
        collection.add(new String("QQ"));
        collection.add(new Person("Laoyang", 20));

        // remove(Object obj)：从当前集合中删除 obj 元素，成功返回 true，失败返回 false
        System.out.println(collection);  // [AAA, 123, ABC, QQ, Person{name='Laoyang', age=20}]
        System.out.println(collection.remove("AAA"));   // true
        System.out.println(collection);  // [123, ABC, QQ, Person{name='Laoyang', age=20}]

        System.out.println("----------------------------------");

        // removeAll(Collection coll)：从当前集合中移除 coll 中所有的元素
        Collection coll = Arrays.asList(123, "QQ", "WW");
        System.out.println(collection.removeAll(coll)); // true
        System.out.println(coll);       // [123, QQ, WW]
        System.out.println(collection);     // [ABC, Person{name='Laoyang', age=20}]
    }

    @Test
    public void testThree() {
        Collection collection = new ArrayList();
        collection.add("AAA");
        collection.add(123);
        collection.add("ABC");
        collection.add(new String("QQ"));
        collection.add(new Person("Laoyang", 20));

        // retainAll(Collection coll)：交集，获取当前集合和 coll 集合的交集，并返回给当前集合
        Collection coll = Arrays.asList(123, "QQ", "WW");
        System.out.println(collection.retainAll(coll)); // true
        System.out.println(collection);     // [123, QQ]

        System.out.println("----------------------------------");

        // equals(Object obj)：要想返回 true，需要当前集合和形参集合的元素都相同
        Collection collA = new ArrayList();
        collA.add("AAA");
        collA.add(123);

        Collection collB = new ArrayList();
        collB.add("AAA");
        collB.add(123);

        Collection collC = new ArrayList();
        collC.add(123);
        collC.add("AAA");

        System.out.println(collA.equals(collB)); // true
        System.out.println(collA.equals(collC)); // false（因为 List 存储的是有序且可重复的数据，如果值一样顺序不一样也会返回 false）
    }

    @Test
    public void testFour() {
        Collection collection = new ArrayList();
        collection.add("AAA");
        collection.add(123);
        collection.add("ABC");
        collection.add(new String("QQ"));
        collection.add(new Person("Laoyang", 20));

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

        /*
        集合 转 数组：toArray()
        数组 转 集合：Arrays.asList()
         */
        Object[] objects = collection.toArray();
        System.out.println(Arrays.toString(objects));   // [AAA, 123, ABC, QQ, Person{name='Laoyang', age=20}]

        List<Object> list = Arrays.asList(objects);
        System.out.println(list);   // [AAA, 123, ABC, QQ, Person{name='Laoyang', age=20}]

        /*
         注意：在使用基本数据类型的数组时，List 只会识别出一个元素！！！
         如果有需要的话，可以使用包装类的方式进行传输
         */
        List<int[]> ints = Arrays.asList(new int[]{1, 2, 3, 4});
        System.out.println(ints.size());    // 1
        System.out.println(ints);   // [[I@22927a81]

        List<char[]> chars = Arrays.asList(new char[]{'q', 'a'});
        System.out.println(chars);  // [[C@78e03bb5]

        // 包装类形参的方式
        List<Integer> integers = Arrays.asList(new Integer[]{1, 2, 3, 4});
        System.out.println(integers.size());    // 4
        System.out.println(integers);   // [1, 2, 3, 4]

        List<Double> doubles = Arrays.asList(new Double[]{1.2, 2.3, 3.4});
        System.out.println(doubles.size());    // 3
        System.out.println(doubles);    // [1.2, 2.3, 3.4]
    }
}

class Person {
    private String name;
    private int age;

    /**
     * 重写 equals 方法
     */
    @Override
    public boolean equals(Object o) {
        System.out.println("进入Person类中的equals方法");
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }

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

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

    public Person() {
    }
}

注意

String 内部重写了 equals 方法，所以在使用 contains 方法的时候会自动调用重写后的 equals 方法进行判断，因此两个相同值的类比较起来就是 true。

而部分类中是没有重写 equals 方法的，就会默认调用 Object 中的 equals 方法，而 Object 类中的 equals 方法是使用 == 号进行判断的（也就是判断地址值的），因此两个相同值的类比较起来就是 false。

如果想要让两个相同值的类为 true，则需要手动重写 equals

在使用基本数据类型的数组时，List 只会识别出一个元素！！！如果有需要的话，可以使用包装类的方式进行传输。

Iterator 迭代器

说明

Iterator 对象称为迭代器(设计模式的一种)，主要用于遍历 Collection 集合中的元素。
GOF 给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。

类似于 “公交车上的售票员”、“火车上的乘务员”、“空姐”。
集合对象每次调用 iterator() 方法都会得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

Iterator 内部定义的方法

hasNext()：判断是否还有下一个元素
next()：指针下移，并且将下移以后集合位置上的元素返回
remove()：在遍历的时候，删除集合中指定的元素，此方法不同于集合直接调用 remove()

在这里插入图片描述

案例

这里简单演示三种遍历方式

package com.laoyang.test.day1;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

/**
 * @ClassName IteratorTest
 * @Description： Ierator 迭代器的使用
 * @Author Laoyang
 * @Date 2021/9/30 11:18
 */
public class IteratorTest {
    @Test
    public void testOne() {
        Collection collection = new ArrayList();
        collection.add("AAA");
        collection.add(123);
        collection.add(new String("QQ"));
        collection.add(new Person("Laoyang", 20));

        Iterator iterator = collection.iterator();
        // 方式一
//        System.out.println(iterator.next());  // AAA
//        System.out.println(iterator.next());  // 123
//        System.out.println(iterator.next());  // QQ
//        System.out.println(iterator.next());  // Person{name='Laoyang', age=20}
//        System.out.println(iterator.next());  // 报错：NoSuchElementException

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

        // 方式三：推荐（hasNext()：判断是否还有下一个元素）
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

Iterator 执行原理

创建 Iterator 对象的时候会生成一个指针

hashNext 方法判断是否还有下一个元素

如果 hashNext 返回 true，那么指针会向下移动，指向集合中的第一个元素，如果为 false，则直接结束…以此类推

Iterator 遍历集合的两种错误写法

错误一：直接使用 next() 进行判断，导致跳着遍历

错误二：使用 Iterator 匿名对象，导致死循环

package com.laoyang.test.day1;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

/**
 * @ClassName IteratorTest
 * @Description： Ierator 迭代器的使用
 * @Author Laoyang
 * @Date 2021/9/30 11:18
 */
public class IteratorTest {
    /**
     * Iterator 遍历集合的两种错误写法
     */
    @Test
    public void testTwo() {
        Collection collection = new ArrayList();
        collection.add("AAA");
        collection.add(123);
        collection.add(new String("QQ"));
        collection.add(new Person("Laoyang", 20));

        /*
         错误一：
         第一次执行的时候获取的是 AAA，然后用 AAA 进行判断
         判断成功后，返回下一个指针所指向的值 123
         最后的效果就会是跳着输出集合元素，然后跳到最后一个的时候，没有下一个了，就会报：NoSuchElementException
         */
//        Iterator iterator = collection.iterator();
//        while ((iterator.next()) != null) {        // 第一次执行的时候获取的是 AAA，然后用 AAA 进行判断
//            System.out.println(iterator.next());   // 判断成功后，返回下一个指针所指向的值 123
//        }

        /*
        错误二：使用 Iterator 匿名对象 - 导致死循环
         */
        while (collection.iterator().hasNext()) {
            System.out.println(collection.iterator().next());
        }
    }
}

remove 方法的使用

注意

Iterator 可以删除集合的元素，但是是遍历过程中通过迭代器对象的 remove 方法，不是集合对象的 remove 方法。
如果还未调用 next() 的时候调用 remove() 就会报 IllegalStateException
在上一次调用 next 方法之后调用了两次 remove 方法也会报 IllegalStateException。

案例

package com.laoyang.test.day1;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

/**
 * @ClassName IteratorTest
 * @Description： Ierator 迭代器的使用
 * @Author Laoyang
 * @Date 2021/9/30 11:18
 */
public class IteratorTest {
    /**
     * remove 方法的使用
     * 情况一：如果还未调用 next() 的时候调用 remove() 就会报 IllegalStateException
     * 情况二：在上一次调用 next 方法之后调用了两次 remove 方法也会报 IllegalStateException。
     */
    @Test
    public void testTherr() {
        Collection collection = new ArrayList();
        collection.add("AAA");
        collection.add(123);
        collection.add(new String("QQ"));
        collection.add(new Person("Laoyang", 20));

        // 删除集合中指定的元素
        Iterator iterator = collection.iterator();
        while (iterator.hasNext()) {
            // 情况一：不能再 hasNext() 方法执行后马上执行 remove 方法，因为这个时候指针还未指到任何一个值
            //iterator.remove();    // 报错：IllegalStateException

            Object next = iterator.next();
            if ("QQ".equals(next)) {
                iterator.remove();
                // 情况二：不能在 next() 方法后连续调用两次 remove()，但是可以在外面调用，比如可以在当前 while 结构外调用 remove()
                //iterator.remove();  // 报错：IllegalStateException
            }
        }
        // 遍历集合，因为上面已经遍历完了，所以我们这里需要在重新赋一下值，然后在进行遍历
        iterator = collection.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

foreach 方式遍历集合元素

说明

foreach 是 JDK5 新增的 for 循环新特性，用于遍历集合、数组。
遍历操作不需获取 Collection 或数组的长度，无需使用索引访问元素。
遍历集合的底层调用 Iterator 完成操作。

案例

package com.laoyang.test.day1;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;

/**
 * @ClassName ForTest
 * @Description： JDK5 新增的 for 循环新特性
 * @Author Laoyang
 * @Date 2021/9/30 15:52
 */
public class ForTest {
    /**
     * 遍历集合：for(集合中的元素类型 局部变量 : 集合对象) { }
     */
    @Test
    public void testOne() {
        Collection collection = new ArrayList();
        collection.add("AAA");
        collection.add(123);
        collection.add(new String("QQ"));
        collection.add(new Person("Laoyang", 20));

        // 这种遍历方式内部仍然调用了迭代器
        for (Object o : collection) {
            System.out.println(o);
        }
    }

    /**
     * 遍历数组：for(数组的元素类型 局部变量 : 数组对象) { }
     */
    @Test
    public void testTwo() {
        int[] arr = new int[]{1, 5, 3, 2};
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

小练习

使用两种不同的 for 循环赋值方式，最后打印的结果分别是什么？

package com.laoyang.test.day1;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;

/**
 * @ClassName ForTest
 * @Description： JDK5 新增的 for 循环新特性
 * @Author Laoyang
 * @Date 2021/9/30 15:52
 */
public class ForTest {
    /**
     * 小练习：最后打印的结果是 WW 还是 MM？
     */
    @Test
    public void testThree() {
        String[] strs = new String[]{"WW", "WW", "WW"};
        /*
        方式一：普通 for 赋值
        这种赋值操作是把 strs 数组中指定下标位置的元素替换成新的值，所以最后遍历的结果就是替换后的元素
         */
//        for (int i = 0; i < strs.length; i++) {
//            strs[i] = "MM";
//        }

        /*
         方式二：增强 for 赋值
         这种赋值操作并不会保存在 strs 中，因为它是先从 strs 中获取到每一个值，然后依次赋值给 str 进行使用
         但是 str 是一个新的局部变量，它的值并不会影响到 strs 中的元素，所以最后打印的结果依然会是 WW
         */
        for (String str : strs) {
            str = "MM";
        }

        for (String str : strs) {
            System.out.println(str);
        }
    }
}

大家可以打开/关闭注释的代码进行测试

List 的使用

说明

对于 Java 中数组用来存储数据的局限性，我们通常使用 List 替代数组。
List 集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
List 容器中的元素都对应一个整数型的序号记载在容器中的位置，可以根据序号存取容器中的元素。
JDK API 中 List 接口的实现类常用的有：ArrayList、LinkedList 和 Vector。

常见面试题：ArrayList、LinkedList 和 Vector 的相同点与不同点？

相同点：三个类都实现了 List 接口，存储数据的特点相同（都是有序且可重复的数据）

不同点：

ArrayList：作为 List 接口的主要实现类（JDK1.2出现）；执行效率高（线程不安全的）；底层使用 Object[] elementData 进行存储；

LinkedList：JDK1.2出现；对于频繁的插入、删除操作使用此类效率比 ArrayList 要高；底层使用双向链表存储；

Vector：作为 List 接口的古老实现类（JDK1.0出现）；执行效率低（线程安全的）；底层使用 Object[] elementData 进行存储；

List 接口也是 JDK1.2 的时候出现的

ArrayList 源码分析（JDK7 & JDK8）

JDK7 中的 ArrayList

ArrayList list = new ArrayList();   // 底层创建了长度为 10 的数组
list.add(111);   // elementData[0] = new Integer(111);
   ...
list.add(999);   // 如果此次的添加操作导致底层 elementData 数组容量不够，则会进行扩容
> 默认情况下，会扩容为原来容量的 1.5 倍，同时需要将原有数组中的数据赋值到新的数组中！
> 建议在实际开发中，使用带参的构造器：ArrayList list = new ArrayList(int initialCapacity);

部分源码

package java.util;

import java.util.*;

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
	// ArrayList 的元素存储在其中的数组缓冲区。ArrayList 的容量就是这个数组缓冲区的长度
	private transient Object[] elementData;
	
	// ArrayList 的大小（它包含的元素数）。
	private int size;
	
	/**
	 * 要分配的数组的最大大小。 一些 VM 在数组中保留一些头字。
	 * 尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超出 VM 限
	 */
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

	// 空参构造器，自动设置 elementData 原始大小
	public ArrayList() {
        this(10);
    }
	
	// 带参构造器，手动设置 elementData 原始大小
	public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Cap" +
                    "acity: "+ initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
	
	// 返回当前元素总数
	public int size() {
        return size;
    }
	
	// 添加元素
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
	
	// 确保内容能够正常放入当前集合中，如果当前添加的内容超过了集合的存储长度，则会使用底层的扩容机制
	private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
	
	// 增加容量以确保它至少可以容纳由最小容量参数指定的元素数量
	private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 默认扩容成原来长度的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            // 如果还是不够，则直接把当前值的长度当做集合的长度
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
			// 如果还是不够，那么就会将int最大值作为长度
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
		// 将当前的 elementData 数组里面的所有元素复制到新的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
	
	private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
}

中文注释是我自己加的，可结合理解，也可以忽略

JDK8 中的 ArrayList

ArrayList list = new ArrayList();   // 底层 Object[] elementData 初始化为 {}，并没有创建长度为 10 的数组
list.add(111);     // 第一次调用 add() 时，底层才创建了长度为 10 的数组，并将数据 111 添加到 elementDate[0] 中
  ...
list.add(999);  // 如果此次的添加操作导致底层 elementData 数组容量不够，则会进行扩容
... 扩容操作与 JDK7 没什么区别

部分源码

package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
	// 用于默认大小的空实例的共享空数组实例。我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
	
	// ArrayList 的大小（它包含的元素数）。
    private int size;
	
	// 要分配的数组的最大大小。一些 VM 在数组中保留一些头字。尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超出 VM 限
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	
	// 构造一个初始容量为 10 的空列表。
	public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
	
	// 将指定的元素附加到此列表的末尾
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
	
	// 确保内部容量
	private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

	// 确保显式容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
	
	// 增加容量以确保它至少可以容纳由最小容量参数指定的元素数量。
	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);
    }

	// 巨大的容量
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
}

中文注释是我自己加的，可结合理解，也可以忽略

小结

JDK7 中的 ArrayList 的创建类似于单例模式中的饿汉式，JDK8 中的 ArrayList 的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。

LinkedList 源码解析

LinkedList list = new LinkedList();  // 内部声明了 Node 类型的 first 和 last 属性，默认值为 null
list.add(111);     // 将 111 封装到 Node 中，创建了 Node 对象

其中 Node（体现了 LinkedList 的双向链表的说法）定义为：
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

部分源码

package java.util;

import java.util.function.Consumer;

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // 第一个元素
    transient Node<E> first;

    // 最后一个元素
    transient Node<E> last;

    private static class Node<E> {
        E item;
        Node<E> next;   // 下一个元素
        Node<E> prev;   // 上一个元素

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    // 添加方法
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    // 链接 e 作为最后一个元素
    void linkLast(E e) {
        // 首次执行的last为null，有元素之后则为最后一个元素
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        // 如果last为空，则把当前要添加的元素当做是一个last元素和first元素（因为第一次只有一个元素新增进来，所以它既是第一个也是最后一个）
        if (l == null)
            first = newNode;
        else
            // 如果last不为空，则把新的元素添加在last元素的下一个元素位置上
            l.next = newNode;
        size++;
        modCount++;
    }
}

中文注释是我自己加的，可结合理解，也可以忽略

Vector 源码解析

因为 Vector 是很久之前的东西了，现在基本不会用到这个实现类，所以这里就简单说明一下

JDK7 和 JDK8 中通过 Vector() 构造器创建对象时，底层创建了长度为 10 的数组
在扩容方面，默认扩容为原来数组的 2 倍
Vector 是线程安全的

部分源码

package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
	// 存储向量组件的数组缓冲区。向量的容量是这个数组缓冲区的长度，并且至少足够包含向量的所有元素。Vector 中最后一个元素之后的任何数组元素都为空
	protected Object[] elementData;
	
	// 此Vector对象中的有效组件数
	protected int elementCount;
	
	// 当向量的大小变得大于其容量时，向量的容量自动增加的量。如果容量增量小于或等于零，则每次需要增长时，向量的容量都会增加一倍
	protected int capacityIncrement;
	
	// 构造一个空向量，使其内部数据数组的大小为10 ，其标准容量增量为零。
	public Vector() {
        this(10);
    }
	
	// 将指定的元素附加到此 Vector 的末尾。
	public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
	
	// 这实现了 ensureCapacity 的非同步语义。此类中的同步方法可以在内部调用此方法以确保容量，而不会产生额外同步的成本。
	private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
	
	// 要分配的数组的最大大小。一些 VM 在数组中保留一些头字。尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超出 VM 限制
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	
	private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }
	
	private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
}

中文注释是我自己加的，可结合理解，也可以忽略

常用方法

方法	作用
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位置的子集合

还有部分方法这里就不列出来了，大家可以看后面案例中的使用

案例

package com.laoyang.test.day2;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/**
 * @ClassName ListMethod
 * @Description： List 接口常用方法
 * @Author Laoyang
 * @Date 2021/10/2 9:41
 */
public class ListMethod {
    @Test
    public void testOne() {
        ArrayList list = new ArrayList();
        // add(Object obj)
        list.add("Laoyang");
        list.add(20);
        list.add(new Person("Xiaobai", 18));
        list.add(20);

        System.out.println(list);   // [Laoyang, 20, Person{name='Xiaobai', age=18}, 20]

        System.out.println("-----------------------------");

        // add(int index, Object ele):在index位置插入ele元素
        list.add(2, "QQ");
        System.out.println(list);   // [Laoyang, 20, QQ, Person{name='Xiaobai', age=18}, 20]

        System.out.println("-----------------------------");

        // addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
        List strings = Arrays.asList("WW", "EE", "RR");
        list.addAll(4, strings);
        // 如果是使用 add 的方式传入集合的话，list 会默认将它作为一个整体然后添加到对应的list中
        //list.add(strings);
        System.out.println(list);  // [Laoyang, 20, QQ, Person{name='Xiaobai', age=18}, WW, EE, RR, 20]
        System.out.println(list.size());    // 使用 addAll() 返回 9，使用 add() 返回 6

        System.out.println("-----------------------------");

        // get(int index):获取指定index位置的元素
        Object o = list.get(3);
        System.out.println(o);  // Person{name='Xiaobai', age=18}

        System.out.println("-----------------------------");

        // indexOf(Object obj):返回obj在集合中首次出现的位置，找不到对应值时返回 -1
        System.out.println(list.indexOf(20));     // 1
        System.out.println(list.indexOf(200));    // -1，找不到对应值时返回 -1

        System.out.println("-----------------------------");

        // lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置，找不到对应值时返回 -1
        System.out.println(list.lastIndexOf(20));   // 7
        System.out.println(list.lastIndexOf(205));   // -1，找不到对应值时返回 -1

        System.out.println("-----------------------------");

        /*
         remove(int index):移除指定index位置的元素，并返回此元素
         remove(Object o):移除对应数组中指定的元素（注意：这种方式不会返回要移除的元素）
         */
        Object remove = list.remove(3);// 根据索引删除
        System.out.println(remove);     // Person{name='Xiaobai', age=18}

        list.remove("EE");   // 根据元素删除
        System.out.println(list);   // [Laoyang, 20, QQ, WW, RR, 20]

        System.out.println("-----------------------------");

        // set(int index, OPbject ele):设置指定index位置的元素为ele
        list.set(3, "QWER");
        System.out.println(list);   // [Laoyang, 20, QQ, QWER, RR, 20]

        System.out.println("-----------------------------");

        // subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合，不会对原来的集合元素有影响
        List list1 = list.subList(0, 3);
        System.out.println(list1);  // [Laoyang, 20, QQ]
        System.out.println(list);   // [Laoyang, 20, QQ, QWER, RR, 20]
    }
}

class Person {
    private String name;
    private int age;

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

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

    public Person() {
    }
}

List 集合遍历的三种方式

Iterator迭代器、foreach()、for()

package com.laoyang.test.day2;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/**
 * @ClassName ListMethod
 * @Description： List 接口常用方法
 * @Author Laoyang
 * @Date 2021/10/2 9:41
 */
public class ListMethod {
    /**
     * List 集合遍历的三种方式
     * Iterator迭代器、foreach()、for()
     */
    @Test
    public void testTwo() {
        ArrayList list = new ArrayList();
        list.add("Laoyang");
        list.add(20);
        list.add(new Person("Xiaobai", 18));
        list.add(20);

        // 方式一：Iterator 迭代器
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("------------------------------");

        // 方式二：foreach()
        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));
        }
    }
}

class Person {
    private String name;
    private int age;

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

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

    public Person() {
    }
}

小结

增：add(Object ele)、addAll(Collection eles)
删：remove(int index)、remove(Object obj)
改：set(int index, Object ele)
查：get(int index)
插：add(int index, Object ele)
长度：size()
遍历：Iterator迭代器、foreach()、for()

Set 的使用

说明

Set 接口是 Collection 的子接口，set 接口没有提供额外的方法。
Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。
Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法。

特点：存储无序、不可重复的数据

使用要求

向 Set 中添加的数据，其所在的类一定要重写 hashCode() 和 equals()
重写的 hashCode() 和 equals() 尽可能保持一致性：相等的对象必须具有相等的散列码（哈希值）
重写两个方法的小技巧：对象中用作 equals() 方法比较的属性，都应该用来计算 hashCode() 值

通常参与计算 hashCode() 的对象的属性也应该参与到 equals() 中进行计算。

建议：IDEA 中有自动生成的 equals() 和 hashCode()，在开发中建议直接使用自动生成的，可以避免一些不必要的麻烦。

IDEA 快捷键：ALT + INS

了解

Set 接口中没有额外定义新的方法，使用的都是 Collection 接口中声明过的方法

Set 实现类

HashSet：作为 Set 接口的主要实现类；线程不安全；可以存储 null 值。

HashSet 底层结构：数组 + 链表（JDK7）
LinkedHashSet：作为 HashSet 的子类；遍历内部数据时，可以按照添加的顺序进行遍历。
ThreeSet：可以按照添加对象的指定属性进行排序。

Set 的无序性与不可重复性（以 HashSet 为例）

无序性：不等于随机性；存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
不可重复性：保证添加的元素按照 equals() 判断时，不能返回 true（因为返回 true 的时候就表示两个元素相同）；相同的元素只能添加一个。

大家可以参照下面的案例代码了解 HashSet 的使用和 HsahSet 中的无序性与不可重复性

案例

实体类

package com.laoyang.test.day3;

import java.util.Objects;

/**
 * @ClassName User
 * @Description：
 * @Author Laoyang
 * @Date 2021/10/8 11:02
 */
public class User implements Comparable {
    private String name;
    private int age;

    public User() {
    }

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

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

    /**
     * 重写 equals() 方法
     */
    @Override
    public boolean equals(Object o) {
        System.out.println("调用了 User 的 equals 方法");
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return age == user.age && Objects.equals(name, user.name);
    }

    /**
     * 重写 hashCode() 方法
     */
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

测试类

package com.laoyang.test.day3;

import org.junit.Test;
import java.util.*;

/**
 * @ClassName SetTest
 * @Description： Set 接口的使用
 * @Author Laoyang
 * @Date 2021/10/2 10:52
 */
public class SetTest {
    /**
     * 无序性
     * 不等于随机性；存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
     */
    @Test
    public void testOne() {
        // HashSet 会默认创建一个长度为 16 的数组
        Set set = new HashSet();
        set.add(123);
        set.add("QQ");
        set.add(new String("ABC"));
        set.add(12.5);

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

    /**
     * 不可重复性
     * 保证添加的元素按照 equals() 判断时，不能返回 true（因为返回 true 的时候就表示两个元素相同）；相同的元素只能添加一个。
     */
    @Test
    public void testTwo() {
        Set set = new HashSet();
        set.add(123);
        set.add("QQ");
        set.add(new String("ABC"));
        set.add(12.5);
        /*
        在 User 类中重写 hashCode() 方法用于判断两个对象的哈希值是否相同（如果哈希值相同，那么才会调用 equals() 方法进行判断）
        如果不重写 hashCode() 方法，则会默认调用 Object 类中的 hashCode() 方法，而 Object 中的 hashCode() 是随机进行判断的
        所以最后可能根本就没有与现有的相同值进行判断，而是直接插入在了不同的位置上,导致最后获取的还是两个相同的对象
         */
        set.add(new User("Xiaobai", 18));
        set.add(new User("Xiaobai", 18));

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            // 最后打印的结果中只会有一个 User 对象
            System.out.println(iterator.next());
        }
    }
}

如果想要看到最后打印两个相同元素的效果，只需要把 User 类中的 hashCode() 方法注释就可以了

LinkedHashSet 的使用

说明

LinkedHashSet 是 HashSet 的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据
优点：对于频繁的遍历操作，LinkedHashSet 的效率要高于 HashSet

案例

package com.laoyang.test.day3;

import org.junit.Test;
import java.util.*;

/**
 * @ClassName SetTest
 * @Description： Set 接口的使用
 * @Author Laoyang
 * @Date 2021/10/2 10:52
 */
public class SetTest {
    /**
     * LinkedHashSet 的使用
     */
    @Test
    public void testThree() {
        Set set = new LinkedHashSet();
        set.add(123);
        set.add("QQ");
        set.add(new String("ABC"));
        set.add(12.5);
        set.add(new User("Xiaobai", 18));
        set.add(new User("Xiaobai", 18));

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

TreeSet 的使用

说明

向 TreeSet 中添加的数据，要求是相同类的对象。
两种排序：自然排序（实现 Comparable）和定制排序（Comparator）
自然排序中，比较两个对象是否相同的标准为：compareTo() 返回 0，不会在意 equals()
定制排序中，比较两个对象是否相同的标准为：compare() 返回 0，不会在意 equals()

特点：有序，查询速度比 List 快

TreeSet 底层使用红黑树结构存储数据

案例

实体类-User

package com.laoyang.test.day3;

import java.util.Objects;

/**
 * @ClassName User
 * @Description：
 * @Author Laoyang
 * @Date 2021/10/8 11:02
 */
public class User implements Comparable {
    // 省略部分代码 - 这个类就是上面那个User类

    /**
     * 按照姓名从小到大进行排序
     */
    @Override
    public int compareTo(Object o) {
        if (o instanceof User) {
            User user = (User) o;
            //return this.name.compareTo(user.name);	// 只判断name是否相同
            int i = this.name.compareTo(user.name);
            if (i != 0) {
                return i;
            } else {
                return Integer.compare(this.age, user.age);
            }
        } else {
            throw new RuntimeException("类型不一致");
        }
    }
}

测试类

package com.laoyang.test.day3;

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

/**
 * @ClassName TreeSetTest
 * @Description： TreeSet 的使用
 * @Author Laoyang
 * @Date 2021/10/8 10:56
 */
public class TreeSetTest {
    /**
     * 自然排序
     */
    @Test
    public void testOne() {
        TreeSet set = new TreeSet();
        // 不能添加不同类的对象：ClassCastException
//        set.add(123);
//        set.add("QQ");
//        set.add(12.5);

        // 举例一
//        set.add(123);
//        set.add(-1);
//        set.add(233);
//        set.add(99);

        // 举例二
        set.add(new User("Tom", 22));
        set.add(new User("Jerry", 18));
        set.add(new User("Jim", 35));
        // 如果只是判断了 name，那么最后打印的时候只会出现一个 Mike
        set.add(new User("Mike", 6));
        set.add(new User("Mike", 15));

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

    /**
     * 定制排序
     */
    @Test
    public void testTwo() {
        Comparator comparator = new Comparator() {
            // 按照年龄从小到大排序
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof User && o2 instanceof User) {
                    User userA = (User) o1;
                    User userB = (User) o2;
                    return Integer.compare(userA.getAge(), userB.getAge());
                } else {
                    throw new RuntimeException("类型不一致");
                }
            }
        };
        TreeSet set = new TreeSet(comparator);
        set.add(new User("Tom", 18));
        set.add(new User("Jerry", 18));
        set.add(new User("Jim", 35));
        set.add(new User("Mike", 6));
        set.add(new User("Mike", 15));

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

Set 中添加元素的过程（以 HashSet 为例）

我们向 HashSet 中添加元素 A，首先调用元素 A 所在类的 hashCode() 方法，计算出元素 A 的哈希值。
然后该哈希值通过某种算法计算出在 HashSet 底层数组中的存放位置（也就是索引位置）。
判断数组当前位置上是否已经存在元素：

如果此位置没有其它元素，那么元素 A 则添加成功（情况一）
如果存在其它元素 B（或者以链表形式存在的多个元素），则比较元素 A 与 B 的哈希值

如果哈希值不相同，则元素 A 添加成功（情况二）
如果哈希值相同，则需要调用元素 A 所在类中的 equals() 方法

如果 equals() 方法返回 true，则表示元素 A 与元素 B 是相同的，添加失败
如果 equals() 方法返回 false，则表示元素 A 与元素 B 是不相同的，添加成功（情况三）

对于添加成功的情况二和情况三而言：元素 A 与已经存在指定索引位置上的数据以链表的方式进行存储

具体存储方式

JDK7：元素 A 放在数组中，指向原来的元素

在这里插入图片描述

JDK8：原来的元素放在数组中，指向元素 A

在这里插入图片描述

总结：七上八下

练习

练习一

创建员工类的 5 个对象，并把这些对象放入 TreeSet 集合中，分别按以下两种方式对集合中的元素进行排序，并遍历输出：

使员工类实现 Comparable 接口，并按 name 排序。
创建 TreeSet 时传入 Comparator 对象，按生日日期的先后排序。

员工生日类

package com.laoyang.test.day4;

/**
 * @ClassName MyDate
 * @Description： 生日类
 * @Author Laoyang
 * @Date 2021/10/10 10:16
 */
public class MyDate implements Comparable {
    private int year;
    private int month;
    private int day;

    public int getYear() {
        return year;
    }

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

    public int getMonth() {
        return month;
    }

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

    public int getDay() {
        return day;
    }

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

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

    public MyDate() {
    }

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

    @Override
    public int compareTo(Object o) {
        if (o instanceof MyDate) {
            MyDate myDate = (MyDate) o;
            // 判断年
            int compareA = Integer.compare(this.getYear(), myDate.getYear());
            if (compareA != 0) {
                return compareA;
            }
            // 判断月
            int compareB = Integer.compare(this.getMonth(), myDate.getMonth());
            if (compareB != 0) {
                return compareB;
            } else {
                // 判断日
                return Integer.compare(this.getDay(), myDate.getDay());
            }
        }
        throw new RuntimeException("类型不一致");
    }
}

员工类

package com.laoyang.test.day4;

/**
 * @ClassName Employee
 * @Description： 员工类
 * @Author Laoyang
 * @Date 2021/10/10 10:15
 */
public class Employee implements Comparable {
    private String name;
    private int age;
    private MyDate birthday;

    public Employee() {
    }

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

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

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

    public MyDate getBirthday() {
        return birthday;
    }

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

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

    @Override
    public int compareTo(Object o) {
        if (o instanceof  Employee) {
            Employee employee = (Employee) o;
            return this.name.compareTo(employee.name);
        }
        throw new RuntimeException("类型不一致");
    }
}

测试类

package com.laoyang.test.day4;

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

/**
 * @ClassName EmployeeTest
 * @Description： 测试类
 * @Author Laoyang
 * @Date 2021/10/10 10:21
 */
public class EmployeeTest {
    /**
     * 自然排序
     * 根据员工姓名进行排序
     */
    @Test
    public void testOne() {
        Employee employeeA = new Employee("David",18,new MyDate(2003,2,20));
        Employee employeeB = new Employee("Jerome",32,new MyDate(1988,5,18));
        Employee employeeC = new Employee("Aaron",21,new MyDate(2000,3,11));
        Employee employeeD = new Employee("Dennis",15,new MyDate(2006,6,1));
        Employee employeeE = new Employee("Robinson",19,new MyDate(2002,10,6));
        TreeSet set = new TreeSet();
        set.add(employeeA);
        set.add(employeeB);
        set.add(employeeC);
        set.add(employeeD);
        set.add(employeeE);

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

    /**
     * 定制排序
     * 根据员工生日信息进行排序
     */
    @Test
    public void testTwo() {
        Employee employeeA = new Employee("David",18,new MyDate(2003,2,20));
        Employee employeeB = new Employee("Jerome",32,new MyDate(1988,5,18));
        Employee employeeC = new Employee("Aaron",21,new MyDate(2000,3,11));
        Employee employeeD = new Employee("Dennis",15,new MyDate(2006,6,1));
        Employee employeeE = new Employee("Robinson",19,new MyDate(2003,10,6));

        Comparator comparator = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Employee && o2 instanceof Employee) {
                    Employee employeeA = (Employee) o1;
                    Employee employeeB = (Employee) o2;

                    MyDate myDateA = employeeA.getBirthday();
                    MyDate myDateB = employeeB.getBirthday();

                    // 方式一：在对应方法方法中编写对应判断
//                    // 判断年
//                    int compareA = Integer.compare(myDateA.getYear(), myDateB.getYear());
//                    if (compareA != 0) {
//                        return compareA;
//                    }
//                    // 判断月
//                    int compareB = Integer.compare(myDateA.getMonth(), myDateB.getMonth());
//                    if (compareB != 0) {
//                        return compareB;
//                    } else {
//                        // 判断日
//                        return Integer.compare(myDateA.getDay(), myDateB.getDay());
//                    }

                    // 方式二：在MyDate类中进行判断，然后直接调用
                    return myDateA.compareTo(myDateB);
                } else {
                    throw new RuntimeException("类型不一致");
                }
            }
        };

        TreeSet set = new TreeSet(comparator);
        set.add(employeeA);
        set.add(employeeB);
        set.add(employeeC);
        set.add(employeeD);
        set.add(employeeE);

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

练习二

在List内去除重复数字值，要求尽量简单

package com.laoyang.test.day4;

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

/**
 * @ClassName ListDeduplication
 * @Description： 练习二：在List内去除重复数字值，要求尽量简单
 * @Author Laoyang
 * @Date 2021/10/10 11:06
 */
public class ListDeduplication {
    public static List duplicateList(List list) {
        HashSet set = new HashSet();
        set.addAll(list);
        return new ArrayList(set);
    }

    public static void main(String[] args) {
        List list = new ArrayList();
        /*
          如果list中加入的是自定义的类，那么在自定义类中就需要重写 hashCode() 和 equals() 方法
         */
        list.add(new Integer(1));
        list.add(new Integer(2));
        list.add(new Integer(2));
        list.add(new Integer(4));
        list.add(new Integer(4));
        List list2 = duplicateList(list);
        for (Object integer : list2) {
            System.out.println(integer);
        }
    }
}

Map 的使用

介绍

Map：双列数据，存储 key-value 对的数据

Map 与 Collection 并列存在。用于保存具有映射关系的数据：key-value
Map 中的 key 和 value 都可以是任何引用类型的数据
Map 中的 key 用 Set 来存放，不允许重复，也就是说同一个 Map 对象所对应的类，必须重写 hashCode() 和 equals() 方法
常用 String 类作为 Map 的 “键”
key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value

常用方法

添加、删除、修改操作

方法	作用
Object put(Object key,Object value)	将指定key-value添加到(或修改)当前map对象中
void putAll(Map m)	将m中的所有key-value对存放到当前map中
Object remove(Object key)	移除指定key的key-value对，并返回value
void clear()	清空当前map中的所有数据

元素查询的操作

方法	作用
Object get(Object key)	获取指定key对应的value
boolean containsKey(Object key)	是否包含指定的key
boolean containsValue(Object value)	是否包含指定的value
int size()	返回map中key-value对的个数
boolean isEmpty()	判断当前map是否为空
boolean equals(Object obj)	判断当前map和参数对象obj是否相等

元视图操作的方法

方法	作用
Set keySet()	返回所有key构成的Set集合
Collection values()	返回所有value构成的Collection集合
Set entrySet()	返回所有key-value对构成的Set集合

案例

package com.laoyang.test.day5;

import org.junit.Test;
import java.util.*;

/**
 * @ClassName MapMethod
 * @Description： Map中的常用方法
 * @Author Laoyang
 * @Date 2021/10/13 11:04
 */
public class MapMethod {
    /**
     添加、删除、修改操作：
     Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
     void putAll(Map m):将m中的所有key-value对存放到当前map中
     Object remove(Object key)：移除指定key的key-value对，并返回value
     void clear()：清空当前map中的所有数据
     */
    @Test
    public void testOne(){
        // put(Object key,Object value)
        Map map = new HashMap();
        // 添加
        map.put("AA", 123);
        map.put(111, 321);
        map.put("bb", 56);
        // 修改
        map.put("AA", 99);

        System.out.println(map);    // {AA=99, bb=56, 111=321}

        // putAll(Map m)
        Map maps = new HashMap();
        maps.put("CC", 123);
        maps.put("DD", 123);
        map.putAll(maps);
        System.out.println(map);    // {AA=99, bb=56, CC=123, DD=123, 111=321}

        // remove(Object key)
        map.remove("CC");
        System.out.println(map);    // {AA=99, bb=56, DD=123, 111=321}

        // clear()：注意：该方法并不是将所有的元素变为null，而是直接变回刚创建的样子（没有任何元素）
        map.clear();
        System.out.println(map.size());  // 0
        System.out.println(map);    // {}
    }

    /**
     元素查询的操作：
     Object get(Object key)：获取指定key对应的value
     boolean containsKey(Object key)：是否包含指定的key
     boolean containsValue(Object value)：是否包含指定的value
     int size()：返回map中key-value对的个数
     boolean isEmpty()：判断当前map是否为空
     boolean equals(Object obj)：判断当前map和参数对象obj是否相等
     */
    @Test
    public void testTwo() {
        Map map = new HashMap();
        map.put("AA", 123);
        map.put(111, 321);
        map.put("bb", 56);

        // get(Object key)：如果找不到对应的 key 值，则返回 null
        System.out.println(map.get("BB"));    // null
        System.out.println(map.get("bb"));    // 56

        // containsKey(Object key)
        boolean A1 = map.containsKey("AA");
        boolean A2 = map.containsKey("aa");
        System.out.println(A1);   // true
        System.out.println(A2);   // false

        // containsValue(Object value)：如果存在相同的 value 值，那么只要找到第一个，就不会在往下继续找了
        boolean B1 = map.containsValue(123);
        boolean B2 = map.containsValue(345);
        System.out.println(B1);   // true
        System.out.println(B2);   // false

        // size()
        System.out.println(map.size());     // 3

        // isEmpty()
        boolean empty = map.isEmpty();
        System.out.println(empty);      // false

        Map map1 = new HashMap();
        System.out.println(map1.isEmpty());  // true

        // equals(Object obj)
        System.out.println(map.equals(map1));   // false
        Map maps = new HashMap();
        maps.put("AA", 123);
        maps.put(111, 321);
        maps.put("bb", 56);
        System.out.println(map.equals(maps));   // true
    }

    /**
     元视图操作（遍历）的方法：
     Set keySet()：返回所有key构成的Set集合
     Collection values()：返回所有value构成的Collection集合
     Set entrySet()：返回所有key-value对构成的Set集合
     Ps：因为都是集合的一种，所以都可以使用 for、foreach、iterator以及 jkd8 中的 Lambda 表达式
     */
    @Test
    public void testThree() {
        Map map = new HashMap();
        map.put("AA", 123);
        map.put(111, 321);
        map.put("bb", 56);

        // map.iterator()   // 不能直接调用 iterator()

        // keySet()：遍历所有的 key 值
        Iterator iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("-----------------------------");

        // values()：遍历所有的 value 值
        Collection values = map.values();
        for (Object value : values) {
            System.out.println(value);
        }

        System.out.println("-----------------------------");

        /*
        遍历所有的 key-value
         */
        // 方式一：entrySet()
        Set set = map.entrySet();
        Iterator iterator1 = set.iterator();
        while (iterator1.hasNext()) {
            Object obj = iterator1.next();
            // entrySet 集合中的元素都是 entry
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }

        System.out.println("-----------------------------");

        // 方式二
        Iterator key = map.keySet().iterator();
        while (key.hasNext()) {
            Object obj = key.next();
            Object value = map.get(obj);
            System.out.println(obj + " = " + value);
        }
    }
}

总结
增：put(Object key, Object value)、putAll(Map m)
删：remove(Object key)
改：put(Object key, Object value)
查：get(Object key)
长度：size()
遍历：keySet()、values()、entrySet()

Map 实现类

HashMap：作为 Map 的主要实现类（JDK1.2 发布）；线程不安全的，效率较高；存储 null 的 key 和 value；

JDK7 及之前的底层结构：数组 + 链表

JDK8 的底层结构：数组 + 链表 + 红黑树
LinkedHashMap：（JDK1.4 发布）；HashMap 的子类；保证遍历 Map 元素时，可以按照添加的顺序进行遍历（在原有的 HashMap 底层结构基础上，添加了一对指针，指向前一个和后一个元素）

对于频繁的遍历操作，此类执行的效率高于 HashMap
TreeMap：（JDK1.2 发布）；保证添加的 key-value 对进行排序，实现排序遍历（此时考虑 key 的自然排序或定制排序）；底层使用的是红黑树；
Hashtable：作为古老的实现类（JDK1.0 发布）；线程安全的，效率较低；不能存储 null 的 key 和 value；
Properties：（JDK1.0 发布）；Hashtable 的子类；常用来处理配置文件；key 和 value 都是 String 类型；

HashMap 的使用

HashMap 结构的理解

Map 中的 key：无序，且不能重复，使用 Set 存储所有的 key（key 所在类需要重写 equals() 和 hashCode()，以 HashMap 为例）
Map 中的 value：无序，可重复，使用 Collection 存储所有的 value（value 所在类需要重写 equals()）

一个键值对：key-value 构成了一个 Entry 对象
Map 中的 entry：无序且不可重复的，使用 Set 存储所有的 entry

HashMap 的底层实现原理

以 JDK7 为例：

HashMap map = new HashMap();   // 在实例化以后，底层创建了长度是 16 的一维数组 Entry[] table;
..假设前面我们已经put过一些数据了..
map.put(key1, value1);

下面可以看到 JDK7 在添加元素的过程是如何实现的

HashMap 添加元素的过程

JDK7

首先，调用 key1 所在类的 hashCode() 计算 key1 的哈希值；
然后，此哈希值经过某种算法计算后得到在 Entry 数组中的存放位置；
判断当前位置上否是有数据：

如果此位置上的数据为空，则 key1-value1 添加成功（情况一）
如果此位置上的数据不为空（也就表示此位置上存在一个或多个数据（以链表形式存在）），则比较 key1 和已存在的一个或多个数据的哈希值

如果 key1 与已存在的数据的哈希值都不相同，则 key1-value1 添加成功（情况二）
如果 key1 与已存在的某一个数据的哈希值相同，则调用 key1 所在类的 equals() 比较 key1 和已存在的一个或多个数据的值

如果 equals() 返回 false，则 key1-value1 添加成功（情况三）
如果 equals() 返回 true，则使用 value1 替换相同 key 的 value 值

比如现在有两个值 A 和 B，然后又添加了一个新的值 C，这时候 C 的 key（哈希值和值）和 A 的一模一样，这个时候就会把 C 的 value 值赋给 A 的 value
就相当于修改操作

补充：关于情况二和情况三：此时 key1-value1 和原来的数据以链表的方式存储

扩容：在不断的添加过程中，会涉及到扩容问题，当超出临界值（且要存放的位置非空）时，就会开始扩容。

默认会扩容为原来容量的两倍，并将原有数据复制到扩容好的数组中

JDK8 相较于 JDK7 在底层实现方面的不同

HashMap map = new HashMap(); // 底层没有创建一个长度为 16 的数组
JDK8 底层的数组是：Node[]，并不是 Entry
首次调用 put() 方法时，底层才会去创建长度为 16 的数组
JDK7 底层结构只有：数组 + 链表；JDK8 底层结构：数组 + 链表 + 红黑树

当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 并且当前数组长度 > 64，此时此索引位置上的所有数据改为使用红黑树存储。

这样做是为了提高我们的查询效率，一旦数据多起来了，那么使用数组查找的时候效率就会比较低（因为每次都需要完整遍历一遍）；而红黑树是有序的，小的排左边，大的排右边，在查找的时候就可以先排除一半的数据在进行查找，可以节省更多的时间。

部分源码

注意：中文注释是我自己加的，有些是根据自己的意思解释，有些是根据源码中的注释进行翻译。所以大家不要太较劲

JDK7

package java.util;
import java.io.*;

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
	/**
     * 默认初始容量 - 必须是 2 的幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;
	
	/**
     * 在构造函数中未指定时使用的负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
	
	/**
     * 最大容量，在两个带参数的构造函数隐式指定更高值时使用。必须是 2 的幂 <= 1<<30
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
	
	/**
     * 存放数据的数组。长度必须始终是 2 的幂
     */
    transient Entry<K,V>[] table;
	
	public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
	
	public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;   // 决定了数组创建的长度（比如我们手动设置HashMap的长度为 15，但其实还是创建了一个长度为16的数组）
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
		 /*
         threshold：临界值（capacity * loadFactor），HashMap 在扩容的时候并不是数组放不下的时候才开始扩容，因为可能以链表的方式一直向下存，所以一般达到临界值的时候就会开始扩容
         capacity * loadFactor = 16 * 0.75 = 12
         MAXIMUM_CAPACITY：最大容量
         */
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }
	
	/**
     * 将指定值与此映射中的指定键相关联。如果映射先前包含键的映射，则旧值将被替换
     *
     * @param key   与指定值相关联的键
     * @param value 要与指定键关联的值
     * @return 与 key 关联的先前值，如果 key 没有映射，则为 null。（null 返回也可以表明映射先前将 null 与 key 关联。）
     */
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        // 获取哈希值
        int hash = hash(key);
        // 通过对应的算法计算出数据在HashMap底层存放的位置
        int i = indexFor(hash, table.length);
        // 判断当前位置上是否存在元素
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 判断哈希值和值本身是否相同
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 如果哈希值和 key 值相同，则替换已存在 key 的 value 值
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        // 没有元素、哈希值不相同、值本身不相同时就会执行添加方法
        addEntry(hash, key, value, i);
        return null;
    }
	
	/**
	 * 计算哈希值
	 */
	final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode();

        // 此函数可确保在每个位位置仅相差常数倍的 hashCode 具有有限数量的冲突（在默认加载因子下约为 8）。
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
	
	/**
     * 根据哈希值找到对应的存放位置
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
	
	/**
	 * 扩容方法
	 * 需要扩容则先扩容在添加数据，不需要则可以直接执行添加方法
	 */
	void addEntry(int hash, K key, V value, int bucketIndex) {
        // 如果当前的临界值小于或等于 key-value 的映射数，并且当前数组位置不为空，则进行扩容操作
        if ((size >= threshold) && (null != table[bucketIndex])) {
            // 扩容：当达到临界值并且当前数组位置不为空，则默认会将数组扩容为原来的两倍
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
	
	/**
	 * 新增方法
	 */
	void createEntry(int hash, K key, V value, int bucketIndex) {
        // 将原有位置上的数据取出来
        Entry<K,V> e = table[bucketIndex];
        // 然后在将新造的 Entry 对象放到当前位置上，以链表方式存放（从上往下存，跟 HashSet（JDK7）差不多）
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
	
	Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

JDK8

package java.util;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
	/**
     * 在构造函数中未指定时使用的负载因子。
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
	
	/**
     * 哈希表的负载因子
     * @serial
     */
    final float loadFactor;
	
	/**
	 * 存放数据的数组。
	 */
	transient Node<K,V>[] table;
	
	/**
     * 构造器
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
	
	/**
     * 将指定值与此映射中的指定键相关联。如果映射先前包含键的映射，则旧值将被替换
     *
     * @param key   与指定值相关联的键
     * @param value 要与指定键关联的值
     * @return 与 key 关联的先前值，如果 key 没有映射，则为 null。（null 返回也可以表明映射先前将 null 与 key 关联。）
     */
	public V put(K key, V value) {
        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);
    }
	
    /**
     * 实现 Map.put 及相关方法
     *
     * @param hash 密钥的散列
     * @param key 钥匙
     * @param value 要放置的值
     * @param onlyIfAbsent 如果为 true，则不要更改现有值
     * @param evict 如果为 false，则表处于创建模式
     * @return 以前的值，如果没有，则为 null
     */
	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;
        if ((p = tab[i = (n - 1) & hash]) == null)
            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;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
	
	/**
     * 初始化或加倍表大小。
	 * 如果为空，则根据字段阈值中持有的初始容量目标进行分配。
	 * 否则，因为我们使用的是 2 的幂扩展，所以每个 bin 中的元素必须保持相同的索引，或者在新表中以 2 的幂的偏移量移动
     */
	final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        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
            newCap = DEFAULT_INITIAL_CAPACITY;
            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);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = 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;
                        }
                    }
                }
            }
        }
        return newTab;
    }
	
	/**
     * 除非表太小，否则替换给定哈希索引处 bin 中的所有链接节点，在这种情况下改为调整大小。
     */
	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();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
}

HashMap 源码中的重要常量

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量：16
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
threshold：扩容的临界值，= 容量 * 填充因子：16 * 0.75 = 12
TREEIFY_THRESHOLD：Bucket 中链表长度大于该默认值，转化为红黑树：8
MIN_TREEIFY_CAPACITY：桶中的 Node 被树化时最小的 hash 表容量：64

这里只举例个别几个，还有一些大家可自行查看源码

LinkedHashMap 的使用

LinkedHashMap 是 HashMap 的子类
在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序
与 LinkedHashSet 类似

LinkedHashMap 底层原理（了解）

LinkedHashMap 底层使用的结构与 HashMap 相同，因为 LinkedHashMap 继承于 HashMap
区别：LinkedHashMap 内部提供了 Entry，替换了 HashMap 中的 Node

LinkedHashMap 内部类：

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);
   }
}

HashMap中的内部类

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

TreeMap 的使用

介绍

TreeMap 存储 Key-Value 对时，需要根据 key-value 对进行排序。 TreeMap 可以保证所有的 Key-Value 对处于有序状态。
TreeSet 底层使用红黑树结构存储数据。
向 TreeMap 中添加 key-value，要求 key 必须是由同一个类创建的对象，因为要按照 key 进行排序：自然排序、定制排序。

注意：只能根据 key 进行排序，不能根据 value 排序！！！

案例

package com.laoyang.test.day5;

import org.junit.Test;
import java.util.*;

/**
 * @ClassName TreeMapTest
 * @Description： TreeMap 的使用
 * @Author Laoyang
 * @Date 2021/10/13 15:08
 */
public class TreeMapTest {
    /**
     * 自然排序
     */
    @Test
    public void testOne() {
        TreeMap map = new TreeMap();
        User userA = new User("Tom", 22);
        User userB = new User("Jerry", 18);
        User userC = new User("Jim", 35);
        User userD = new User("Mike", 6);
        map.put(userA, 60);
        map.put(userB, 76);
        map.put(userC, 32);
        map.put(userD, 100);
        Set set = map.entrySet();
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object obj = iterator.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "的成绩为：" + entry.getValue());
        }
    }

    /**
     * 定制排序
     */
    @Test
    public void testTwo() {
        Comparator comparator = new Comparator() {
            // 根据年龄排序
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof User && o2 instanceof User) {
                    User userA = (User) o1;
                    User userB = (User) o2;
                    return Integer.compare(userA.getAge(), userB.getAge());
                }
                throw new RuntimeException("类型不一致");
            }
        };

        TreeMap map = new TreeMap(comparator);
        User userA = new User("Tom", 22);
        User userB = new User("Jerry", 18);
        User userC = new User("Jim", 35);
        User userD = new User("Mike", 6);
        map.put(userA, 60);
        map.put(userB, 76);
        map.put(userC, 32);
        map.put(userD, 100);
        Set set = map.entrySet();
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object obj = iterator.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "的成绩为：" + entry.getValue());
        }
    }
}

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

    /**
     * 重写 equals() 方法
     */
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return age == user.age &&
                Objects.equals(name, user.name);
    }

    /**
     * 重写 hashCode() 方法
     */
    @Override
    public int hashCode() {
        return Objects.hash(name, 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;
    }

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

    public User() {
    }

    /**
     * 按照姓名从小到大进行排序
     */
    @Override
    public int compareTo(Object o) {
        if (o instanceof User) {
            User user = (User) o;
            int i = this.name.compareTo(user.name);
            if (i != 0) {
                return i;
            } else {
                return 0;
            }
        }
        throw new RuntimeException("类型不一致");
    }

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

Hashtable 的使用

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

Properties 的使用

介绍

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

案例

配置文件 - jdbc.properties

username=root
password=123456

该文件创建在父工程下面（因为这里只是测试一下效果，所以创建后就可以随便写一点东西）

注意：配置文件中等号（=）两边不能出现空格，比如 name = “AAA”

测试类

package com.laoyang.test.day5;

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Properties;

/**
 * @ClassName PropertiesTest
 * @Description： Properties 的使用
 * @Author Laoyang
 * @Date 2021/10/13 15:28
 */
public class PropertiesTest {
    /**
     Properties：常用来处理配置文件，key 和 value 都是 String 类型
     */
    public static void main(String[] args) {
        FileInputStream stream = null;
        try {
            Properties properties = new Properties();
            stream = new FileInputStream("jdbc.properties");
            properties.load(stream);
            String name = properties.getProperty("username");
            String password = properties.getProperty("password");
            System.out.println("账号为：" + name + "，密码为：" + password);
        } catch (IOException e) {
            System.out.println(e.getMessage());
        } finally {
            if (stream != null) {
                try {
                    stream.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

有时候写配置文件导致乱码，可能是编码格式没有设置好

扩展：如果不想配置文件出现乱码，则需要在创建配置文件之前，设置好对应的编码格式（如果已经创建好文件并且已经出现乱码，则需要先删除对应的配置文件，然后在进行编码设置，之后才能接着编写，否则并不会实现正确的效果）
如果是使用 IDEA ，那么需要把 File > Editor > File Encodings > Iransparent native-to-ascii conversion 勾上

Collections 工具类的使用

操作数组的工具类：Arrays

介绍

Collections 是一个操作 Set、List 和 Map 等集合的工具类
Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

常用方法

排序操作

方法	作用
reverse(List list)	反转集合中的所有元素
shuffle(List list)	将集合元素进行随机排序
sort(List list)	将集合元素进行自然排序
sort(List list, Comparator com)	将集合元素进行定制排序
swap(List list，int i， int j)	交换集合中指定位置上的元素

查找、替换

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

需要注意 copy()

同步控制

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

方法	作用
synchronizedCollection(Collection c)	返回由指定集合支持的同步（线程安全）集合
synchronizedList(List list)	返回由指定列表支持的同步（线程安全）列表
synchronizedMap(Map map)	返回由指定Map支持的同步（线程安全）映射
synchronizedSet(Set set)	返回由指定集合支持的同步（线程安全）集
synchronizedSortedMap(SortedMap m)	返回由指定的排序映射支持的同步（线程安全）排序映射
synchronizedSortedSet(SortedSet s)	返回由指定的排序集支持的同步（线程安全）排序集

案例

package com.laoyang.test.day6;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @ClassName CollectionUtil
 * @Description： Collections 工具类的使用
 * @Author Laoyang
 * @Date 2021/10/13 15:59
 */
public class CollectionsUtil {
    /**
     排序操作：（均为static方法）
     reverse(List)：反转 List 中元素的顺序
     shuffle(List)：对 List 集合元素进行随机排序
     sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
     sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
     swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
     */
    @Test
    public void testOne() {
        List list = new ArrayList();
        list.add(22);
        list.add(57);
        list.add(33);
        list.add(19);
        System.out.println(list);   // [22, 57, 33, 19]

//        Collections.reverse(list);      // 反转集合元素
//        Collections.shuffle(list);      // 将集合元素进行随机排序
//        Collections.sort(list);         // 将集合元素进行自然排序，如果想使用定制排序，则需要在添加一个 Comparator 参数
        Collections.swap(list, 1, 3);   // 交换集合中指定位置的元素

        System.out.println(list);
    }

    /**
     查找、替换
     Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
     Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
     Object min(Collection)：根据元素的自然顺序，返回给定集合中的最小元素
     Object min(Collection，Comparator)：根据元素的定制顺序，返回给定集合中的最小元素
     int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
     void copy(List dest,List src)：将src中的内容复制到dest中
     boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值
     */
    @Test
    public void testTwo() {
        List list = new ArrayList();
        list.add(22);
        list.add(57);
        list.add(57);
        list.add(33);
        list.add(19);
        System.out.println(list);   // [22, 57, 57, 33, 19]

        // max(Collection coll)：根据自然排序找到集合中的最大值，定制排序需添加 Comparator 参数
        System.out.println(Collections.max(list));    // 57

        // min(Collection coll)：根据自然排序找到集合中的最小值，定制排序需添加 Comparator 参数
        System.out.println(Collections.min(list));    // 19

        // frequency(Collection coll, Object obj)：
        System.out.println(Collections.frequency(list, 57));    // 2

        System.out.println("------------------------");

        //copy(List dest, List src)：复制，将 src 中的值复制到 dest 中
        /*
         // 报异常：java.lang.IndexOutOfBoundsException: Source does not fit in dest
         List list1 = new ArrayList();
         Collections.copy(list1, list);
         */

        // 正确写法
        List list1 = Arrays.asList(new Object[list.size()]);
        System.out.println(list1.size());   // 5
        Collections.copy(list1, list);      // 执行成功

        System.out.println(list1);

        System.out.println("------------------------");

        //replaceAll(List list，Object oldVal，Object newVal)：使用新值（oldVal）替换 List 中的旧值（newVal）
        Collections.replaceAll(list, 22, 99);

        System.out.println(list);   // [99, 57, 57, 33, 19]
    }

    /**
     Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，
     从而可以解决多线程并发访问集合时的线程安全问题
     */
    @Test
    public void testThree() {
        List list = new ArrayList();
        list.add(22);
        list.add(57);
        list.add(57);
        list.add(33);
        list.add(19);
        System.out.println(list);   // [22, 57, 57, 33, 19]

        // 返回的 list1 就是线程安全的
        List list1 = Collections.synchronizedList(list);
    }
}

练习一

请从键盘随机输入10个整数保存到List中，并按倒序、从大到小的顺序显示出来

package com.laoyang.test.day6;

import java.util.*;

/**
 * @ClassName Practise
 * @Description： 练习一
 * @Author Laoyang
 * @Date 2021/10/13 17:15
 */
public class ExerciseOne {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        List list = new ArrayList();
        int j;
        for (int i = 0; i < 10; i++) {
            System.out.print("请输入整数：");
            j = input.nextInt();
            list.add(j);
        }
        Collections.sort(list);
        Collections.reverse(list);
        System.out.println(list);
    }
}

练习二

将学生名与考试分数录入到集合中，并按分数显示前三名成绩学员的名字

package com.laoyang.test.day6;

import org.junit.Test;
import java.util.*;

/**
 * @ClassName ExerciseTwo
 * @Description： 练习二
 * @Author Laoyang
 * @Date 2021/10/13 17:28
 */
public class ExerciseTwo {
    @Test
    public void testOne() {
        List list = new ArrayList();
        list.add(new Student("Tom", 60));
        list.add(new Student("Jerry", 80));
        list.add(new Student("Jim", 73));
        list.add(new Student("Mike", 52));
        list.add(new Student("Noob", 90));

        Collections.sort(list, new Comparator<Object>() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Student && o2 instanceof Student) {
                    Student stuA = (Student) o1;
                    Student stuB = (Student) o2;
                    return -Double.compare(stuA.getFraction(), stuB.getFraction());
                }
                throw new RuntimeException("类型不一致");
            }
        });

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

class Student {
    private String name;
    private double fraction;

    public Student() {
    }

    public Student(String name, double fraction) {
        this.name = name;
        this.fraction = fraction;
    }

    public String getName() {
        return name;
    }

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

    public double getFraction() {
        return fraction;
    }

    public void setFraction(double fraction) {
        this.fraction = fraction;
    }

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

面试题

一、ArrayList、LinkedList 和 Vector 的相同点与不同点？

相同点：三个类都实现了 List 接口，存储数据的特点相同（都是有序且可重复的数据）

不同点：

ArrayList：作为 List 接口的主要实现类（JDK1.2出现）；执行效率高（线程不安全的）；底层使用 Object[] elementData 进行存储；

LinkedList：JDK1.2出现；对于频繁的插入、删除操作使用此类效率比 ArrayList 要高；底层使用双向链表存储；

Vector：作为 List 接口的古老实现类（JDK1.0出现）；执行效率低（线程安全的）；底层使用 Object[] elementData 进行存储；

List 接口也是 JDK1.2 出现的

二、下面代码最终打印的结果是什么?

题一、

package com.laoyang.test.day2;

import org.junit.Test;
import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName ListInterviewQuestions
 * @Description： 面试题
 * @Author Laoyang
 * @Date 2021/10/2 10:43
 */
public class ListInterviewQuestions {
    @Test
    public void testOne() {
        List list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        updateList(list);
        System.out.println(list);  //1,2
    }

    private static void updateList(List list) {
        // 默认情况下去删除整型元素的时候，会优先调用 List 中的 remove(int index)，而不是 remove(Object obj)
        list.remove(2);    				   // 根据下标删除，[1, 2]
        //list.remove(new Integer(2));     // 根据元素删除，[1, 3]
    }
}

主要考察点：区分 list 中 remove(int index) 和 remove(Object obj)

这里写了两种方式，大家可以打开注释进行测试，查看最后的效果

题二、

package com.laoyang.test.day4;

import org.junit.Test;
import java.util.HashSet;
import java.util.Objects;

/**
 * @ClassName Set
 * @Description： 面试题
 * @Author Laoyang
 * @Date 2021/10/10 11:09
 */
public class SetInterviewQuestions {
    @Test
    public void test() {
        HashSet set = new HashSet();
        Person p1 = new Person(1001,"AA");
        Person p2 = new Person(1002,"BB");
        set.add(p1);
        set.add(p2);

        // 将 set 中 p1 的 name 值进行修改
        p1.name = "CC";
        /*
         此时的 remove 找的是 1001，CC 的存放位置
         而 p1 在存储的时候是根据 1001，AA 的哈希值进行存储的
         所以这个时候 remove 是找不到 p1 的，所以也就无法删除成功
         */
        set.remove(p1);
        System.out.println(set);    // 1002，BB；1001，CC

        /*
          因为 p1 是根据 1001，AA 找到的位置进行存放的，即使后面修改成了 1001，CC，位置也是没有发生改变的
          所以这里的 1001，CC 是可以添加成功的
         */
        set.add(new Person(1001,"CC"));
        System.out.println(set);     // 1002，BB；1001，CC；1001，CC

        /*
         这里的 1001，AA 的哈希值和 p1 是一致的，但是 p1 的值现在是 1001，CC
         所以哈希值相同以后，在调用 equals() 判断两个对象的值是否相同，AA != CC，所以可以添加成功
         */
        set.add(new Person(1001,"AA"));
        System.out.println(set);    // 1002，BB；1001，CC；1001，CC；1001，AA
    }
}

class Person {
    public int id;
    public String name;

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

    public Person() {
    }

    @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);
    }
}

三、 HashMap 的底层实现原理？

如果上面的看不懂的话那就自行百度吧

四、HashMap 和 Hashtable 的相同点和不同点？

如果上面的看不懂的话那就自行百度吧

五、CurrentHashMap 与 Hashtable 的相同点和不同点？

暂时略过

六、Collection 和 Collections 的区别？

Collection 是存储单列接口的集合接口
Collections 是操作 Collection 的工具类

七、负载因子的大小，对 HashMap 有什么影响？

负载因子的大小决定了 HashMap 的数据密度
负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长，造成查询或插入时的比较次数增多，性能会下降。
负载因子越小，就越容易触发扩容，数据密度也越小，也就以为着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高，但是会浪费一定的内容空间，经常扩容也会影响性能。
按照其它语言的参考及研究经验，会考虑将负载因子设置为 0.7~0.75，此时的平均检索长度接近于常数。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)