面试题：C++ 哈希表冲突处理方式及实现

Question

在C++中实现哈希表时，冲突是常见问题。请描述至少两种处理哈希表冲突的方法，并使用C++代码示例实现其中一种方法。

Answer 1

处理哈希表冲突的方法

1. 开放定址法：当发生冲突时，通过某种探查序列在哈希表中寻找下一个空的位置来存储数据。常见的探查序列有线性探查、二次探查等。
2. 链地址法（拉链法）：哈希表每个位置都维护一个链表，当发生冲突时，将冲突的元素插入到对应位置的链表中。

链地址法（拉链法）代码示例

#include <iostream>
#include <list>
#include <functional>

const int hashTableSize = 10;

class HashTable {
private:
    std::list<int> table[hashTableSize];

public:
    int hashFunction(int key) {
        return key % hashTableSize;
    }

    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }

    bool search(int key) {
        int index = hashFunction(key);
        for (int element : table[index]) {
            if (element == key) {
                return true;
            }
        }
        return false;
    }
};

可以通过以下方式调用：

int main() {
    HashTable hashTable;
    hashTable.insert(10);
    hashTable.insert(20);
    hashTable.insert(30);

    std::cout << "Search 20: " << (hashTable.search(20)? "Found" : "Not Found") << std::endl;
    std::cout << "Search 40: " << (hashTable.search(40)? "Found" : "Not Found") << std::endl;

    return 0;
}