C++ unordered_map实现原理及应用案例详解

一、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对，保持访问时间越新的元素越靠近链表尾部，访问时间越旧的元素越靠近链表头部。如果缓存空间满了，则将访问时间最早的元素删除。