如何为最长4位小写英文字符串生成唯一哈希存入STL unordered_map

架构老林

2026-10-1

回答

结论

完全可以实现无碰撞的唯一哈希，这类字符串的总数量非常有限，仅不到50万，很容易构造完美哈希函数。

总量计算

先统计所有符合要求的字符串总数，确认可以用单个整数覆盖全量唯一编码：

长度为1的小写字母串：26个
长度为2的小写字母串：26² = 676个
长度为3的小写字母串：26³ = 17576个
长度为4的小写字母串：26⁴ = 456976个
总数量：26 + 676 + 17576 + 456976 = 475254个，远小于32位整数的最大值，完全可以用单个整数唯一表示所有符合要求的字符串。

哈希函数实现思路

你可以用带长度前缀的26进制编码逻辑实现无碰撞哈希，核心是先区分不同长度的字符串，再对字符串内容做编码，避免不同长度的字符串出现哈希冲突：

先统计所有长度小于当前字符串的串的总数，作为偏移量：
- 长度1：偏移量为0
- 长度2：偏移量为26
- 长度3：偏移量为26 + 26² = 702
- 长度4：偏移量为26 + 26² + 26³ = 18278
把当前字符串的每一位字符按c - 'a'转成0~25的数值，按顺序拼接为26进制数
最终哈希值 = 偏移量 + 26进制编码的数值

C++ 适配unordered_map的代码示例

#include <unordered_map>
#include <string>

struct ShortStrHash {
    size_t operator()(const std::string& s) const {
        // 提前预计算的各长度偏移量
        const size_t offset[] = {0, 0, 26, 702, 18278};
        size_t len = s.size();
        size_t hash = offset[len];
        size_t base = 1;
        for (int i = len - 1; i >= 0; --i) {
            hash += (s[i] - 'a') * base;
            base *= 26;
        }
        return hash;
    }
};

// 自定义哈希的unordered_map声明方式
std::unordered_map<std::string, int, ShortStrHash> str_map;