一、unordered_map简介
C++ STL中的unordered_map是基于哈希表（hash table）实现的关联容器。哈希表是一种将key-value映射存储的数据结构，它允许常数时间内进行插入、删除和查找操作。
unordered_map的每个元素包含一个key和value，元素之间没有顺序关系。因此，在进行查找操作时，需要通过哈希函数找到对应的桶，对桶中的元素进行搜索。因此，unordered_map的查找、插入、删除操作的时间复杂度都是O(1)，相对于普通的红黑树实现的map，高效得多。
以下是unordered_map的常用操作：
// 声明一个unordered_map
std::unordered_map<int, std::string> umap;
// 插入key-value
umap.insert(std::make_pair(1, "value1"));
umap.insert({2, "value2"});
// 查找元素
if (umap.find(1) != umap.end()) {
std::cout << "Found element with key 1" << std::endl;
}
// 修改元素
umap[1] = "new value1";
// 删除元素
umap.erase(2);
// 遍历unordered_map
for (const auto& kv : umap) {
std::cout << kv.first << ": " << kv.second << std::endl;
}
二、unordered_map的内部实现原理
unordered_map的内部实现主要由哈希函数、哈希表、桶和节点组成。哈希函数用于将key映射到对应的桶中，每个桶保存对应的节点。节点包含key、value以及指向下一个节点的指针。
哈希函数的设计非常重要，它的优秀程度将直接影响unordered_map插入、查找、删除等操作的效率。常见的哈希函数有除留余数法、乘法散列法和随机旋转哈希等。具体实现中，STL使用除留余数法（%运算符）作为哈希函数的默认实现。下面是一个例子：
std::unordered_map<std::string, int> umap(8);
std::hash<std::string> hasher; // 哈希函数
std::size_t hash_val = hasher("hello world");
std::size_t bucket_num = hash_val % umap.bucket_count(); // 计算桶的索引
umap.insert(std::make_pair("hello world", 42));
插入元素时，将先使用哈希函数计算key的哈希值，然后将哈希值对桶的数量取模得到桶的索引。桶的数量最好选择一个质数，可以减少哈希冲突的概率。
如果桶中已经存在一个节点，这种情况称为哈希冲突。STL中使用链式法（chaining）解决哈希冲突，即将节点插入到桶对应链表的末尾。当节点数量太大时，桶中的链表可能会退化成一条很长的链表，时间复杂度可能退化到O(n)。
三、unordered_map的应用案例
unordered_map在实际应用中非常常用，尤其在需要高效的查找和插入操作时大受欢迎。下面是unordered_map的几个应用案例：
1、单词统计、列表去重
std::unordered_map<std::string, int> word_count;
std::vector<std::string> words = { "hello", "world", "hello", "foo", "bar", "foo" };
for (const auto& w : words) {
++word_count[w];
}
for (const auto& kv : word_count) {
std::cout << kv.first << ": " << kv.second << std::endl;
}
std::unordered_set<std::string> word_set(words.begin(), words.end());
for (const auto& w : word_set) {
std::cout << w << std::endl;
}
以上代码可以统计输入字符串中每个单词出现的次数，并去重输出。
2、图的邻接表表示
unordered_map可以用于实现图的邻接表（adjacency list）表示法，即用一个unordered_map保存每个节点以及与之相邻的节点集合。下面是一个例子：
std::unordered_map<int, std::vector<int>> adj_list;
adj_list[0] = { 1, 2 };
adj_list[1] = { 0, 2, 3 };
adj_list[2] = { 0, 1, 3 };
adj_list[3] = { 1, 2 };
以上代码可以实现一个无向图，每个节点都与若干个相邻节点相连。
3、LRU缓存
unordered_map可以用于实现LRU（Least Recently Used）缓存，即缓存数据时，如果缓存空间满了，则替换最近最少被使用的数据。可以使用两个数据结构：unordered_map和双向链表。unordered_map用于实现key到节点的映射，双向链表用于维护节点的顺序。
使用unordered_map保存key与链表中的节点的映射，使用双向链表维护节点顺序，链表中的元素按照访问时间从旧到新排序。以下是LRU缓存的具体实现：
class LRUCache {
public:
LRUCache(int capacity) : capacity_(capacity) {}
int get(int key) {
auto it = cache_.find(key);
if (it == cache_.end()) {
return -1;
}
touch(it->second);
return it->second.value;
}
void put(int key, int value) {
auto it = cache_.find(key);
if (it != cache_.end()) {
touch(it->second);
it->second.value = value;
} else {
if (cache_.size() == capacity_) {
evict();
}
Node* new_node = new Node(key, value);
cache_[key] = *new_node;
add(new_node);
}
}
private:
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};
void touch(Node& node) {
// 将node从链表中删除
node.prev->next = node.next;
node.next->prev = node.prev;
// 将node加入链表尾部
add(&node);
}
void evict() {
// 删除链表头部元素
Node* removed = head_.next;
head_.next = head_.next->next;
head_.next->prev = &head_;
cache_.erase(removed->key);
delete removed;
}
void add(Node* node) {
// 将node加入链表尾部
node->prev = tail_.prev;
node->next = &tail_;
tail_.prev->next = node;
tail_.prev = node;
}
int capacity_;
std::unordered_map<int, Node> cache_;
Node head_; // 哨兵节点，链表头部的前一个节点
Node tail_; // 哨兵节点，链表尾部的后一个节点
};
以上代码实现了一个带有get和put操作的LRU缓存，可以用于缓存key-value对，保持访问时间越新的元素越靠近链表尾部，访问时间越旧的元素越靠近链表头部。如果缓存空间满了，则将访问时间最早的元素删除。
