c++算法实现拉链法散列表的查找

拉链法散列表（Chained Hashing），也称为开放地址法结合链表，是一种常见的哈希表实现策略。在C++中，它通过数组作为底层存储，每个位置可以链接多个元素（即链表节点），当发生冲突（两个键值映射到同一个数组位置）时，新插入的元素会添加到该位置的链表中。

查找操作的基本步骤如下：

1. **计算哈希值**：首先，对需要查找的键值应用一个哈希函数，得到其在数组中的索引。哈希函数的设计很重要，尽量保证不同的键值有较小的概率落在同一个位置上。

2. **遍历链表**：如果计算出的索引处不是空的，就开始遍历该位置的链表。对于每个节点，检查它的键值是否与目标键相等。

3. **查找匹配**：如果找到相同的键值，返回对应的值；如果没有找到，则表示元素不存在。

struct Node {
    int key;
    int value;
    Node* next; // 链表指针
};

class ChainedHashTable {
private:
    int capacity;
    Node** table; // 存储链表头节点的数组

public:
    // 构造函数
    ChainedHashTable(int size) {
        capacity = size;
        table = new Node*[capacity];
        for (int i = 0; i < capacity; ++i)
            table[i] = nullptr;
    }

    // 查找方法
    int find(const int& key) const {
        int index = hashFunction(key);
        if (table[index] == nullptr)
            return -1; // 键不存在

        Node* current = table[index];
        while (current != nullptr) {
            if (current->key == key)
                return current->value;

            current = current->next;
        }
        return -1; // 没找到
    }

private:
    // 实现哈希函数
    int hashFunction(int key) const {
        // 假设简单的取模操作
        return key % capacity;
    }
};