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;
};

這兩種沖突解決策略各有優缺點。鏈地址法在空間效率上較高，因為每個槽位只需要存儲一個鏈表節點。而開放地址法在空間效率上較低，因為需要額外的空間來存儲探測路徑。然而，開放地址法在某些情況下可以實現更好的負載因子，從而提高查找和刪除操作的性能。