C++ 实现哈希表的实例

下面是“C++ 实现哈希表的实例”的攻略。

什么是哈希表？

哈希表是一种用于存储键值对的数据结构，它通过哈希函数将键映射为一个确定的桶，然后将键值对存储到对应的桶中。哈希表的主要优势是能够支持快速的插入、查找和删除操作，因为它的查找时间是常数级别的，即 O(1)。

实现哈希表的基本步骤

在 C++ 中实现哈希表的基本步骤如下：

1. 定义哈希函数：通常情况下，哈希函数会将键转化为一个整数值。可以使用 C++11 新增的 std::hash 及其特化模板来实现哈希函数，也可以自己定义哈希函数。
2. 定义哈希表的数据结构：哈希表通常由一个数组和一个哈希函数组成，在数组中存储键值对。每个键值对是一个链表中的节点，用于解决哈希值冲突的问题。
3. 实现哈希表的插入、查找和删除操作：哈希表的操作与链表非常类似，不同的是需要先对键进行哈希，然后找到对应的桶。

具体步骤我们将在下面的示例中说明。

示例1：使用 C++11 的 std::hash 实现哈希表

下面是一个使用 C++11 的 std::unordered_map 实现哈希表的示例。

#include <iostream>
#include <unordered_map>

int main()
{
    // 创建一个 unordered_map 容器，用于存储字符串和对应的整数值
    std::unordered_map<std::string, int> hashmap;

    // 添加键值对
    hashmap["hello"] = 1;
    hashmap["world"] = 2;
    hashmap["test"] = 3;

    // 查找键对应的值
    std::cout << hashmap["hello"] << std::endl;

    // 删除键值对
    hashmap.erase("test");

    return 0;
}

上面的代码中，我们先使用 std::unordered_map 定义了一个哈希表，它包含 std::string 类型的键和 int 类型的值。然后我们使用 [] 操作符向哈希表中添加键值对，并使用 [] 操作符找到键对应的值。最后使用 erase 函数删除键值对。这些操作与使用普通的数组非常相似，而且它们的时间复杂度也是常数级别的。

示例2：手动实现哈希表

下面是一个手动实现哈希表的示例，其中我们使用了一个简单的哈希函数和链表来解决哈希冲突的问题。

#include <iostream>
#include <string>

const int TABLE_SIZE = 128;

class Node
{
public:
    std::string key;
    int value;
    Node* next;

    Node(const std::string& key, int value) :
        key(key), value(value), next(nullptr)
    {}
};

class HashMap
{
private:
    Node** table;
    std::hash<std::string> hashFunc;

public:
    HashMap()
    {
        table = new Node*[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
        {
            table[i] = nullptr;
        }
    }

    ~HashMap()
    {
        for (int i = 0; i < TABLE_SIZE; i++)
        {
            Node* node = table[i];
            while (node != nullptr)
            {
                Node* temp = node;
                node = node->next;
                delete temp;
            }
        }
        delete[] table;
    }

    void put(const std::string& key, int value)
    {
        int index = hashFunc(key) % TABLE_SIZE;
        Node* node = table[index];

        if (node == nullptr)
        {
            table[index] = new Node(key, value);
        }
        else
        {
            while (node != nullptr)
            {
                if (node->key == key)
                {
                    node->value = value;
                    return;
                }
                else if (node->next == nullptr)
                {
                    node->next = new Node(key, value);
                    return;
                }
                node = node->next;
            }
        }
    }

    int get(const std::string& key)
    {
        int index = hashFunc(key) % TABLE_SIZE;
        Node* node = table[index];
        while (node != nullptr)
        {
            if (node->key == key)
            {
                return node->value;
            }
            node = node->next;
        }
        return -1;
    }

    void remove(const std::string& key)
    {
        int index = hashFunc(key) % TABLE_SIZE;
        Node* node = table[index];
        if (node == nullptr)
        {
            return;
        }
        else if (node->key == key)
        {
            table[index] = node->next;
            delete node;
        }
        else
        {
            while (node->next != nullptr)
            {
                if (node->next->key == key)
                {
                    Node* temp = node->next;
                    node->next = node->next->next;
                    delete temp;
                    return;
                }
                node = node->next;
            }
        }
    }
};

int main()
{
    // 创建一个哈希表，用于存储字符串和对应的整数值
    HashMap hashmap;

    // 添加键值对
    hashmap.put("hello", 1);
    hashmap.put("world", 2);
    hashmap.put("test", 3);

    // 查找键对应的值
    std::cout << hashmap.get("hello") << std::endl;

    // 删除键值对
    hashmap.remove("test");

    return 0;
}

上面的代码中，我们手动实现了哈希表的插入、查找和删除操作。具体来说，我们使用 std::hash 实现了一个简单的哈希函数，将字符串转化为一个整数并求模，然后根据这个整数找到对应的桶。每个桶是一个链表，用于存储键值对。我们实现了 put、get 和 remove 函数来完成哈希表的插入、查找和删除操作，这些操作的时间复杂度都是常数级别的。