C++哈希表实现方法详解

C++中实现哈希表有两种方式：一是使用标准库的unordered_map和unordered_set，二是手动实现。首先，unordered_map和unordered_set是C++11引入的基于哈希的容器，分别用于存储键值对和唯一元素集合，具有高效查找性能。示例代码展示了如何用unordered_map插入和访问数据。其次，手动实现哈希表可通过链地址法解决冲突，文中提供了一个使用vector和list实现的简单哈希表类，包含插入、查找、删除操作，哈希函数采用字符串ASCII码求和取模。注意事项包括选择良好哈希函数、动态扩容、线程安全及自定义类型支持。日常开发推荐使用标准库容器，学习或特殊需求时可参考手动实现。

在C++中实现哈希表，主要有两种方式：使用标准库提供的unordered_map和unordered_set，或者手动实现一个简单的哈希表。下面分别介绍这两种方法。

使用C++标准库的哈希表

C++11引入了基于哈希的容器，定义在<unordered_map>和<unordered_set>头文件中。

示例代码：

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> hashTable;
    hashTable["apple"] = 5;
    hashTable["banana"] = 3;
    
    cout << "apple: " << hashTable["apple"] << endl;
    return 0;
}

这种方法简单高效，适合大多数应用场景。

手动实现简易哈希表

如果需要理解底层原理或定制行为，可以自己实现一个线性探测或链地址法的哈希表。

以下是一个使用链地址法（拉链法）实现的简单哈希表示例：

#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;

class HashTable {
private:
    static const int TABLE_SIZE = 100;
    vector<list<pair<string, int>>> table;

    int hash(const string& key) {
        int sum = 0;
        for (char c : key) sum += c;
        return sum % TABLE_SIZE;
    }

public:
    HashTable() : table(TABLE_SIZE) {}

    void insert(const string& key, int value) {
        int index = hash(key);
        for (auto& pair : table[index]) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        table[index].push_back({key, value});
    }

    bool find(const string& key, int& value) {
        int index = hash(key);
        for (const auto& pair : table[index]) {
            if (pair.first == key) {
                value = pair.second;
                return true;
            }
        }
        return false;
    }

    void remove(const string& key) {
        int index = hash(key);
        table[index].remove_if([&](const pair<string, int>& p) {
            return p.first == key;
        });
    }
};

这个实现包括基本操作：插入、查找、删除。冲突通过链表解决，哈希函数采用字符ASCII码求和取模。

注意事项与优化建议

手动实现时需要注意以下几点：

基本上就这些。对于日常开发，推荐优先使用unordered_map；学习或特殊需求时，可参考手动实现方式加深理解。