hash

哈希表（Hash Table）笔记

1. 前提条件

之前学过的查找：顺序查找

数组： array
[8, 3, 5, 10, 7]

找：
10

需要：
8

3

5

10

比较四次。

时间复杂度：O(n)

然而二分查找

要求：必须有序

例如：[1,3,5,7,9]

查找：7

时间复杂度：O(log n)

有没有更快？

希望：一下找到

于是有：哈希表

2. 核心概念

什么是哈希

例如：

学号

↓

宿舍号

或者：

QQ号

↓

用户信息

例如：

20260001

↓

张三

我们希望：

输入key

直接找到value

于是：

key

↓

哈希函数

↓

数组下标

3. 哈希函数

例如：

key = 123

哈希函数：

hash = key % 10;

得到：

3

存放：

table[3]

查找：

123

↓

123 % 10

↓

3

↓

直接访问table[3]

时间复杂度：O(1)理想情况。

4. 哈希表结构

本质：数组

例如：int table[10];

存：11

位置：

11 % 10 = 1

放：

table[1] = 11;

5. 哈希冲突

最重要概念。

例如：

11 % 10 = 1

21 % 10 = 1

发现：两个元素

对应同一个位置

这就叫：哈希冲突(Hash Collision)

6. 冲突解决方法

方法1：拉链法

又叫：链地址法

例如：

11

21

31

都映射到：1

存：table[1]

↓

11 -> 21 -> 31

即：

数组 + 链表

图：

0

1 -> 11 -> 21 -> 31

2

3

优点：
简单

常用

LeetCode里的哈希表基本都这么实现。

方法2：开放定址法

发生冲突：

往后找空位

例如：

11

↓

1

放：table[1]

再插入：

21

↓

1

发现：

table[1]

被占了。

往后：

table[2]

空。

放进去。

最终：

1:11

2:21

7. 哈希表ADT

结构体
链地址法：

struct Node
{
int key;

struct Node* next;

};

struct HashTable
{
struct Node* table[100];
};

哈希函数
int hash(int key)
{
return key % 100;
}

插入
void insert(
struct HashTable* h,
int key)
{
int index = hash(key);

struct Node* node =
    malloc(sizeof(struct Node));

node->key = key;

node->next =
    h->table[index];

h->table[index] = node;

}

理解：头插法。

例如：

11

21

31

结果：

31 -> 21 -> 11

8. 查找
   bool search(
   struct HashTable* h,
   int key)
   {
   int index = hash(key);

   struct Node* cur =
   h->table[index];

   while(cur != NULL)
   {
   if(cur->key == key)
   {
   return true;
   }

    cur = cur->next;
   

   }

   return false;
   }

9. 删除

思路和链表一样。

找到前驱

修改next

10. 哈希表复杂度

理想情况：

插入 O(1)

查找 O(1)

删除 O(1)

极端情况：全部冲突

变成：链表

时间复杂度：O(n)

11. LeetCode中的哈希思想

最经典：两数之和

1题

暴力：

for
for

时间：

O(n²)

哈希：边遍历,边存哈希表

例如：

nums=[2,7,11,15]

target=9

遍历：2
需要：7

查哈希：没有

存：2

遍历：7

需要：2

发现：哈希表里有

直接返回。

复杂度：O(n)

12. 易错点
    哈希表不是排序

例如：

8

2

10

哈希表里可能：

2

10

8

没有顺序。

哈希冲突一定存在

不可能完全避免。

只能：减少

哈希函数要简单

常见：key % size
不要写太复杂。

13. 题型总结
    类型1

查找是否存在

例如：

1 两数之和

217 存在重复元素

关键词：

是否存在

是否出现过

想到：

哈希表

类型2

统计次数

例如：

169 多数元素

347 前K个高频元素

关键词：

频率

次数

想到：哈希表

类型3

字符统计

例如：

242 有效字母异位词

3 无重复字符最长子串

关键词：

字符出现次数

想到：哈希表

哈希表(Hash Table)

核心思想：空间换时间

---

key

↓

哈希函数

↓

数组下标

---

理想复杂度：

插入 O(1)

查找 O(1)

删除 O(1)

---

冲突：

多个key映射同一位置

---

解决：

1. 拉链法（链地址法）

数组+链表

2. 开放定址法

往后找空位

---

常见哈希函数：

key % size

---

LeetCode关键词：

是否存在

是否出现过

统计次数

频率

字符计数

↓

字符串哈希（ASCII 256数组）
↓
LeetCode 1 两数之和
LeetCode 217 存在重复元素
LeetCode 242 有效字母异位词
LeetCode 49 字母异位词分组