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

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

Posted by Hilda on April 6, 2025

概览:

前置知识:无

提醒:讲解虽然用的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基础考察)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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。

下面举例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 范围很大或不连续的场景(如字符串、自定义对象)。

例如:

1
2
3
4
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];就是这个意思

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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类如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

测试:

1
2
3
4
5
6
7
8
9
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方法的通用约定 参考阅读博客

  1. 在应用程序的执行期间,只要对象的equals方法的比较操作所用到的信息没有被修改,那么对这个同一对象调用多次,hashCode方法必须始终如一地返回同一个整数。在同一个应用程序的多次执行过程中,每次执行所返回的整数可以不一致。
  2. 如果两个对象根据equals(Object)方法比较是相等的,那么调用这两个对象中任意一个对象的hashCode方法都必须产生同样的整数结果。反之,如果两个对象hashCode方法返回整数结果一样,则不代表两个对象相等,因为equals方法可以被重载。
  3. 如果两个对象根据equals(Object)方法比较是不相等的,那么调用这两个对象中任意一个对象的hashCode方法,则不一定要产生不同的整数结果。但,如果能让不同的对象产生不同的整数结果,则有可能提高散列表的性能。

hashCode散列码计算(来自:Effective Java)

  1. 把某个非零的常数值,比如17,保存在一个名为resultint类型的变量中。
  2. 对于对象中每个关键域f(equals方法中涉及的每个域),完成以下步骤:
    1. 为该域计算int类型的散列码c: > 1. 如果该域是boolean类型,则计算(f?1:0)。
    1. 如果该域是bytecharshort或者int类型,则计算(int)f
    2. 如果该域是long类型,则计算(int)(f^(f>>>32))
    3. 如果该域是float类型,则计算Float.floatToIntBits(f)
    4. 如果该域是double类型,则计算Double.doubleToLongBits(f),然后按照步骤2.1.3,为得到的long类型值计算散列值。
    5. 如果该域是一个对象引用,并且该类的equals方法通过递归地调用equals的方式来比较这个域,则同样为这个域递归地调用hashCode。如果需要更复杂的比较,则为这个域计算一个范式(canonical representation),然后针对这个范式调用hashCode。如果这个域的值为null,则返回0(其他常数也行)。
    6. 如果该域是一个数组,则要把每一个元素当做单独的域来处理。也就是说,递归地应用上述规则,对每个重要的元素计算一个散列码,然后根据步骤2.2中的做法把这些散列值组合起来。如果数组域中的每个元素都很重要,可以利用发行版本1.5中增加的其中一个Arrays.hashCode方法。
    7. 按照下面的公式,把步骤2.1中计算得到的散列码c合并到result中:result = 31 * result + c; //此处31是个奇素数,并且有个很好的特性,即用移位和减法来代替乘法,可以得到更好的性能:31*i == (i<<5) - i, 现代JVM能自动完成此优化。
  3. 返回result
  4. 检验并测试该hashCode实现是否符合通用约定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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;
    }
}

运行测试:

1
2
3
4
5
6
7
8
9
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)结构,键有序,值是伴随数据。

例如:

1
2
3
4
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():返回最大键。

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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):不会去重,允许重复元素。

1
2
3
4
5
6
7
8
9
10
11
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类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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越小的优先级越高。

1
2
3
4
5
6
7
8
9
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();
    }
}

测试代码:

1
2
3
4
5
6
7
8
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表达式:

1
2
3
4
5
6
7
8
9
10
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

字典序的概念

比较规则

  1. 逐字符比较:
    • 从两个序列的第一个元素开始比较。
    • 如果当前元素不同,则较小的元素所在的序列在字典序中靠前。
    • 如果当前元素相同,继续比较下一个元素。
  2. 长度规则:
    • 如果一个序列是另一个序列的前缀(即较短的序列先结束),则较短的序列在字典序中靠前。
  3. 空序列:
    • 空序列(长度为 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”。