概览：

前置知识：无

提醒：讲解虽然用的java语言，但是任何语言都有对等的概念

提醒：后续有专门的章节来详解哈希函数、有序表，这节课就是常规用法展示

哈希表的用法（认为是集合，根据值来做key 或者根据内存地址做key）

HashSet和HashMap原理一样，有无伴随数据的区别

增、删、改、查时间为O(1)，但是大常数

所以当key的范围是固定的、可控的情况下，可以用数组结构替代哈希表结构

注意：

Java中通过自定义hashCode、equals等方法

任何类都可以实现“根据值做key”或者“根据内存地址做key”的需求

但是这里不再展开，因为在算法学习这个范畴内，这些并不重要，还有其他语言的同学也不关心这些

笔试、面试、比赛也都不会用到，课上只说对算法学习重要的内容

有序表的用法（认为是集合，但是有序组织）

TreeSet和TreeMap原理一样，有无伴随数据的区别

增、删、改、查 + 很多和有序相关的操作(floor、ceilling等)，时间为O(log n)

有序表比较相同的东西会去重，如果不想去重就加入更多的比较策略（比较器定制）。堆不会去重。

有序表在java里就是红黑树实现的

AVL树、SB树、替罪羊树、Treap、Splay、跳表等等很多结构都可实现同样功能

后续的课程会涉及，这里不做展开，只讲解简单用法

比较器：定制比较策略。用在排序、堆、有序表等很多需要序的结构中都可使用

定义类、直接Lamda表达式

字典序的概念

哈希表的用法

哈希表（Hash Table）是一种基于键值对（key-value）的高效数据结构，Java 中常见的实现包括 HashMap 和 HashSet。哈希表的核心思想是通过哈希函数将 key 映射到一个索引位置，从而实现快速的增、删、改、查操作。

根据值做 key vs 根据内存地址做 key

根据内存地址做key

默认情况下，Java 中的对象使用其内存地址（引用）作为身份标识。

通过 == 比较的是对象的内存地址是否相同。

如果不重写 hashCode 和 equals，哈希表会根据对象的内存地址判断是否为同一个 key。

根据值做key

通过重写 hashCode 和 equals 方法，可以让哈希表根据对象的值来判断是否为同一个 key。

例如，两个内容相同但内存地址不同的对象可以被认为是同一个 key。

例如：(其实下面的内容也可以作为Java基础考察)

public static void main(String[] args) {
    String s1 = "Hello";
    String s2 = "Hello";
    // 比较内存地址, 但是对于创建s2时，JVM 再次检查字符串常量池，发现 "Hello" 已经存在
    // （由 s1 创建或之前已存在）。此时，JVM 不会创建新对象，而是直接让 s2 指向池中已有的那个 "Hello" 对象。
    System.out.println(s1 == s2);  // 输出True
    // String重写了equals方法，比较的是值，而不是内容地址
    System.out.println(s1.equals(s2));  // 输出True


    // 对比上面的例子
    // 如果使用 new String("Hello") 来创建字符串，情况就不同了：
    String s3 = new String("Hello");
    String s4 = new String("Hello");
    System.out.println(s3 == s4); // false
    System.out.println(s3.equals(s4)); // true
}

HashSet 和 HashMap 的原理

HashSet：

本质上是一个 HashMap，但只存储 key，不存储 value。
内部维护一个 HashMap，value 固定为一个常量对象（通常是 PRESENT，一个 Object 实例）。
用于表示集合，检查元素是否存在。

HashMap：

存储键值对（key-value），key 通过哈希函数映射到数组索引。
内部是一个数组（Node[]），每个数组位置可能是单个节点或链表（JDK 8 后若冲突过多会转为红黑树）。

有无伴随数据的区别

HashSet：无伴随数据，只关心 key 是否存在。
HashMap：有伴随数据，key 关联一个 value，可以通过 key 获取 value。

下面举例：

String s1 = new String("Hello");
String s2 = new String("Hello");

HashSet<String> set = new HashSet<>();
set.add(s1);
System.out.println(set.contains(s1)); // true
System.out.println(set.contains(s2)); // true, 因为值相同，不会重复添加
set.add(s2);
System.out.println(set.size()); // 1

HashMap<String, String> map = new HashMap<>();
map.put(s1, "world");
System.out.println(map.containsKey("Hello")); // true
System.out.println(map.containsKey(s2)); // true
System.out.println(map.get(s2)); // world

注：

HashSet 只关心 key 的存在性，size 不会因为添加相同值的 str2 而增加。
HashMap 允许通过 key 获取对应的 value，且相同值的 key 会覆盖之前的 value。

增、删、改、查时间复杂度为 O(1)，但有大常数

哈希表的操作（put、get、remove、contains）通过哈希函数直接定位到数组索引，理想情况下是 O(1)。

但如果发生哈希冲突（多个 key 映射到同一索引），需要通过链表或红黑树解决冲突，最坏情况可能退化为 O(n) 或 O(log n)。

JDK 8 的 HashMap 在冲突严重时将链表转为红黑树，保持 O(log n) 的复杂度。

哈希函数计算、冲突处理、内存分配等操作引入了较大的常数开销。

相比简单数组的直接索引（几乎无额外开销），哈希表的 O(1) 常数较大。

当 key 范围固定、可控时，可用数组替代哈希表

如果 key 的取值范围是有限且连续的（例如 0 到 99），可以用数组直接索引代替哈希表。

数组的优势：

无哈希计算开销，常数更小。
直接通过下标访问，效率更高。

哈希表的优势：

适用于 key 范围很大或不连续的场景（如字符串、自定义对象）。

例如：

HashMap<Integer, Integer> map2 = new HashMap<>();
map2.put(56, 7285);  // O(1)，但有哈希计算
int[] arr = new int[100];
arr[56] = 7285;  // O(1)，直接索引，无额外开销

比如力扣2404. 出现最频繁的偶数元素的解法如下：下面的int[] count = new int[50001];就是这个意思

class Solution {
    public int mostFrequentEven(int[] nums) {
        int[] count = new int[50001];
        int ans = -1, mx = 0;
        for (int n : nums) {
            if (n % 2 == 0) {
                int freq = ++count[n / 2];
                if (freq > mx || (freq == mx && ans > n)) {
                    mx = freq;
                    ans = n;
                }
            }
        }
        return ans;        
    }
}

自定义 hashCode 和 equals 方法

Java 中任何类都可以通过重写 hashCode 和 equals 方法，决定哈希表是“根据值做 key”还是“根据内存地址做 key”：

默认行为：不重写时，基于内存地址（Object 的 hashCode 返回对象的哈希码，通常与地址相关）。
自定义行为：重写后，可以基于对象的值。

例子：

定义Student类如下：

public class Student {
    Integer age;

    String name;

    public Student(Integer age, String name) {
        this.age = age;
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public String getName() {
        return name;
    }

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

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

测试：

Student stu1 = new Student(17, "张三");
Student stu2 = new Student(17, "张三");
HashSet<Student> setStu = new HashSet<>();
setStu.add(stu1);
System.out.println(setStu.contains(stu1)); // true
System.out.println(setStu.contains(stu2)); // false
System.out.println(setStu.size()); // 1
setStu.add(stu2);
System.out.println(setStu.size()); // 2

现在重写Student类的hashCode和equals方法。

首先补充：

实现高质量的equals方法的诀窍包括　　

使用==操作符检查“参数是否为这个对象的引用”；

使用instanceof操作符检查“参数是否为正确的类型”；

对于类中的关键属性，检查参数传入对象的属性是否与之相匹配；

编写完equals方法后，问自己它是否满足对称性、传递性、一致性；

重写equals时总是要重写hashCode；

不要将equals方法参数中的Object对象替换为其他的类型，在重写时不要忘掉@Override注解。

实现hashCode方法的通用约定 参考阅读博客

在应用程序的执行期间，只要对象的equals方法的比较操作所用到的信息没有被修改，那么对这个同一对象调用多次，hashCode方法必须始终如一地返回同一个整数。在同一个应用程序的多次执行过程中，每次执行所返回的整数可以不一致。

如果两个对象根据equals(Object)方法比较是相等的，那么调用这两个对象中任意一个对象的hashCode方法都必须产生同样的整数结果。反之，如果两个对象hashCode方法返回整数结果一样，则不代表两个对象相等，因为equals方法可以被重载。

如果两个对象根据equals(Object)方法比较是不相等的，那么调用这两个对象中任意一个对象的hashCode方法，则不一定要产生不同的整数结果。但，如果能让不同的对象产生不同的整数结果，则有可能提高散列表的性能。

hashCode散列码计算（来自：Effective Java）

把某个非零的常数值，比如17，保存在一个名为result的int类型的变量中。

对于对象中每个关键域f(指equals方法中涉及的每个域)，完成以下步骤：

为该域计算int类型的散列码c： > 1. 如果该域是boolean类型，则计算(f?1:0)。

如果该域是byte，char，short或者int类型，则计算(int)f。

如果该域是long类型，则计算(int)(f^(f>>>32))。

如果该域是float类型，则计算Float.floatToIntBits(f)。

如果该域是double类型，则计算Double.doubleToLongBits(f)，然后按照步骤2.1.3，为得到的long类型值计算散列值。

如果该域是一个对象引用，并且该类的equals方法通过递归地调用equals的方式来比较这个域，则同样为这个域递归地调用hashCode。如果需要更复杂的比较，则为这个域计算一个范式(canonical representation)，然后针对这个范式调用hashCode。如果这个域的值为null，则返回0(其他常数也行)。

如果该域是一个数组，则要把每一个元素当做单独的域来处理。也就是说，递归地应用上述规则，对每个重要的元素计算一个散列码，然后根据步骤2.2中的做法把这些散列值组合起来。如果数组域中的每个元素都很重要，可以利用发行版本1.5中增加的其中一个Arrays.hashCode方法。

按照下面的公式，把步骤2.1中计算得到的散列码c合并到result中：result = 31 * result + c; //此处31是个奇素数，并且有个很好的特性，即用移位和减法来代替乘法，可以得到更好的性能：31*i == (i<<5) - i，现代JVM能自动完成此优化。

返回result

检验并测试该hashCode实现是否符合通用约定。

public class Student {
    Integer age;

    String name;

    public Student(Integer age, String name) {
        this.age = age;
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public String getName() {
        return name;
    }

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

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

    @Override
    public boolean equals(Object obj) {
        if (this == obj) { // 先判断是不是自己,提高运行效率
            return true;
        }
        if (obj instanceof Student) { // 再判断是不是Person类,提高代码的健壮性
            Student s = (Student) obj;// 向下转型,父类无法调用子类的成员和方法
            // 最后判断类的所有属性是否相等，其中String类型和Object类型可以用相应的equals()来判断
            return (this.getName().equals(s.getName()) && this.getAge() == s.getAge());
        }
        return false;
    }

    @Override
    public int hashCode() {
        int result = 17;// 准备一个质数
        result = result * 17 + age;
        result = result * 17 + name.hashCode();
        return result;
    }
}

运行测试：

Student stu1 = new Student(17, "张三");
Student stu2 = new Student(17, "张三");
HashSet<Student> setStu = new HashSet<>();
setStu.add(stu1);
System.out.println(setStu.contains(stu1)); // true
System.out.println(setStu.contains(stu2)); // true
System.out.println(setStu.size()); // 1
setStu.add(stu2);
System.out.println(setStu.size()); // 1

有序表的用法

有序表的概念

有序表可以看作是一个集合，但其元素是有序组织的。

它通过某种比较策略（默认或自定义）保持元素的顺序，支持快速的增删改查以及与顺序相关的操作。

Java中，有序表的数据结构是TreeSet 和 TreeMap

TreeSet 和 TreeMap的共同点：底层原理相同，都是基于红黑树实现的有序结构，时间复杂度为 O(log n)。

TreeSet 和 TreeMap的区别：

TreeSet：只有键（key），没有伴随数据，类似于一个有序的集合，会自动去重。
TreeMap：键值对（key-value）结构，键有序，值是伴随数据。

例如：

TreeSet<String> s = new TreeSet<>();
s.add("hello");
TreeMap<String, Integer> m = new TreeMap<>();
m.put("a", 10);

基本操作及时间复杂度

增（add/put）、删（remove）、改（put 更新值）、查（containsKey/get）：时间复杂度均为 O(log n)。(因为底层是红黑树实现的有序结构)

与有序相关的操作：

floorKey(x)：返回 ≤ x 的最大键。
ceilingKey(x)：返回 ≥ x 的最小键。
firstKey()：返回最小键。
lastKey()：返回最大键。

例如：

TreeSet<String> set1 = new TreeSet<>();
set1.add("a");
set1.add("a");
set1.add("b");
System.out.println(set1.size());// 2   去重
System.out.println(set1.contains("a"));// true
set1.add("e");
set1.add("z");
System.out.println(set1.last());// z
System.out.println(set1.first());// a

TreeMap<Integer, String> map1 = new TreeMap<>();
map1.put(1, "jello");
map1.put(2, "you");
map1.put(3, "90");
map1.put(5, "tee");
map1.put(7, "foot");
map1.put(9, "head");
System.out.println(map1.floorKey(5));// 5  返回<=5
System.out.println(map1.ceilingKey(5));// 5  返回>=8
System.out.println(map1.firstKey());// 1
System.out.println(map1.lastKey());// 9

去重特性

有序表（TreeSet/TreeMap）：默认会对相同元素去重（基于比较策略判断相等）。

如果不想去重，可以通过定制比较器，加入更多比较条件（如内存地址或唯一标识）。

堆（PriorityQueue）：不会去重，允许重复元素。

TreeSet<String> treeset = new TreeSet<>();
treeset.add("p");
treeset.add("p");
treeset.add("q");
System.out.println(treeset.size());// 2

PriorityQueue<String> pQueue = new PriorityQueue<>();
pQueue.add("p");
pQueue.add("p");
pQueue.add("q");
System.out.println(pQueue.size());// 3

底层实现

Java 中的实现：有序表（如 TreeSet 和 TreeMap）在 Java 中由红黑树实现。

其他实现方式：

AVL 树、SB 树（Size-Balanced Tree）、替罪羊树、Treap、Splay 树、跳表等。

比较器（Comparator）

定制比较策略，用于排序、堆、有序表等需要序的结构。

定义方式：

定义类：实现 Comparator 接口。
Lambda 表达式：直接 inline 定义。

比较规则：

返回负数：第一个元素优先级更高。
返回正数：第二个元素优先级更高。
返回 0：认为相等（有序表会去重）。

例如：

有EmployEE类：

public class EmployEE {
    int employeeId;
    int departmentId;

    public EmployEE(int employeeId, int departmentId) {
        this.employeeId = employeeId;
        this.departmentId = departmentId;
    }

    public int getEmployeeId() {
        return employeeId;
    }

    public void setEmployeeId(int employeeId) {
        this.employeeId = employeeId;
    }

    public int getDepartmentId() {
        return departmentId;
    }

    public void setDepartmentId(int departmentId) {
        this.departmentId = departmentId;
    }
}

方法1:定义一个EmployeeComparator类，实现接口Comparator，定义比较策略，比较员工部门ID，如果一样，employeeId越小的优先级越高，否则部门ID越小的优先级越高。

static class EmployeeComparator implements Comparator<EmployEE> {

    @Override
    public int compare(EmployEE o1, EmployEE o2) { // 返回负数，o1优先级更高
        return o1.getDepartmentId() - o2.getDepartmentId() != 0
                ? o1.getDepartmentId() - o2.getDepartmentId()
                : o1.getEmployeeId() - o2.getEmployeeId();
    }
}

测试代码：

EmployEE e1 = new EmployEE(1, 2);
EmployEE e2 = new EmployEE(1, 3);
EmployEE.EmployeeComparator comparator = new EmployEE.EmployeeComparator();
System.out.println(comparator.compare(e1, e2));// -1

e1 = new EmployEE(10, 2);
e2 = new EmployEE(6, 2);
System.out.println(comparator.compare(e1, e2));// 4

方法2:也可以写Lambda表达式：

EmployEE e1 = new EmployEE(8, 2);  // dept=2, emp=8
EmployEE e2 = new EmployEE(6, 3);  // dept=3, emp=6
EmployEE e3 = new EmployEE(5, 2);  // dept=2, emp=5

Comparator<EmployEE> comparator = Comparator.comparingInt(EmployEE::getDepartmentId)
        .thenComparingInt(EmployEE::getEmployeeId);

System.out.println(comparator.compare(e1, e2)); // dept: 2 vs 3
System.out.println(comparator.compare(e1, e3)); // dept: 2 vs 2, emp: 8 vs 5
System.out.println(comparator.compare(e3, e1)); // dept: 2 vs 2, emp: 5 vs 8

字典序的概念

比较规则

逐字符比较：
- 从两个序列的第一个元素开始比较。
- 如果当前元素不同，则较小的元素所在的序列在字典序中靠前。
- 如果当前元素相同，继续比较下一个元素。
长度规则：
- 如果一个序列是另一个序列的前缀（即较短的序列先结束），则较短的序列在字典序中靠前。
空序列：
- 空序列（长度为 0）在字典序中通常小于任何非空序列。

例如：

“apple” vs “banana”：

‘a’ vs ‘b’：’a’ < ‘b’，所以 “apple” < “banana”。

“cat” vs “cattle”：

‘c’ vs ‘c’：相等，继续。
‘a’ vs ‘a’：相等，继续。
‘t’ vs ‘t’：相等，继续。
“cat” 结束，”cattle” 还有字符，所以 “cat” < “cattle”。

“abc” vs “ab”：

‘a’ vs ‘a’：相等。
‘b’ vs ‘b’：相等。
“ab” 结束，”abc” 还有 ‘c’，所以 “ab” < “abc”。

026 哈希表，有序表和比较器的用法

哈希表(集)：O(1)操作依赖hashCode/equals；有序表(集)：O(log n)操作依赖比较器维护顺序。介绍根据值/地址作键、数组替代哈希表场景、比较器定制和字典序概念。

哈希表的用法

根据值做 key vs 根据内存地址做 key

HashSet 和 HashMap 的原理

增、删、改、查时间复杂度为 O(1)，但有大常数

当 key 范围固定、可控时，可用数组替代哈希表

自定义 hashCode 和 equals 方法

实现高质量的equals方法的诀窍包括

有序表的用法

有序表的概念

基本操作及时间复杂度

去重特性

底层实现

比较器（Comparator）

字典序的概念

CATALOG

FEATURED TAGS

FRIENDS