【C++数据结构 | 哈希表速通】哈希表完成英汉词典增删改查 | 哈希表实现类型unordered_map详解

发布时间:2023年12月17日

哈希表

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.firstp.second 就分别表示 p 包含的两个变量,即

在这里插入图片描述

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

查询键是否存在( count )

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

文章来源:https://blog.csdn.net/qq_38970634/article/details/135049138
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。