哈希表

by.Qin3Yu

ps.本文的哈希表特指unordered_map实现类型

文中所有代码默认已使用std命名空间且已导入部分头文件：

#include <iostream>
#include <unordered_map>
using namespace std;

---

概念速览

什么是键值对？

• 所谓 键值对，顾名思义就是 键 和 值 组成的 对子，通过键，我们可以快速的找到值。比如在学校中，学号 和 学生 就是一个键值对；在词典中，狗 和 dog 就是一个键值对。键和值可以是不同的数据类型，如 商品名称（string型） 和 商品价格（float型） 也可以是一个键值对。

• 特别注意：值不一定是唯一的，但是键一定是唯一的。 打个比方：学号一定是唯一的，但是学生名字可能有重名的。

什么是哈希表？

• 哈希表简单来说就是储存键值对的容器。
• 哈希表的定义是一种通过哈希函数将数据映射到数组中的数据结构。它的目的是实现快速的插入、删除和查找操作。哈希表的基本思想是将键通过哈希函数转换为一个确定的索引，然后将对应的值存储在该索引位置上。

• 当需要查找或删除一个键对应的值时，再次利用哈希函数计算得到索引，从相应位置上获取或删除对应的值，以达到快速查找的目的。

优势：
1.高效性： 哈希表能够在平均情况下实现O(1)时间复杂度的插入和查找操作。
2.灵活性： 哈希表可以存储不同类型的数据。
3.调节性： 哈希表支持动态扩展，即使在插入大量元素时，也能够自动调整内部的存储空间大小。

缺点：
1.内存消耗： 哈希表在存储数据时需要额外的内存来存储散列桶、指针等信息。
2.冲突消耗： 由于散列函数可能将不同的键映射到相同的散列桶位置，一个不好的散列函数可能导致冲突过多，从而降低效率。

---

哈希表操作

声明一个哈希表（ unordered_map ）

• 我们可以直接在函数中使用 unordered_map<T1, T2> name 声明一个哈希表，其中T1表示键（key）的类型，T2表示值（value）的类型，name表示哈希表的名字。在本文中，我们使用名为hs的字符串键值对哈希表来举例：

unordered_map<string, string> hs;  //声明一个名为hs的哈希表，他的键和值都是字符串类型

插入键值对（ insert ）

• 现在我们已经有了一个空的字符串哈希表，，我们可以通过 hs.insert({ key,value }) 方法来将键值对插入哈希表。在本文中，我们以制作词典为例，我们使用的键值对是单词 - 翻译，因此，我们可以向我们的词典哈希表中插入一些单词和翻译的键值对：

//注意，“键值对”顾名思义，前者为键，后者为值
hs.insert({ "蝾螈", "newt" });
hs.insert({ "章鱼", "octopus"});
hs.insert({ "水豚", "capybara"});
hs.insert({ "牛蛙", "bullfrog" });
hs.insert({ "臭鼬", "skunk" });

• 另外，我们也可以通过控制台输入来添加键值对，只需向 hs.insert({ key,value }) 传入相应参数即可：

cout << "请输入中文:";
string chinese; cin >> chinese;  //输入中文为键
cout << "请输入英文:";
string english; cin >> english;  //输入翻译为值
hs.insert({ chinese, english });  //插入 { 中文,翻译 } 键值对

• ps.请注意，哈希表中的元素是没有先后顺序的。

删除键值对（ erase ）

• 我们已经向哈希表中插入了一些数据，但假如其中的一些键值对输入错误，或者我们不再需要某些键值对，我们则需要做出删除键值对的操作。我们可以通过 hs.erase(key) 方法删除键值对。
• 注意：此方法只可通过键来删除键值对。若想通过值删除键值对，可以采用后文说到的遍历方法，先找出键，然后再通过键删除键值对。

hs.insert({ "狗", "dag" });  //单词dog拼写错误，需要删除键值对
hs.erase("狗");  //删除 { 狗 , dog } 键值对
hs.insert({ "臭鼬", "skunk" });  //我不喜欢臭鼬，所以删除 { 臭鼬 , skunk } 键值对

查询值

• 要查询哈希表中的值，我们只需要使用类似索引的方法 hs[key] 即可，此部分很简单，我们直接举例说明：

cout << hs["水豚"];  //哈希表中对应的键值对为 { 水豚 , kapybara } 
//执行后控制台将会输出：kapybara

查询键

• 在哈希表中，没有直接通过输入值查询键的方法，所以我们只能通过遍历的方法，将哈希表中的所有键值对逐个读取一遍，直到找到对应的值后才能得到对应的键。

//此处我要通过值val找出对应的键
//代码将在后文详细解释
for (const auto& p : hs) {
    if (p.second == val) {
        cout << "对应的翻译是：" << p.first << endl;
    }
}

• 在上面的代码中，const auto 表示自动根据后面变量 p 的值推断相应的数据类型；符号 & 表示应用类型，引用类型可以避免在循环中对容器元素进行拷贝，提高性能并节省内存。
• for (const auto& p : hs) 表示遍历循环，具体来说变量 p 将会依次等于 hs 中的每一个键值对。在循环内部，因为 p 等于键值对，而键值对包含键和值两个变量，所以 p.first 和 p.second 就分别表示 p 包含的两个变量，即键和值：

• 因此，当 p.second = val 的时候，p.first就等于对应的key，从而得到键。

查询键是否存在（ count ）

• 我们在进行键的增删查操作时，难免会遇到键不存在的情况，如果强行调用不存在的键，程序不会报错，而是会返回一个空值。
• 但通常情况下，我们并不希望它返回空值，而是进行其他操作。所以，我们可以使用 hs.count(key)方法 来查询键是否存在。此方法的原理是返回哈希表中键与传入的 key 相同的键值对的数量，但根据键唯一的特性，此方法通常只会返回两个值，即 0 或 1 。

if( hs.count(key) == 0 )
    cout << "键值对不存在！";
else ( hs.count(key) == 1 )
    cout << "键值对存在！";

至此，哈希表的基本用法讲解完毕

---

完整代码展示

题目：使用哈希表完成以下功能：创建一个简单的中英词典，用户可以根据中文查询英文（ 进阶：也可以根据英文查询中文 ），并且用户可以向词典中添加和删除内容。

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

//这里我将大部分哈希表的相关操作单独写在getVal方法中，以便读者单独理解
//这里哈希表hs用引用类型，防止二次拷贝，从而节省内存
void getVal(unordered_map<string, string>& hs, string key) {
    if (key[0] >= 65 && key[0] <= 122) {
        //根据英文（值）查询中文（键）
        //遍历哈希表
        for (const auto& p : hs) {
            if (p.second == key) {
                cout << "对应的翻译是：" << p.first << endl;
                return;
            }
        }
        cout << "未查询到值!" << endl;
        return;
    }
    if (hs.count(key) == 0) {  //查询指定值的数量
        cout << "未查询到值!" << endl;
        return;
    }
    //根据中文（键）查询英文（值）
    cout << "对应的翻译是：" << hs[key] << endl;
}

int main() {
    //声明一个哈希表
    unordered_map<string, string> hs;
    //向哈希表中添加一些初始数据
    hs.insert({ "蝾螈", "newt" });
    hs.insert({ "章鱼", "octopus"});
    hs.insert({ "水豚", "capybara"});
    hs.insert({ "牛蛙", "bullfrog" });
    hs.insert({ "臭鼬", "skunk" });
    cout << "输入\"退出\"退出程序，输入\"删除\"删除单词，输入\"增加\"增加单词" << endl;
    while (true) {
        cout << "输入查询的单词：";
        string s; cin >> s;
        if (s == "删除") {
            //此处仅举例根据键删除，若要根据值删除同理遍历哈希表即可
            cout << "请输入要删除的单词的中文:";
            cin >> s;
            hs.erase(s);
            cout << "已删除！" << endl;
        }
        else if (s == "退出")
            break;
        else if (s == "增加") {
            //将用户输入的字符串作为参数传递给insert
            cout << "请输入中文:";
            string chinese; cin >> chinese;
            cout << "请输入英文:";
            string english; cin >> english;
            hs.insert({ chinese, english });
            cout << "已添加！" << endl;
        }
        else 
            getVal(hs, s);
    }
    return 0;
}

如需提问，可以在评论区留言或私信（=

感谢您的阅读（=

by.Qin3Yu