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對，保持訪問時間越新的元素越靠近鏈表尾部，訪問時間越舊的元素越靠近鏈表頭部。如果緩存空間滿了，則將訪問時間最早的元素刪除。