C++ Hash沖突解決方法

在C++中，哈希沖突是指兩個不同的輸入值經過哈希函數處理后，得到了相同的哈希值。為了解決這個問題，我們可以采用以下幾種方法：

1. 鏈地址法（Separate Chaining）： 鏈地址法是一種常見的解決哈希沖突的方法。在這種方法中，哈希表的每個槽位都指向一個鏈表。當發生哈希沖突時，將具有相同哈希值的元素添加到該槽位的鏈表中。查找、插入和刪除操作都需要遍歷鏈表。

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

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

    void insert(const std::string& key) {
        size_t index = hash(key) % table.size();
        table[index].push_back(key);
    }

    bool search(const std::string& key) const {
        size_t index = hash(key) % table.size();
        for (const auto& item : table[index]) {
            if (item == key) {
                return true;
            }
        }
        return false;
    }

    void remove(const std::string& key) {
        size_t index = hash(key) % table.size();
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (*it == key) {
                table[index].erase(it);
                break;
            }
        }
    }

private:
    std::vector<std::list<std::string>> table;

    size_t hash(const std::string& key) const {
        size_t hash_value = 0;
        for (char c : key) {
            hash_value = 31 * hash_value + c;
        }
        return hash_value;
    }
};

2. 開放地址法（Open Addressing）： 開放地址法是一種線性探測的方法，當發生哈希沖突時，會按照一定的規則尋找下一個可用的槽位。常見的開放地址法有線性探測、二次探測和雙散列。

線性探測：

size_t linearProbing(size_t index, size_t size) {
    return (index + 1) % size;
}

二次探測：

size_t quadraticProbing(size_t index, size_t size) {
    return (index * index) % size;
}

雙散列：

size_t doubleHashing(size_t index, size_t size, size_t seed) {
    return (hash(index, seed) % size);
}

size_t hash(size_t index, size_t seed) {
    return index * seed;
}

3. 再哈希法（Rehashing）： 再哈希法是當哈希表的大小不足以存儲所有元素時，可以通過增加哈希表的大小并重新計算哈希值來解決沖突。這種方法可以避免鏈地址法和開放地址法的空間開銷。

HashTable resize(HashTable& table, size_t newSize) {
    std::vector<std::list<std::string>> newTable(newSize);
    for (const auto& bucket : table.table) {
        for (const auto& item : bucket) {
            size_t newIndex = hash(item, newSize) % newSize;
            newTable[newIndex].push_back(item);
        }
    }
    return HashTable(newSize, newTable);
}

這些方法可以單獨使用，也可以組合使用，以滿足不同的需求和場景。在實際應用中，可以根據數據的特點和性能要求選擇合適的哈希沖突解決方法。