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)时间复杂度内查找键对应的值，同时保持插入和删除操作的灵活性。