哈希表 - 南叶の小窝

南叶酱

摸鱼ing...

统计加载中...

公告

评论不能用！！！其他里的东西暂时还没改，不是我的！！问题反馈和建议请加qq420883290

Learn More

731 字

4 分钟

哈希表

2025-11-03

算法

统计加载中...

哈希表的基本原理#

哈希表就是一个加强版的数组
可以用过key在O(1)的时间复杂度查找到对应的value
key可以是数字或字符串
相比于数组，哈希表在日常的使用更加广泛，比如通讯录就可以理解成一个哈希表
下面用代码实现一个哈希表

1
class MyHashMap {
2

3
private:
4
    vector<void*> table;//表示任意类型的指针
5

6
public:
7
    // 增/改，复杂度 O(1)
8
    void put(auto key, auto value) {
9
        int index = hash(key);
10
        table[index] = value;
11
    }
12

13
    // 查，复杂度 O(1)
14
    auto get(auto key) {
15
        int index = hash(key);
16
        return table[index];
17
    }
18

19
    // 删，复杂度 O(1)
20
    void remove(auto key) {
21
        int index = hash(key);
22
        table[index] = nullptr;
23
    }
24

25
private:
26
    // 哈希函数，把 key 转化成 table 中的合法索引
27
    // 时间复杂度必须是 O(1)，才能保证上述方法的复杂度都是 O(1)
28
    int hash(auto key) {
29
        // ...
30
    }
31
};

注意#

key 是唯一的，value 可以重复

哈希冲突#

如果两个不同的 key 通过哈希函数得到了相同的索引,这种情况就叫做「哈希冲突」。
哈希冲突不可能避免，只能在算法层面妥善处理出现哈希冲突的情况。
哈希冲突是一定会出现的，因为这个 hash 函数相当于是把一个无穷大的空间映射到了一个有限的索引空间，所以必然会有不同的 key 映射到同一个索引上。
有两种常见的解决方法，一种是拉链法，另一种是线性探查法（也经常被叫做开放寻址法）。
- 拉链法简单来说就是让哈希表储存的是一个链表，每有一个新的就加上去
- 而线性探查法的思路是，一个 key 发现算出来的 index 值已经被别的 key 占了，那么它就去 index + 1 的位置看看，如果还是被占了，就继续往后找，直到找到一个空的位置为止。
拉链法和线性探查法虽然能解决哈希冲突的问题，但是它们会导致性能下降。
- 比如拉链法，你算出来 index = hash(key) 这个索引了，结果过去查出来的是个链表，你还得遍历一下这个链表，才能在里面找到你要的 value。这个过程的时间复杂度是 O(n)
- 线性探查法也是类似的，你算出来 index = hash(key) 这个索引了，你去这个索引位置查看，发现存储的不是要找的 key，但由于线性探查法解决哈希冲突的方式，你并不能确定这个 key 真的不存在，你必须顺着这个索引往后找，直到找到一个空的位置或者找到这个 key 为止，这个过程的时间复杂度也是 O(n)
为了避免哈希冲突（也就是哈希表被塞太满），就有了负载因子