五天手撕数据结构之 —— 哈希表
哈希表（Hash Table），也叫散列表，是一种极其高效的数据结构。
哈希表能在平均情况下，以接近 O(1) 的时间复杂度进行数据的插入、删除和查找，这比数组的遍历（O(n)）和二叉搜索树的搜索（O(log n)）要快得多。
哈希表就像是一个智能的储物柜系统：
- 传统储物柜：你需要记住每个物品放在哪个柜子里（线性查找）
- 智能储物柜：你告诉管理员物品名称，他直接告诉你柜子编号（哈希查找）
核心思想：
通过哈希函数将**键（Key）**转换为**数组索引**，实现快速访问。
用空间换时间，用计算换顺序。
基本概念
什么是哈希表？
哈希表是一种通过键（Key）来直接访问值（Value）的数据结构，它利用一个叫做哈希函数的公式，把任意大小的键（比如一个字符串、一个数字或一个对象）转换成一个固定大小的数字，这个数字被称为哈希值或哈希码。然后，用这个哈希值作为数组的索引，将值存储在这个索引对应的数组位置上。
这个过程就像给每个键分配一个唯一的座位号（哈希值），然后告诉它：你的数据就放在这个号码的座位上。当你想找这个数据时，只需要用同样的规则再算一次座位号，就能直接走过去拿到它，而不用一个个座位去问。
核心组件
一个哈希表主要由以下三个核心部分组成：
- 键（Key）： 你要存储和查找数据时使用的标识符。比如，在电话簿中，人名就是键。
- 值（Value）： 与键相关联的实际数据。在电话簿中，电话号码就是值。
- 哈希函数（Hash Function）： 将键映射到数组索引的数学函数。它是哈希表的心脏。
工作原理
上图清晰地展示了哈希表的工作流程：无论是插入还是查找，都始于一个键，通过哈希函数计算出索引，然后直接对数组的该位置进行操作，从而实现了高速访问。
哈希冲突
当两个或多个不同的键（Key），经过同一个哈希函数计算后，得到了相同的哈希值（即映射到哈希表的同一个位置）。
如果不处理冲突：
- 后插入的键值对会覆盖先插入的数据；
- 导致数据丢失或查找错误；
- 哈希表就失去了正确性。
解决方案：
链地址法（Chaining）
- 每个槽位存一个链表（或动态数组）；
- 所有哈希到同一位置的键值对，都放进这个链表；
- 查找时遍历链表即可。
📌 优点：实现简单，负载因子可 >1
📌 缺点：链表过长时性能退化（O (n)）
开放寻址法（Open Addressing）
- 所有元素都存在数组中；
- 冲突时，按规则探测下一个空位（如线性探测：+1, +2, +3…）；
- 查找时沿相同路径探测，直到找到或遇到空槽。
📌 优点：缓存友好，内存紧凑
📌 缺点：删除复杂，负载因子必须 <1
代码演示
java 实现开放寻址法哈希表
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| import java.util.Objects;
public class LinearProbingHashTable<K, V> {
private static class Entry<K, V> {
K key;
V value;
boolean deleted;
Entry(K key, V value) {
this.key = key;
this.value = value;
this.deleted = false;
}
}
private Entry<K, V>[] table;
private int size;
private int tombstones;
private static final double LOAD_FACTOR_THRESHOLD = 0.75;
@SuppressWarnings("unchecked")
public LinearProbingHashTable(int initialCapacity) {
this.table = new Entry[initialCapacity];
this.size = 0;
this.tombstones = 0;
}
public LinearProbingHashTable() {
this(16);
}
private int hash(K key) {
return (key.hashCode() & 0x7fffffff) % table.length;
}
private int findIndex(K key) {
int index = hash(key);
int probe = 0;
while (probe < table.length) {
Entry<K, V> entry = table[index];
if (entry == null) {
return -1;
}
if (!entry.deleted && Objects.equals(entry.key, key)) {
return index;
}
index = (index + 1) % table.length;
probe++;
}
return -1;
}
public void put(K key, V value) {
if ((size + tombstones) >= table.length * LOAD_FACTOR_THRESHOLD) {
resize();
}
int index = hash(key);
int probe = 0;
while (probe < table.length) {
Entry<K, V> entry = table[index];
if (entry == null || entry.deleted) {
table[index] = new Entry<>(key, value);
if (entry == null) {
size++;
} else {
size++;
tombstones--;
}
return;
}
if (Objects.equals(entry.key, key)) {
entry.value = value;
return;
}
index = (index + 1) % table.length;
probe++;
}
throw new IllegalStateException("Hash table is full");
}
public V get(K key) {
int index = findIndex(key);
if (index != -1) {
return table[index].value;
}
return null;
}
public V remove(K key) {
int index = findIndex(key);
if (index != -1) {
V oldValue = table[index].value;
table[index].deleted = true;
size--;
tombstones++;
return oldValue;
}
return null;
}
@SuppressWarnings("unchecked")
private void resize() {
Entry<K, V>[] oldTable = table;
int newCapacity = table.length * 2;
table = new Entry[newCapacity];
size = 0;
tombstones = 0;
for (Entry<K, V> entry : oldTable) {
if (entry != null && !entry.deleted) {
put(entry.key, entry.value);
}
}
}
public double loadFactor() {
return (double) (size + tombstones) / table.length;
}
public int size() {
return size;
}
}
|
