文章

HashTable的C++实现

发表于 更新于
作者 sanenchen
11 分钟阅读
HashTable的C++实现

Hash Table介绍

哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 $O(1)$ 时间内获取对应的值 value 。

如下图所示，给定 $n$ 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用下图所示的哈希表来实现。 最好的情况下，哈希表的时间复杂度为O(1)。如果大量的哈希冲突的出现，则会降级为O(n)。

  • 添加元素：仅需将元素添加至数组（链表）的尾部即可，使用 $O(1)$ 时间。
  • 查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 $O(n)$ 时间。
  • 删除元素：需要先查询到元素，再从数组（链表）中删除，使用 $O(n)$ 时间。
 数组链表哈希表
查找元素$O(n)$$O(n)$$O(1)$
添加元素$O(1)$$O(1)$$O(1)$
删除元素$O(n)$$O(n)$$O(1)$

C++标准库中的hashmap用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 初始化操作
unordered_map<int, string> hashMap;
// 添加操作
hashMap[1997] = "123";
hashMap[2008] = "三";
// 访问操作
cout << hashMap[1997] << endl;
// 删除操作
hashMap.erase(1997);

/* 遍历Hash表 */
// 遍历键值对
for (const auto&[fst, snd] : hashMap) {
    cout << fst << ":" << snd << endl;
}
for (const auto& kv : hashMap) {
    cout << kv.first << ":" << kv.second << endl;
}
// 使用迭代器
for (auto iter = hashMap.begin(); iter != hashMap.end(); iter++) {
    cout << iter->first << ":" << iter->second << endl;
}

尝试复刻C++版本的 HashMap

1. 实现 map[0]赋值 map[0] = “Hello” 赋值

实现代码：

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

//
// Created by sanenchen on 25-7-2.
//

#ifndef HASHMAP_H
#define HASHMAP_H
#include <vector>

using namespace std;

// 模板类
template<typename KeyType, typename ValueType>
class HashMap {
    vector<pair<KeyType, ValueType>> data; // 简单用vector模拟存储
public:
    // 返回对应key的value引用，若不存在则插入默认值
    ValueType &operator[](const KeyType &key) {
        // 先查找是否有该key
        for (auto& kv : data) {
            if (kv.first == key) {
                return kv.second;  // 找到返回引用
            }
        }
        // 没找到，插入默认值
        data.emplace_back(key, ValueType{});
        return data.back().second;  // 返回新插入元素的引用
    }
};


#endif //HASHMAP_H

使用

1
2
3

HashMap<int, string> map;
map[0] = "hello";
cout << map[0] << endl;
疑问：ValueType{}是什么，为什么这个可以代指=后面的值

你提出了一个非常棒、非常核心的问题！这恰好是理解 std::unordered_map 或我们自己实现的 HashMap 中 operator[] 工作原理的关键。

我来帮你彻底弄清楚：

一个重要的澄清：ValueType{} 不是 = 右边的值

这是最需要先理解的误区。ValueType{} 并不代表 你在赋值语句 map[key] = value; 中等号右边的那个 value。

它们是两个完全不同的东西，在不同的时间点起作用。

map[key] = value; 的完整执行流程

让我们分解一下 map[0] = "Hello"; 这行代码到底发生了什么：

第一阶段：执行 map[0]

  1. 首先，程序调用 map.operator[](0) 这个函数。

  2. 在 operator[] 函数内部：

    • 代码开始遍历 data 容器，试图寻找 key 等于 0 的元素。
    • 假设这是第一次调用，key 为 0 的元素不存在。
    • 循环结束，没有找到。
    • 程序执行到这一行：data.emplace_back(key, ValueType{});
    • 这里的 ValueType{} 开始起作用了！

第二阶段：ValueType{} 的角色

  • ValueType{} 的意思是：“请为 ValueType 创建一个默认的初始值”。

    • 如果 ValueType 是 std::string，那么 ValueType{} 就是一个空字符串 ""。
    • 如果 ValueType 是 int，那么 ValueType{} 就是 0。
    • 如果 ValueType 是一个自定义类，它会调用这个类的默认构造函数。
  • 所以，data.emplace_back(key, ValueType{}) 这行代码实际上是向 data 这个 vector 中添加了一个新的 pair：{0, ""}。
  • 紧接着，函数返回 data.back().second，也就是刚刚添加的那个空字符串 "" 的引用 (&)。

第三阶段：执行 = 赋值操作

  1. map[0] 这个函数调用已经执行完毕，它返回了一个指向内部空字符串 "" 的引用。
  2. 现在，程序才开始处理 = 右边的部分。
  3. 它将 "Hello" 这个值，通过刚刚拿到的引用，赋给了那个空字符串。
  4. 结果就是，data 容器内部的 pair 从 {0, ""} 被修改为了 {0, "Hello"}。

总结

语法/操作它的作用是什么？发生在哪一步？
map[key]调用 operator[] 函数，负责查找或创建一个存储位置。第一步
ValueType{}如果 key 不存在，用它来创建一个默认值（如 "" 或 0）来占据那个新创建的存储位置。第二步（在 operator[] 内部）
= value将等号右边的真实值，赋给 operator[] 返回的那个存储位置的引用。第三步（在 operator[] 返回之后）

所以，ValueType{} 的作用就像一个“占位符”。它保证了即使 key 原先不存在，operator[] 也总能返回一个有效的、可以被赋值的内存地址（引用），从而让 = 赋值操作能够顺利完成。这正是这个设计如此巧妙和强大的原因。

2. 实现哈希表存取功能

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

template<typename KeyType, typename ValueType>
class HashMap {
    vector<list<ValueType>> data; // 简单用vector模拟存储
private:
    vector<list<pair<KeyType, ValueType>>> buckets;

public:
    HashMap():buckets(100) {}
    // 返回对应key的value引用，若不存在则插入默认值
    ValueType &operator[](const KeyType &key) {
        // 哈希
        hash<KeyType> hasher;
        size_t newIndex = hasher(key) % 100;
        cout << "newIndex: " << newIndex << endl;
        auto& target_bucket = buckets[newIndex];
        // 先查找是否有该key

        for (auto& it : target_bucket) {
            /** 为什么auto加个&？
             *  加上& 就代表这是一个别名，不加的话，就是一个拷贝，不是元素的本身
             *  it将会是一个局部变量
             *  生命周期仅限于本次循环当中
             **/
            if (it.first == key) {
                return it.second;
            }
        }

        // 没找到，插入默认值
        // 构建一个链表
        target_bucket.emplace_back(key, ValueType{});
        return target_bucket.back().second;  // 返回新插入元素的引用
    }
};

3. 实现哈希表删除功能

1
2
3
4
5
6
7
8
9
10
11

void erase(const KeyType &key) {
    hash<KeyType> hasher;
    size_t index = hasher(key) % 100;
    auto& target_bucket = buckets[index];
    for (auto it = target_bucket.begin(); it !=target_bucket.end(); ++it) {
        if (it->first == key) {
            target_bucket.erase(it);
            return;
        }
    }
}

4. 完整代码

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

// hashmap.h
//
// Created by sanenchen on 25-7-2.
//

#ifndef HASHMAP_H
#define HASHMAP_H
#include <iostream>
#include <list>
#include <vector>

using namespace std;

// 模板类
template<typename KeyType, typename ValueType>
class HashMap {
    vector<list<ValueType>> data; // 简单用vector模拟存储
private:
    vector<list<pair<KeyType, ValueType>>> buckets;

public:
    HashMap():buckets(100) {}
    // 返回对应key的value引用，若不存在则插入默认值
    ValueType &operator[](const KeyType &key) {
        // 哈希
        hash<KeyType> hasher;
        size_t newIndex = hasher(key) % 100;
        // cout << "newIndex: " << newIndex << endl;
        auto& target_bucket = buckets[newIndex];
        // 先查找是否有该key

        for (auto& it : target_bucket) {
            /** 为什么auto加个&？
             *  加上& 就代表这是一个别名，不加的话，就是一个拷贝，不是元素的本身
             *  it将会是一个局部变量
             *  生命周期仅限于本次循环当中
             **/
            if (it.first == key) {
                return it.second;
            }
        }

        // 没找到，插入默认值
        // 构建一个链表
        target_bucket.emplace_back(key, ValueType{});
        return target_bucket.back().second;  // 返回新插入元素的引用
    }

    void erase(const KeyType &key) {
        hash<KeyType> hasher;
        size_t index = hasher(key) % 100;
        auto& target_bucket = buckets[index];
        for (auto it = target_bucket.begin(); it !=target_bucket.end(); ++it) {
            if (it->first == key) {
                target_bucket.erase(it);
                return;
            }
        }
    }
};


#endif //HASHMAP_H

使用

1
2
3
4
5
6

HashMap<int, string> map;
map[1] = "HashMap"; // 赋值
cout << map[1] << endl;
map.erase(1); // 删除
map[1] = "Map";
cout << map[1] << endl; //输出

END

数据结构, 算法, C++
C++ HashMap
本文由作者按照 CC BY 4.0 进行授权