小白：大牛你好！我最近学习了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的工作原理和利用方法。
大牛：不客气，假如你有任何疑问，随时可以问我。
小白：那我再问一个问题吧，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的底层实现和利用方法都有了更深入的理解。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
