Java 基础学习（十四）Map集合与Set集合

1 Map集合

1.1 Map接口

1.1.1 Map接口概述

Map接口是一种双列集合。Map的每个元素都包含一个键对象Key和一个值对象Value ，键对象和值对象之间存在对应关系，这种关系称为映射（Mapping）。

Map接口中的元素，可以通过 key 找到 value，因此：

• 一个键只能映射一个值，但允许多个不同的键映射到同一个值上
• 键对象Key必须是唯一的，不允许重复
• 值对象Value允许重复

如下图所示：

1.1.2 Map接口的实现类

Map接口常用的实现类包括HashMap、TreeMap和LinkedHashMap：

1.1.3 Map接口的常用方法

Map是实现映射集合的根接口。Map接口定义了关于映射集合的相关的操作方法，常用方法如下所示：

1.1.4 【案例】Map常用方法示例

编写代码，测试Map的常用方法。代码示意如下：

import java.util.*;
public class MapDemo1 {
    public static void main(String[] args) {
        Map<Integer,String> map = new HashMap<>();
        // 存放元素，以键值对形式
        map.put(1, "Tom");
        map.put(3, "Jerry");
        map.put(5, "Lucy");
        // 获取元素，通过key获取value
        String value = map.get(1);
        System.out.println("value: " + value); // Tom
        String value2 = map.get(2); // 尝试通过不存在的key获取value
        System.out.println("value2: " + value2); // 返回null
        // 存放已存在的key，则替换value，并返回被替换的value
        String oldValue = map.put(1, "Tony");
        System.out.println("oldValue: "+oldValue); // Tom
        System.out.println("value: " + map.get(1)); // Tony
        // 支持基于key删除键值对，返回被删除的value
        map.remove(1);
        System.out.println("value: " + map.get(1)); // null
        // 查询map中是否包含了某个key 或 value
        boolean flag1 = map.containsKey(3);
        System.out.println("containsKey 3: "+flag1);
        boolean flag2 = map.containsValue("Tom");
        System.out.println("containsValue Tom: "+flag2);
        // 返回包含了所有key的集合
        Set<Integer> keys = map.keySet();
        System.out.println("keys: " + keys); // [3, 5]
        // 返回包含了所有value的集合
        Collection<String> values = map.values();
        System.out.println("values: " + values); // [Jerry, Lucy]
    }
}

1.2 哈希表

1.2.1 初识哈希表

哈希表（Hash Table），也称为散列表，是一种常见的数据结构，用于存储和检索键值对（key-value pairs）。它基于哈希函数将关键字（key）映射到数组索引（下标），以便快速访问和操作数据。

我们通过一个对比案例来介绍哈希表的作用及原理。在这个案例中，我们需要按顺序添加5个键值对，分别是(5, Lucy), (22, Tom), (131, Jerry), (666, Bob), (23, Alice)。

首先，我们来看一下不使用哈希表的情况，默认按照元素的添加顺序将键值对的键存放到数组中，如下图所示。

这种方式的缺点在于使用key查询数据时，最差的情况下需要遍历整个数组。

接下来，我们来看一下使用哈希表的情况。想使用哈希表，我们需要先定义一个哈希函数。简单的说，哈希函数是计算一个key对应的数组索引的函数。

在本例中，我们使用的哈希函数如下：

此时计算得到的key与数组下标的关系如下：

按照这一规则，元素在数组中的存放位置如下：

采用这样的方式，使用key查询数据时，可以使用相同的规则计算索引，直接通过计算的结果获取数组该位置元素，查询效率高。

在许多情况下，哈希表比搜索树或任何其他表查找结构平均更有效。 因此，哈希表被广泛用于多种计算机软件，特别是关联数组、数据库索引、缓存和集合。

1.2.2 哈希算法

哈希函数（也称Hash算法）有多种实现方法，比如“除留取余法”，以及“直接定址法”、“数字分析法”、“分段叠加法”、“平均取中法”、“伪随机数法”等。

除留取余法如下图所示：

1.2.3 哈希冲突

两个不同的输入值，根据同一哈希函数计算出的索引相同的现象称为哈希冲突，也称为哈希碰撞。

例如，假设数组的长度为10，使用除留取余法，元素18和元素28对应的数组索引均为8，即发生了哈希冲突。

衡量一个Hash算法的重要指标就是发生冲突的概率，以及发生冲突的解决方案。任何Hash函数基本都无法彻底避免冲突，常见的解决冲突的方法有以下几种：

1、开放地址法：一旦发生了冲突，就去寻找下一个空的哈希地址，只要哈希表足够大，总能找到空的哈希地址，并将元素存入。

2、再Hash法：当Hash地址发生冲突时使用其他函数计算另一个Hash函数地址，直到不再产生冲突为止。

3、建立公共溢出区：将Hash表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表。

4、链地址法：将Hash表的每个单元作为链表的头节点，所有Hash地址为i的元素构成一个同义词链表，即发生冲突时就把该元素链接在该单元为头节点的链表的尾部。

1.3 HashMap

1.3.1 HashMap概述

HashMap类是Map接口最常用的实现类之一，内部基于哈希表存储键值对数据，以提供高效的插入、删除和查找操作。HashMap在实际开发中广泛应用于缓存、索引、数据存储和快速查找等场景。

HashMap的内部使用了一个Node类来表示存储在哈希桶（数组）中的键值对。Node类是HashMap的内部私有静态类。

Node类包含了以下几个主要的字段：

• final int hash：存储键的哈希码，用于确定键值对在桶数组中的位置。
• final K key：存储键的值。
• V value：存储与键相关联的值。
• Node<K,V> next：用于处理哈希冲突，存储下一个Node节点的引用，形成链表或红黑树结构。

1.3.2 【案例】HashMap遍历示例

编写代码，测试HashMap的遍历。代码示意如下：

import java.util.*;
public class HashMapDemo1 {
    public static void main(String[] args) {
        Map<Integer,String> map = new HashMap<>();
        // 存放元素，以键值对形式
        map.put(5, "Tom");
        map.put(3, "Jerry");
        map.put(9, "Lucy");
        // 通过keySet()方法遍历
        Set<Integer> keySet = map.keySet();
        for(Integer key : keySet) {
            // 基于key查询value，多了一步查询
            System.out.println("key: " + key+" value: " + map.get(key));
        }
        // 通过entrySet方法遍历（推荐），一次查询出全部键值对
        Set<Map.Entry<Integer,String >> entrySet = map.entrySet();
        for(Map.Entry<Integer,String> entry:entrySet){
            System.out.println("key: " + entry.getKey()+" value: " + entry.getValue());
        }
    }
}

1.3.3 hashCode方法

在前面的案例中，我们使用的key是整型，可以直接参与取余运算。如果我们想要使用字符串或者自定义类型（例如Student）作为key，是否还能使用哈希表呢？答案是肯定的。

Java在Object类中设计了hashCode方法，用于返回当前对象的哈希值。通过下面的源码可以看到，该方法返回的是一个int类型的值。

通过这样的设计，任意一个Java对象均可以作为哈希表的key。

1.3.4 put方法的执行流程

当使用HashMap对象的put方法存储一个键值对时，一般会经过以下几步：

1、计算Key的哈希值。

• 如果Key为null，则哈希值为0
• 如果Key不为null，调用Key的hashCode方法，计算Key的哈希值

2、如果内部数组没有被初始化，会先初始化内部数组。

3、通过Key的哈希值计算Key在桶（数组）中的位置。

4、如果桶中目标位置没有元素，则创建Node对象，存储键值对数据，并将Node对象保存到桶中目标位置。

5、如果桶中目标位置有元素（注意可能有多个），则将key与这些元素的key进行比较。

• 如果Key与某个元素的Key相等（== 或 equals），则使用新存入的Value覆盖旧的Value
• 如果Key与桶中该位置的所有元素都不相等，则创建新的Node对象，存储键值对数据，并追加到链表中

1.3.5 【案例】put方法示例

编写代码，测试HashMap的遍历。代码示意如下：

import java.util.HashMap;
import java.util.Map;
public class HashMapDemo2 {
    public static void main(String[] args) {
        // 使用包裹类作为Key
        Map<Integer, String> map1 = new HashMap<>();
        map1.put(1, "Tom");
        map1.put(1, "Jerry");
        System.out.println(map1.get(1)); // Jerry
        // 使用自定义类作为Key
        Map<Student, String> map2 = new HashMap<>();
        Student s1 = new Student("Tom", 18);
        Student s2 = new Student("Tom", 18);
        map2.put(s1, "Tom");
        map2.put(s2, "Jerry");
        System.out.println(map2.get(s1)); // Tom
        System.out.println(map2.get(s2)); // Jerry
        // hashCode不同导致不会调用equals方法
        System.out.println("s1.hashCode:"+s1.hashCode()); // 990368553
        System.out.println("s1.hashCode:"+s2.hashCode()); // 1096979270
    }
}
class Student{
    String name;
    Integer age;
    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public boolean equals(Object obj) { // 案例中的equals并没有被调用
        System.out.println("equals方法被调用了:" + obj);
        return super.equals(obj);
    }
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

1.3.6 重写hashCode方法

结合put方法的执行流程及上面案例的执行效果我们可以发现：使用hashCode方法的默认实现逻辑，可能导致HashMap无法正确识别两个逻辑相等的Key。

因此，在使用自定义类型作为HashMap中的Key时，需要重写该类的hashCode方法，以满足以下要求。

1、多次调用同一个对象的hashCode方法，应返回相同的哈希码。

2、如果两个对象被equals()方法判断为相等，那么它们的hashCode()方法应该返回相同的哈希码。

3、如果两个对象被equals()方法判断为不相等，不强制要求它们的hashCode()方法返回不同的哈希码，但是开发者应该了解，返回不同的哈希码有利于提高哈希表的性能。

集成式开发环境如IDEA和Eclipse均提供了重写hashCode和equals方法的支持，开发者可直接使用，提高开发效率。

1.3.7 【案例】HashMap应用示例

请基于HashMap重构前一天的ArrayList应用示例，对比HashMap和ArrayList在使用上的差别。

1、将前一天的Subject、Exam和ArrayListDemo2三个类拷贝到今天的package中。

2、将ArrayListDemo2更名为HashMapDemo3。

3、分析并重构HashMapDemo3中的代码，在适合使用HashMap的地方将ArrayList替换为HashMap。

import java.io.BufferedReader;
import java.io.FileReader;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.*;
public class HashMapDemo3 {
    public static void main(String[] args) {
        String subjectPath = "d:/data/subject.csv";
        String examPath = "d:/data/exam.csv";
        HashMap<Integer, Subject> subjects = readSubjects(subjectPath);
        System.out.println(subjects); // 打印科目信息
        HashMap<Integer, Exam> exams = readExams(examPath, subjects);
        System.out.println(exams); // 打印考试信息
        // 筛选出考试时间在10点之后的考试信息
        DateTimeFormatter formatter =
                DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss");
        for (Exam exam : exams.values()) {
            LocalDateTime ldt = LocalDateTime
                                    .parse(exam.getStartTime(),formatter);
            if (ldt.getHour()>9){
                System.out.println(exam);
            }
        }
    }
    /**
     * 读取文件中的数据，每行生成一个考试对象，存储到集合中
     * @param path
     * @param subjects
     * @return
     */
    public static HashMap<Integer, Exam> readExams(String path
                                    , Map<Integer, Subject> subjects) {
        List<String> lines = readLines(path);
        HashMap<Integer, Exam> exams = new HashMap<>();
        for (String line : lines) {
            String[] arr = line.split(",");
            Exam exam = new Exam();
            exam.setId(Integer.parseInt(arr[0]));
            exam.setName(arr[1]);
            exam.setStartTime(arr[2]);
            exam.setDuration(Integer.parseInt(arr[3]));
            // 从map中查询科目对象
            exam.setSubject(subjects.get(Integer.parseInt(arr[4])));
            exams.put(exam.getId(), exam);
        }
        return exams;
    }
    /**
     * 读取文件中的数据，每行生成一个科目对象，存储到集合中
     * @param path
     * @return
     */
    public static HashMap<Integer, Subject> readSubjects(String path){
        List<String> lines = readLines(path);
        HashMap<Integer, Subject> subjects = new HashMap<>();
        for(String line : lines){
            String[] arr = line.split(",");
            Subject subject = new Subject();
            subject.setId(Integer.parseInt(arr[0]));
            subject.setName(arr[1]);
            subjects.put(subject.getId(), subject);
        }
        return subjects;
    }
    /**
     * 读取文件中的数据，每行生成一个字符串，存储到集合中
     * @param path
     * @return
     */
    public static ArrayList<String> readLines(String path){
        ArrayList<String> lines = new ArrayList<>();
        try(
            FileReader fr = new FileReader(path);
            BufferedReader br = new BufferedReader(fr);
        ){
            String line = br.readLine();
            line = br.readLine(); // 跳过第一行
            while(line != null){
                lines.add(line);
                line = br.readLine();
            }
        }catch (Exception e){
            e.printStackTrace();
        }
        return lines;
    }
}

1.4 HashMap原理

1.4.1 HashMap的容量

HashMap中使用数组作为存储元素的桶，对应的内部属性为table，如下图所示。HashMap的内部数组不是在创建HashMap对象时初始化，而是在首次存入元素时进行初始化，以减少对内存的占用。

从源码注释中我们可以发现，官方规定table的长度总是2的幂，即2的N次方。这样设计的原因是为了保证HashMap的速度足够快。这是一个需要特别注意的面试高频考点。

我们知道，不论存操作还是取操作，HashMap都使用除留取余法通过key的哈希值计算key在桶中的索引。如果能优化这一计算的速度，将会大幅优化HashMap存取操作的速度。

在数学中有这样一条公式：X % 2^n = X & (2^n - 1) 。简单的说，当X对Y取余时，如果Y是2的幂，则可以将取余运算转换为位运算，以提高计算速度。

综上，HashMap的容量始终是2的幂，以保证内部高效的哈希运算。

1.4.2 HashMap的初始容量

与ArrayList相似，HashMap的初始容量分为默认容量和手动指定两种情况。

当使用无参构造器创建HashMap对象时，table的初始化长度为16，由如下的静态常量指定。

因此，默认情况下，HashMap的默认容量为16。

HashMap支持使用带参构造器HashMap(int initialCapacity)来创建HashMap对象，并指定内部数组的初始化长度。

此处需要注意，HashMap并不会直接使用开发者指定的长度作为内部数组的长度，而是会通过一个内部方法，计算大于开发者指定长度的最小的2的幂作为内部数组的长度。

因此，当开发者指定初始长度时，HashMap的容量为大于该长度的最小的2的幂。

1.4.3 HashMap的扩容

HashMap中提供了桶的自动扩容机制，在满足特定的条件时自动将桶的长度扩容到原来的两倍。

想要理解桶的扩容条件，需要先分清楚4个概念：

• 1、容量（capacity）：HashSet内部数组的长度，默认长度为16
• 2、大小（size）：HashSet中实际存储的元素的个数，默认为0
• 3、负载因子（loadFactor）：用来衡量HashSet“满”的程度，默认值为0.75f
• 4、临界值（threshold）：当size超过临界值时，HashSet将会扩容，threshold = capacity * loadFactor

对于一个默认的HashSet来说，临界值=16 * 0.75 = 12，即当存储了超过12个元素时，HashSet会自动扩容，将容量扩大到原来的2倍，即32。

扩容后，还会对所有的元素进行一次rehash操作，相当于对所有的元素重新做一遍Hash运算，是一项比较耗时的操作。

由于存在上述的设计，因此开发者手动指定HashMap的初始容量时，需要计算合适的容量，而不是直接传入要存储元素的个数。具体可参考《阿里巴巴 Java开发手册》中的建议。

1.4.4 树化与退化

HashMap中使用链地址法处理Hash冲突，当桶中某个位置的链表过长时，会响查询效率的情况。

自Java 8开始，HashMap在解决哈希冲突时引入了红黑树的应用，以提高查找操作的效率。当链表长度大于等于阈值（默认为8），同时HashMap容量已达到64时，链表会转换为红黑树，从而减少查找操作的时间复杂度，这个过程称为树化（Treeify）。

树化的2个阈值由HashMap内部的静态常量指定。

红黑树是一种自平衡的二叉搜索树，它具有良好的平衡性能和较快的查找、插入和删除操作的时间复杂度。相比于链表，红黑树在大型哈希桶中可以提供更快的查找速度。

同时，当红黑树中的节点数量减少到一定程度（默认为6）时，HashMap会将红黑树转换回链表。这个过程称为退化（Untreeify）。退化的阈值同样由HashMap内部的静态常量指定：

1.5 LinkedHashMap

1.5.1 LinkedHashMap概述

HashMap虽然提供了高效的添加和查询功能，但是无法保存元素的添加顺序。在一些特定的应用场景中，可能需要保存键值对的添加顺序，此时可以使用LinkedHashMap来实现。

例如：项目既需要提供按用户名快速查询用户信息的功能，也需要提供按用户签到顺序显示用户信息列表的功能。此时需要能够记载元素的添加顺序。

LinkedHashMap是在HashMap的基础上维护了一个Entry的双向链表，以此记录元素之间的先后顺序。

1.5.2 【案例】LinkedHashMap示例

编写代码，测试LinkedHashMap的遍历。代码示意如下：

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class LinkedHashMapDemo {
    public static void main(String[] args) {
        LinkedHashMap<Integer,String> map = new LinkedHashMap<>();
        // 存放元素，以键值对形式
        map.put(5, "Tom");
        map.put(3, "Jerry");
        map.put(9, "Lucy");
        // 通过entrySet方法遍历
        Set<Map.Entry<Integer,String >> entrySet = map.entrySet();
        for(Map.Entry<Integer,String> entry:entrySet){
            System.out.println("key: " + entry.getKey()+" value: " + entry.getValue());
        }
    }
}

2 Set集合

2.1 Set接口

2.1.1 Set接口概述

Set接口继承自Collection接口，所以与Collection接口中的方法基本一致，并没有对Collection接口进行功能上的扩充，只是比Collection接口更加严格。

Set集合的特点是无序且不可重复：

• 无序：不能保证按照添加元素的顺序来存放元素
• 不可重复：集合中不能存储两个用equals方法判断为相等的元素

可以利用Set集合不可重复的特点实现去重操作。

2.1.2 【案例】Set集合示例

编写代码，测试Set集合的使用。代码示意如下：

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class SetDemo1 {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(7, 3, 1, 3, 5, 3, 1);
        // 创建Set集合对象，并将list集合中的元素添加到Set中
        Set<Integer> set = new HashSet<>(list);
        System.out.println(set); // 1, 3, 5, 7
        // 尝试添加重复元素
        boolean flag = set.add(1);
        System.out.println("flag: " + flag); // false
        System.out.println(set); // 1, 3, 5, 7
    }
}

2.1.3 集合运算

Set接口能利用相关方法实现数学上的集合运算，如并、交、差等：

常用的集合运算方法如下所示：

2.1.4 【案例】集合运算示例

编写代码，测试集合运算。代码示意如下：

import java.util.*;
public class SetDemo2 {
    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(1, 2, 3, 4);
        List<Integer> list2 = Arrays.asList(3, 4, 5, 6);
        Set<Integer> set1 = new HashSet<>(list1);
        Set<Integer> set2 = new HashSet<>(list2);
        System.out.println("set1: " + set1);
        System.out.println("set2: " + set2);
        // 求交集
        set1.retainAll(set2);
        System.out.println("set1 和 set2 交集："+set1);
        // 重置set1
        set1= new HashSet<>(list1);
        // 求并集
        set1.addAll(set2);
        System.out.println("set1 和 set2 并集："+set1);
        // 重置set1
        set1= new HashSet<>(list1);
        // 求补集
        set1.removeAll(set2);
        System.out.println("set1 和 set2 补集："+set1);
    }
}

2.2 HashSet

2.2.1 HashSet概述

HashSet是Java中实现了Set接口的集合类，它使用哈希表作为底层数据结构，用于存储唯一的元素。HashSet不保证元素的顺序，且不允许重复元素。

HashSet底层实际上是使用HashMap对象来存储数据，如下图所示。

以下是HashSet的一些特点：

1、HashSet基于哈希表，使用哈希函数将元素映射到对应的存储位置。

2、HashSet存储的元素是无序的，即元素的插入顺序与遍历顺序不一致。

3、HashSet不允许重复元素，每个元素只能出现一次。当尝试将重复元素添加到HashSet时，操作将被忽略。

4、HashSet的元素可以是任何对象，但需要正确实现hashCode()和equals()方法，以确保元素的唯一性。

5、HashSet允许使用null作为元素，但只能有一个null元素。

6、HashSet的插入、删除和查找操作具有常数时间复杂度（平均情况下为O(1)），提供了高效的性能。

2.2.2 【案例】HashSet示例

编写代码，测试HashSet的使用。代码示意如下：

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
public class HashSetDemo1 {
    public static void main(String[] args) {
        Set<Student1> set1 = new HashSet<>();
        set1.add(new Student1("Tom",18));
        set1.add(new Student1("Tom",18));
        System.out.println(set1);
        Set<Student2> set2 = new HashSet<>();
        set2.add(new Student2("Tom",18));
        set2.add(new Student2("Tom",18));
        System.out.println(set2);
    }
}
class Student1{
    String name;
    int age;
    public Student1(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Student1{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
class Student2{
    String name;
    int age;
    public Student2(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student2 student2 = (Student2) o;
        return age == student2.age && Objects.equals(name, student2.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    @Override
    public String toString() {
        return "Student1{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}