C++ Hash表與鏈表結合應用

在C++中，哈希表（Hash Table）和鏈表（Linked List）可以結合應用，以實現更高效的數據存儲和訪問。哈希表提供了快速的查找、插入和刪除操作，而鏈表則提供了動態內存分配和插入操作的優勢。結合這兩種數據結構，可以實現一個高效的數據結構，既能夠快速查找數據，又能夠靈活地插入和刪除數據。

下面是一個簡單的示例，展示了如何將哈希表和鏈表結合應用：

#include <iostream>
#include <unordered_map>
#include <list>

template <typename Key, typename Value>
class HashLinkedList {
public:
    // 查找鍵對應的值
    Value get(const Key& key) const {
        auto it = hash_table.find(key);
        if (it != hash_table.end()) {
            return it->second;
        }
        return Value(); // 如果找不到，返回默認值
    }

    // 插入鍵值對
    void insert(const Key& key, const Value& value) {
        if (hash_table.find(key) == hash_table.end()) {
            hash_table[key] = value;
            linked_list.push_back(key);
        }
    }

    // 刪除鍵值對
    void remove(const Key& key) {
        auto it = hash_table.find(key);
        if (it != hash_table.end()) {
            hash_table.erase(it);
            // 從鏈表中刪除鍵
            auto list_it = std::find(linked_list.begin(), linked_list.end(), key);
            if (list_it != linked_list.end()) {
                linked_list.erase(list_it);
            }
        }
    }

private:
    std::unordered_map<Key, Value> hash_table; // 哈希表
    std::list<Key> linked_list; // 鏈表
};

int main() {
    HashLinkedList<int, std::string> hash_linked_list;
    hash_linked_list.insert(1, "one");
    hash_linked_list.insert(2, "two");
    hash_linked_list.insert(3, "three");

    std::cout << "Key 1: " << hash_linked_list.get(1) << std::endl;
    std::cout << "Key 2: " << hash_linked_list.get(2) << std::endl;
    std::cout << "Key 3: " << hash_linked_list.get(3) << std::endl;

    hash_linked_list.remove(2);

    std::cout << "After removing Key 2:" << std::endl;
    std::cout << "Key 1: " << hash_linked_list.get(1) << std::endl;
    std::cout << "Key 2: " << hash_linked_list.get(2) << std::endl;
    std::cout << "Key 3: " << hash_linked_list.get(3) << std::endl;

    return 0;
}

在這個示例中，我們定義了一個名為HashLinkedList的模板類，它包含一個哈希表（std::unordered_map）和一個鏈表（std::list）。哈希表用于存儲鍵值對，鏈表用于存儲鍵的順序。通過這種方式，我們可以在O(1)時間復雜度內查找鍵對應的值，同時保持插入和刪除操作的靈活性。