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

这些方法可以单独使用，也可以组合使用，以满足不同的需求和场景。在实际应用中，可以根据数据的特点和性能要求选择合适的哈希冲突解决方法。