学会吊打面试官之underedmap

 

小白:大牛你好!我最近学习了STL容器,看到有个叫做unordered_map的容器,这是什么?

大牛:unordered_map是一个无序的关联式容器,也就是一种键值对的存储结构,其中的元素没有固定的顺序。它和map类似,但是比map更快,适用于需要高效查找的场合。

小白:那unordered_map有哪些特点和用法呢?

大牛:unordered_map的特点主要是快速的查找速度,底层是通过哈希表实现的,所以在查找元素时平均时间复杂度为O(1)。而且,unordered_map的元素不是按照插入的顺序排列的,而是按照哈希值排列的。它的用法和map基本一致,可以使用insert、find、erase等函数。

小白:那我们来看一个具体的例子吧!

大牛:当然可以。比如我们要统计一段英文文本中每个单词出现的次数,可以使用unordered_map来实现。我们可以将每个单词作为键,出现次数作为值,然后遍历整个文本,将单词插入到unordered_map中,如果这个单词已经在unordered_map中存在,就将对应的值加1,否则插入一个新的键值对。

下面是一个简单的示例代码:

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main()
{
    unordered_map<string, int> wordCount;
    string word;
    while (cin >> word)
    {
        ++wordCount[word];
    }
    for (const auto& pair : wordCount)
    {
        cout << pair.first << ": " << pair.second << endl;
    }
    return 0;
}

这段代码会读入一段英文文本,统计每个单词出现的次数,并输出结果。在这个示例中,unordered_map的键是string类型的单词,值是int类型的出现次数。

小白:感谢大牛的解释,我终于理解了unordered_map的工作原理和使用方法。

大牛:不客气,如果你有任何疑问,随时可以问我。

小白:那我再问一个问题吧,unordered_map和map有什么区别?

大牛:这是一个常见的问题。unordered_map和map都是关联容器,但它们的实现方式不同。unordered_map内部使用哈希表实现,而map内部使用红黑树实现。哈希表的查找速度非常快,但是哈希表并不保证元素的顺序,而红黑树则可以保证元素的有序性。

小白:那么,我应该使用哪一个?

大牛:这取决于你的需求。如果你对元素的顺序没有要求,只是希望查找速度尽可能快,那么就可以使用unordered_map。如果你需要保证元素的顺序,或者需要进行范围查找等操作,那么就应该使用map。

小白:那我再问一个问题,unordered_map的底层实现原理是什么呢?

大牛:unordered_map的底层实现原理就是哈希表,哈希表是一种非常高效的数据结构。哈希表可以将键映射到一个唯一的索引值,这个索引值就是哈希值。然后,将键值对存储在这个索引值对应的位置,这样在查找时就可以直接根据键的哈希值来找到对应的位置,而无需遍历整个容器。

小白:那么,哈希表是如何处理哈希冲突的呢?

大牛:哈希冲突指的是不同的键可能会映射到同一个索引值的情况。哈希表需要处理哈希冲突,以保证键值对能够正确地存储和查找。哈希表处理哈希冲突的方法有很多种,最常用的方法是链表法。在链表法中,哈希表的每个位置不再存储一个单独的键值对,而是存储一个链表,所有哈希值相同的键值对都存储在这个链表中。这样,当发生哈希冲突时,只需要将新的键值对插入到对应位置的链表中即可。

小白:哦,我大概明白了,能否再举一个例子呢?

大牛:当然可以。比如我们要实现一个电话簿程序,可以使用unordered_map来存储每个人的姓名和电话号码。我们可以将每个人的姓名作为键,电话号码作为值,然后遍历整个电话簿,将每个人的姓名和电话号码插入到unordered_map中。如果发现姓名已经在unordered_map中存在,就更新对应的电话号码。

下面是一个简单的示例代码:

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main()
{
    unordered_map<string, string> phonebook;
    string name, phone;
    while (cin >> name >> phone)
    {
        phonebook[name] = phone;
    }
    for (const auto& pair : phonebook)
    {
        cout << pair.first << ": " << pair.second << endl;
    }
    return 0;
}

这段代码会读入一些人的姓名和电话号码,将它们存储在unordered_map中,并输出结果。在这个示例中,unordered_map的键是string类型的姓名,值是string类型的电话号码。

小白:感谢大牛的解释和示例代码,我现在对unordered_map的底层实现和使用方法都有了更深入的理解。