Hash算法在C++中的冲突解决策略

在C++中，哈希算法可能会遇到冲突，即不同的输入值映射到相同的哈希值。为了解决这个问题，我们可以采用以下几种冲突解决策略：

1. 链地址法（Separate Chaining）： 链地址法是一种常见的冲突解决方法。在这种方法中，哈希表的每个槽位都指向一个链表。当发生冲突时，新的元素将被添加到链表的末尾。查找和删除操作需要遍历链表，直到找到目标元素或到达链表末尾。

#include <iostream>
#include <list>
#include <vector>

class HashTable {
public:
    HashTable(size_t size) : table(size) {}

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

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

    void remove(int key) {
        size_t index = hash(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (*it == key) {
                table[index].erase(it);
                break;
            }
        }
    }

private:
    size_t hash(int key) {
        return key % table.size();
    }

    std::vector<std::list<int>> table;
};

2. 开放地址法（Open Addressing）： 开放地址法是一种线性探测的冲突解决方法。当发生冲突时，新的元素将被添加到哈希表的下一个槽位，直到找到一个空槽位。查找和删除操作需要遍历哈希表，直到找到目标元素或到达一个空槽位。

#include <iostream>
#include <vector>

class HashTable {
public:
    HashTable(size_t size) : table(size, nullptr), size(size) {}

    void insert(int key) {
        size_t index = hash(key);
        while (table[index] != nullptr) {
            if (table[index] == key) {
                return;
            }
            index = (index + 1) % size;
        }
        table[index] = key;
    }

    bool search(int key) {
        size_t index = hash(key);
        while (table[index] != nullptr) {
            if (table[index] == key) {
                return true;
            }
            index = (index + 1) % size;
        }
        return false;
    }

    void remove(int key) {
        size_t index = hash(key);
        while (table[index] != nullptr) {
            if (table[index] == key) {
                table[index] = nullptr;
                return;
            }
            index = (index + 1) % size;
        }
    }

private:
    size_t hash(int key) {
        return key % size;
    }

    std::vector<int*> table;
    size_t size;
};

这两种冲突解决策略各有优缺点。链地址法在空间效率上较高，因为每个槽位只需要存储一个链表节点。而开放地址法在空间效率上较低，因为需要额外的空间来存储探测路径。然而，开放地址法在某些情况下可以实现更好的负载因子，从而提高查找和删除操作的性能。