许多开发者认为std::set和std::multiset是基于哈希表的，但实际上它们底层采用红黑树实现。虽然这些容器确实使用了哈希函数进行映射，但数据存储结构是红黑树而非哈希表。

在C++标准演进过程中，hash_set和hash_map曾是非标准扩展（常见于SGI STL实现），而unordered_set和unordered_map从C++11开始成为标准库成员。尽管两者功能相似，但官方标准推荐的unordered_*系列更稳定可靠。

在算法面试中，判断元素是否存在的场景应优先采用哈希策略。相比std::set，数组实现的哈希表占用空间更小、查询速度更快——因为set需要为每个键计算哈希值并维护红黑树结构。当数据量增大时，性能差异会变得显著。

哈希表核心原理

基本实现思路：声明布尔数组hashtable[]，读取数字x时设置hashtable[x]=true，查询时检查hashtable[y]是否有效。若要统计出现次数，可将布尔值替换为整数计数器。

问题一：数值范围超出数组容量
解决方案：通过哈希函数将大数映射到较小范围。取模运算key % M是常用方法，建议选择素数作为模数以获得更好的分布性。

冲突处理方案：

• 线性探测法：检查h(key)+1位置，若被占用则继续探测下一个位置，到达表尾后循环查找
• 平方探测法：依次检查h(key)+1²、h(key)-1²、h(key)+2²...
• 链地址法：在冲突位置建立链表存储多个值

实际开发中直接使用std::unordered_map即可，无需手动实现。

问题二：字符串哈希
将字符串视为特定进制数：例如26进制（大写字母）可转换为十进制整数。代码实现如下：

// 26进制字符串转整数（仅大写字母）
int hashString(const char str[], int length) {
    int code = 0;
    for (int i = 0; i < length; ++i) {
        code = code * 26 + (str[i] - 'A');
    }
    return code;
}

当包含大写字母（A-Z）、小写字母（a-z）时，可扩展为52进制：

int code = 0;
for (int i = 0; i < len; ++i) {
    if (str[i] >= 'A' && str[i] <= 'Z')
        code = code * 52 + (str[i] - 'A');
    else if (str[i] >= 'a' && str[i] <= 'z')
        code = code * 52 + 26 + (str[i] - 'a');
}

若包含数字可将进制扩展至62。对于ben4这种字母+固定位数数字的模式，可先处理字母部分再拼接数字。

经典题目解析

1. 旧键盘问题

题目：给定原始字符串This_is_a_test和实际输出_hs_s_a_es，找出损坏的键。

#include <iostream>
#include <string>
const int ASCII_SIZE = 256;

int main() {
    std::string original, typed;
    std::cin >> original >> typed;
    bool keyMap[ASCII_SIZE] = {false};

    for (char ch : typed) {
        keyMap[toupper(ch)] = true;
    }

    for (char ch : original) {
        char upper = toupper(ch);
        if (!keyMap[upper]) {
            std::cout << upper;
            keyMap[upper] = true;  // 避免重复输出
        }
    }
    return 0;
}

2. 坏键盘打字问题

题目：已知损坏的键和原始输入，输出实际显示的字符。

#include <iostream>
#include <string>
#include <cstring>

bool workingKeys[256];

int main() {
    memset(workingKeys, true, sizeof(workingKeys));
    std::string broken, input;
    std::cin >> broken >> input;

    for (char ch : broken) {
        workingKeys[tolower(ch)] = false;
    }

    for (char ch : input) {
        if (ch >= 'A' && ch <= 'Z') {
            // 大写字母需检查+键和对应小写键
            if (workingKeys['+'] && workingKeys[ch + 32])
                std::cout << ch;
        } else if (workingKeys[ch]) {
            std::cout << ch;
        }
    }
    return 0;
}

3. 数组交集问题（哈希表法）

std::vector<int> getIntersection(std::vector<int>& nums1, std::vector<int>& nums2) {
    if (nums1.size() > nums2.size()) {
        return getIntersection(nums2, nums1);
    }
    
    std::unordered_map<int, int> counter;
    for (int num : nums1) counter[num]++;
    
    std::vector<int> result;
    for (int num : nums2) {
        if (counter.count(num)) {
            result.push_back(num);
            if (--counter[num] == 0)
                counter.erase(num);
        }
    }
    return result;
}

4. 数组交集问题（排序+双指针法）

std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::sort(nums1.begin(), nums1.end());
    std::sort(nums2.begin(), nums2.end());
    
    int i = 0, j = 0;
    std::vector<int> result;
    
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            result.push_back(nums1[i]);
            i++, j++;
        }
    }
    return result;
}

5. 快乐数判断

class HappyNumberChecker {
public:
    bool isHappy(int n) {
        std::unordered_set<int> seen;
        while (true) {
            int sum = digitSquareSum(n);
            if (sum == 1) return true;
            if (seen.find(sum) != seen.end()) return false;
            seen.insert(sum);
            n = sum;
        }
    }

private:
    int digitSquareSum(int num) {
        int total = 0;
        while (num > 0) {
            int digit = num % 10;
            total += digit * digit;
            num /= 10;
        }
        return total;
    }
};

注意：strlen函数的时间复杂度为O(n)，应避免在循环条件中反复调用。