CS61B
课程笔记（Lab 9：Tree Map 与 Hash Map | CS 61B Spring 2018)
1.
BSTMap：基于二叉搜索树的 Map 实现
原理介绍：
BSTMap 使用二叉搜索树（Binary Search Tree,
BST）作为其核心数据结构。二叉搜索树是一种二叉树，它的每个节点都包含一个键值对，并且具有以下性质：
- 左子树的所有键值小于当前节点的键值。
- 右子树的所有键值大于当前节点的键值。
这种结构使得在二叉搜索树中的查找、插入和删除操作的时间复杂度在平均情况下为
O(n)，最坏情况下（当树退化为链表时）为 \(O(n)\)。
BSTMap 的操作流程：
- 查找 (
get)：
- 从根节点开始，依次与当前节点的键比较。
- 如果目标键比当前节点的键小，则递归在左子树查找。
- 如果目标键比当前节点的键大，则递归在右子树查找。
- 如果找到了目标键，则返回该节点对应的值。
- 插入 (
put)：
- 和查找操作类似，首先找到合适的插入位置。
- 将新的键值对插入到合适的子树中。
- 如果树中已经存在该键，则更新其值。
- 计算大小 (
size)：
代码实现（包含详细中文注释）：
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| public class BSTMap<K extends Comparable<K>, V> implements Map61B<K, V> {
private class Node {
private K key;
private V value;
private Node left, right;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
private Node root;
private int size;
public BSTMap() {
this.root = null;
this.size = 0;
}
@Override
public void clear() {
root = null;
size = 0;
}
@Override
public V get(K key) {
return getHelper(root, key);
}
private V getHelper(Node node, K key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
return getHelper(node.left, key);
} else if (cmp > 0) {
return getHelper(node.right, key);
} else {
return node.value;
}
}
@Override
public void put(K key, V value) {
root = putHelper(root, key, value);
}
private Node putHelper(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = putHelper(node.left, key, value);
} else if (cmp > 0) {
node.right = putHelper(node.right, key, value);
} else {
node.value = value;
}
return node;
}
@Override
public int size() {
return size;
}
@Override
public Set<K> keySet() {
throw new UnsupportedOperationException();
}
@Override
public V remove(K key) {
throw new UnsupportedOperationException();
}
@Override
public Iterator<K> iterator() {
throw new UnsupportedOperationException();
}
}
|
2.
MyHashMap：基于哈希表的 Map 实现
原理介绍：
MyHashMap 是基于哈希表（Hash
Table）的映射实现。哈希表通过哈希函数将键映射到不同的“桶”（bucket）中，每个桶存储一组键值对。这样通过键的哈希值，可以快速定位到存储的桶，极大提高了查找速度。
哈希表的时间复杂度通常为
O(1)，因为可以通过哈希函数直接定位到目标桶。
哈希表的操作流程：
- 哈希函数 (
hash)：
- 对键调用
hashCode()
方法，获取其哈希值，并通过取模操作将其映射到桶的索引。
- 查找 (
get)：
- 通过哈希函数找到键对应的桶，从桶中查找键值对。
- 如果找到目标键，返回其对应的值。
- 插入 (
put)：
- 通过哈希函数找到键对应的桶，插入键值对。
- 如果负载因子（元素个数/桶的数量）超过一定阈值，则需要扩容，将桶数量加倍。
- 扩容：
- 当负载因子超过设定的最大值（例如
0.75）时，进行扩容，将所有键值对重新分配到更大的桶数组中。
代码实现（包含详细中文注释）：
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| public class MyHashMap<K, V> implements Map61B<K, V> {
private static final int DEFAULT_INITIAL_SIZE = 16;
private static final double MAX_LF = 0.75;
private ArrayMap<K, V>[] buckets;
private int size;
private int capacity;
public MyHashMap() {
this(DEFAULT_INITIAL_SIZE);
}
public MyHashMap(int initialSize) {
this.capacity = initialSize;
this.size = 0;
this.buckets = createTable(capacity);
}
@Override
public void clear() {
buckets = createTable(capacity);
size = 0;
}
private int hash(K key) {
if (key == null) {
return 0;
}
return Math.floorMod(key.hashCode(), capacity);
}
@Override
public V get(K key) {
int bucketIndex = hash(key);
return buckets[bucketIndex].get(key);
}
@Override
public void put(K key, V value) {
if ((double) size / capacity > MAX_LF) {
resize(2 * capacity);
}
int bucketIndex = hash(key);
if (!buckets[bucketIndex].containsKey(key)) {
size++;
}
buckets[bucketIndex].put(key, value);
}
@Override
public int size() {
return size;
}
private void resize(int newCapacity) {
ArrayMap<K, V>[] newBuckets = createTable(newCapacity);
for (ArrayMap<K, V> bucket : buckets) {
for (K key : bucket.keySet()) {
int newIndex = Math.floorMod(key.hashCode(), newCapacity);
newBuckets[newIndex].put(key, bucket.get(key));
}
}
this.capacity = newCapacity;
容量
this.buckets = newBuckets;
}
@Override
public Set<K> keySet() {
throw new UnsupportedOperationException();
}
@Override
public V remove(K key) {
throw new UnsupportedOperationException();
}
@Override
public Iterator<K> iterator() {
throw new UnsupportedOperationException();
}
}
|
3. BSTMap 与 MyHashMap
的核心区别
| 特性 |
BSTMap（基于二叉搜索树） |
MyHashMap（基于哈希表） |
| 数据结构 |
二叉搜索树 |
哈希表 |
| 查找/插入时间复杂度 |
平均 \(O(\log n)\)，最坏 \(O(n)\) |
平均 \(O(1)\)，最坏 \(O(n)\) |
| 键的有序性 |
保持键的有序性（中序遍历能得到有序的键序列） |
键的顺序是无序的 |
| 适用场景 |
适合需要频繁进行范围查询的场景 |
适合大数据量且需要快速查找、插入的场景 |
| 扩容机制 |
无需扩容，但最坏情况可能退化为链表结构 |
当负载因子过高时，需要进行扩容 |
