概览:
前置知识:无
提醒:讲解虽然用的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
方法的通用约定 参考阅读博客
- 在应用程序的执行期间,只要对象的
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
实现是否符合通用约定。
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
字典序的概念
比较规则
- 逐字符比较:
- 从两个序列的第一个元素开始比较。
- 如果当前元素不同,则较小的元素所在的序列在字典序中靠前。
- 如果当前元素相同,继续比较下一个元素。
- 长度规则:
- 如果一个序列是另一个序列的前缀(即较短的序列先结束),则较短的序列在字典序中靠前。
- 空序列:
- 空序列(长度为 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”。