学会吊打面试官之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的底层实现和使用方法都有了更深入的理解。