C++哈希表使用详解

一、哈希表基础

哈希表是一种不同于常规数组或链表的数据结构，通过哈希函数将数据映射到不同的槽位上，使得数据的查找、插入和删除操作时间复杂度为O(1)。C++ STL中提供了unordered_map和unordered_set两个哈希表的实现，它们的底层实现都是使用哈希表。

使用哈希表时，我们通常需要关注哈希函数的设计和冲突解决方法。哈希函数应当将数据均匀地分散在不同的槽位上，并且能够处理不同类型的数据；而冲突解决方法则需要保证数据不会重复，并且插入、删除时不会影响其他数据。

二、unordered_map用法

unordered_map是C++ STL中实现的哈希表，其使用方法与map基本相同，但相比于map，其查找、插入、删除的时间复杂度更低且不需要数据排序。以下是unordered_map的简单示例：

#include 
#include 
#include 

using namespace std;

int main() {
    unordered_map m;
    m[1] = "hello";
    m[2] = "world";
    m[3] = "!";
    cout << m[2] << endl; // 输出 world
    return 0;
}

在上述代码中，我们使用了unordered_map来存储int和string类型的键值对，通过下标访问map中的元素，并输出了键为2的元素的值。

三、哈希函数设计

哈希函数是哈希表的核心，一个好的哈希函数能够有效地减少数据冲突。以下是一个简单的哈希函数设计：

size_t hash_func(const string& str) {
    size_t hash_value = 0;
    for (const auto& c : str) {
        hash_value = 31 * hash_value + c;
    }
    return hash_value;
}

在上述代码中，我们采用了djb2哈希算法，将每个字符的ASCII码乘以一个质数31，并加上前面字符的哈希值，最终得到一个哈希值。

四、哈希冲突解决

当两个不同的数据被哈希函数映射到同一个槽位时，就会发生哈希冲突。为了解决哈希冲突，我们通常需要使用链表、开放寻址等技术。以下是开放寻址法的示例代码：

template 
class OpenAddrHashTable {
public:
    explicit OpenAddrHashTable(size_t size = 1000) : size_(size) {
        table_ = new std::pair[size];
        ++size_;
    }

    ~OpenAddrHashTable() {
        delete[] table_;
    }

    OpenAddrHashTable(const OpenAddrHashTable&) = delete;

    OpenAddrHashTable& operator=(const OpenAddrHashTable&) = delete;

    void insert(const Key& key, const Value& value) {
        size_t hash_value = hash_func(key);
        size_t i = hash_value % size_;
        size_t j = i;
        while (table_[j].first != key && table_[j].first != Key()) {
            ++j;
            if (j == size_)
                j = 0;
            if (j == i)
                throw std::runtime_error("hash table full");
        }
        table_[j] = std::make_pair(key, value);
    }

    Value& search(const Key& key) const {
        size_t i = hash_func(key) % size_;
        size_t j = i;
        while (table_[j].first != key && table_[j].first != Key()) {
            ++j;
            if (j == size_)
                j = 0;
            if (j == i)
                throw std::runtime_error("key not found");
        }
        return table_[j].second;
    }

private:
    size_t size_;
    std::pair* table_;

    size_t hash_func(const Key& key) const {
        // 哈希函数的实现
    }
};

在OpenAddrHashTable中，我们使用了开放寻址法来解决哈希冲突。当数据插入时，如果对应的槽位已经被占用，就从下一个槽位开始往后查找，直到找到空槽位为止；当数据查找时，如果对应的槽位不是要查找的数据，就继续从下一个槽位开始往后查找，直到找到要查找的数据或者槽位为空为止。

五、总结

哈希表是一种高效的数据结构，适用于需要快速查找、插入和删除的场景。C++ STL中通过unordered_map和unordered_set提供了哈希表的实现，我们可以根据业务需求选择不同的实现方式。同时，针对特定的问题场景，我们也可以自己实现哈希表来达到更好的效果。