实现编译时字符串哈希 ​

面试考点 ​

编译时字符串哈希是 constexpr 编程的经典应用。面试官考察你是否理解 constexpr 函数的递归写法、FNV-1a 哈希算法、用户定义字面量(user-defined literal),以及编译时哈希在 switch-case 字符串匹配中的实际应用。

核心概念 ​

C++ 的 switch 语句只能匹配整数和枚举,不能直接匹配字符串。编译时字符串哈希把字符串在编译期转换为整数,使得 switch-case 可以间接匹配字符串。FNV-1a 是一种简单且分布均匀的哈希算法,其递归形式天然适合 constexpr 实现。

基本示例 ​

cpp
#include <iostream>
#include <string>
#include <cstdint>
#include <string_view>
#include <array>

// ============================
// FNV-1a 编译时哈希(32位)
// ============================

// FNV-1a 算法参数(32位版本)
constexpr uint32_t fnv1a_basis_32 = 0x811c9dc5u;
constexpr uint32_t fnv1a_prime_32 = 0x01000193u;

// 编译时字符串哈希(递归实现)
// C++11 风格:constexpr 函数只能有一条 return 语句
constexpr uint32_t hash32(const char* str, uint32_t hash = fnv1a_basis_32) {
    // 遇到字符串结束符返回哈希值
    // 否则:hash = (hash ^ 当前字符) * 质数,递归处理下一个字符
    return (*str == '\0')
        ? hash
        : hash32(str + 1, (hash ^ static_cast<uint32_t>(*str)) * fnv1a_prime_32);
}

// ============================
// FNV-1a 编译时哈希(64位)
// ============================

constexpr uint64_t fnv1a_basis_64 = 0xcbf29ce484222325ull;
constexpr uint64_t fnv1a_prime_64 = 0x100000001b3ull;

constexpr uint64_t hash64(const char* str, uint64_t hash = fnv1a_basis_64) {
    return (*str == '\0')
        ? hash
        : hash64(str + 1, (hash ^ static_cast<uint64_t>(*str)) * fnv1a_prime_64);
}

// ============================
// C++17 风格:循环实现
// ============================

// C++17 放宽了 constexpr 的限制,可以用循环
constexpr uint32_t hash32_loop(const char* str) {
    uint32_t hash = fnv1a_basis_32;
    while (*str != '\0') {
        hash ^= static_cast<uint32_t>(*str);
        hash *= fnv1a_prime_32;
        str++;
    }
    return hash;
}

// 支持 string_view(已知长度,不依赖空终止符)
constexpr uint32_t hash32_sv(std::string_view sv) {
    uint32_t hash = fnv1a_basis_32;
    for (char c : sv) {
        hash ^= static_cast<uint32_t>(c);
        hash *= fnv1a_prime_32;
    }
    return hash;
}

// ============================
// 用户定义字面量
// ============================

// 允许写 "hello"_hash 代替 hash32("hello")
constexpr uint32_t operator""_hash(const char* str, size_t) {
    return hash32(str);
}

constexpr uint64_t operator""_hash64(const char* str, size_t) {
    return hash64(str);
}

// ============================
// 运行时哈希(与编译时结果一致)
// ============================

// 用于运行时字符串(如用户输入、动态字符串)
uint32_t hash32_runtime(const char* str) {
    uint32_t hash = fnv1a_basis_32;
    while (*str != '\0') {
        hash ^= static_cast<uint32_t>(*str);
        hash *= fnv1a_prime_32;
        str++;
    }
    return hash;
}

uint32_t hash32_runtime(const std::string& str) {
    return hash32_runtime(str.c_str());
}

// ============================
// 应用:switch-case 字符串匹配
// ============================

void handle_command(const std::string& cmd) {
    // 运行时计算输入字符串的哈希
    // case 分支中的哈希在编译期计算
    switch (hash32_runtime(cmd)) {
        case "help"_hash:
            std::cout << "显示帮助信息" << std::endl;
            break;
        case "quit"_hash:
        case "exit"_hash:
            std::cout << "退出程序" << std::endl;
            break;
        case "version"_hash:
            std::cout << "版本 1.0.0" << std::endl;
            break;
        case "status"_hash:
            std::cout << "状态正常" << std::endl;
            break;
        default:
            std::cout << "未知命令: " << cmd << std::endl;
            break;
    }
}

// ============================
// 编译期验证
// ============================

// static_assert 验证编译期求值
static_assert(hash32("hello") == hash32_loop("hello"),
              "递归和循环实现结果应该一致");

static_assert(hash32("hello") != hash32("world"),
              "不同字符串应该产生不同哈希");

static_assert(hash32("") == fnv1a_basis_32,
              "空字符串的哈希应该是初始值");

// 编译期常量
constexpr auto hello_hash = hash32("hello");
constexpr auto world_hash = hash32("world");

// ============================
// 应用:编译时字符串表查找
// ============================

// 编译时构建哈希→值的映射
struct HashEntry {
    uint32_t hash;
    const char* key;
    int value;
};

constexpr std::array<HashEntry, 4> color_table = {{
    {hash32("red"),   "red",   0xFF0000},
    {hash32("green"), "green", 0x00FF00},
    {hash32("blue"),  "blue",  0x0000FF},
    {hash32("white"), "white", 0xFFFFFF},
}};

// 编译时查找
constexpr int lookup_color(const char* name) {
    uint32_t h = hash32(name);
    for (const auto& entry : color_table) {
        if (entry.hash == h) {
            return entry.value;
        }
    }
    return -1;  // 未找到
}

// 编译期验证
static_assert(lookup_color("red") == 0xFF0000, "红色查找");
static_assert(lookup_color("blue") == 0x0000FF, "蓝色查找");
static_assert(lookup_color("unknown") == -1, "未知颜色");

// ============================
// 应用:类型字符串映射
// ============================

enum class TypeId { Unknown, Int, Float, String, Bool };

constexpr TypeId parse_type(const char* name) {
    switch (hash32(name)) {
        case hash32("int"):    return TypeId::Int;
        case hash32("float"):  return TypeId::Float;
        case hash32("string"): return TypeId::String;
        case hash32("bool"):   return TypeId::Bool;
        default:               return TypeId::Unknown;
    }
}

static_assert(parse_type("int") == TypeId::Int, "");
static_assert(parse_type("string") == TypeId::String, "");

// ============================
// 测试
// ============================

void test_basic() {
    std::cout << "--- 基本哈希 ---" << std::endl;
    std::cout << "hash32(\"hello\"): " << hash32("hello") << std::endl;
    std::cout << "hash32(\"world\"): " << hash32("world") << std::endl;
    std::cout << "hash64(\"hello\"): " << hash64("hello") << std::endl;

    // 用户定义字面量
    std::cout << "\"hello\"_hash: " << "hello"_hash << std::endl;
    std::cout << "\"hello\"_hash64: " << "hello"_hash64 << std::endl;

    // 编译期常量
    std::cout << "hello_hash (编译期): " << hello_hash << std::endl;
}

void test_switch() {
    std::cout << "\n--- switch-case 字符串匹配 ---" << std::endl;
    handle_command("help");
    handle_command("version");
    handle_command("quit");
    handle_command("foo");
}

void test_color_lookup() {
    std::cout << "\n--- 颜色查找 ---" << std::endl;
    // 运行时查找
    std::string color = "green";
    switch (hash32_runtime(color)) {
        case "red"_hash:   std::cout << "红色" << std::endl; break;
        case "green"_hash: std::cout << "绿色" << std::endl; break;
        case "blue"_hash:  std::cout << "蓝色" << std::endl; break;
        default:           std::cout << "未知颜色" << std::endl; break;
    }
}

int main() {
    test_basic();
    test_switch();
    test_color_lookup();
    return 0;
}

FNV-1a 算法步骤 ​

步骤操作说明
初始化hash = offset_basis32位: 0x811c9dc5, 64位: 0xcbf29ce484222325
异或hash = hash XOR byte混入当前字节
乘法hash = hash * prime32位: 0x01000193, 64位: 0x100000001b3
循环对每个字节重复直到字符串结束

C++11 vs C++17 的 constexpr 差异 ​

特性C++11 constexprC++17 constexpr
函数体只能有一条 return可以有循环、条件、变量
实现方式递归循环(更直观)
递归深度限制标准最少 512 层同样限制,但可以用循环避免
string_view不可用可用

常见问题 ​

哈希碰撞怎么办?

两个不同字符串可能产生相同的哈希值。在 switch-case 中,如果碰撞发生会导致错误匹配。解决方案:1) 在 case 分支中加字符串相等性检查作为第二重验证;2) 使用 64 位哈希减少碰撞概率;3) 在编译期用 static_assert 检测已知字符串集合中是否有碰撞。

为什么选择 FNV-1a?

FNV-1a 算法简单(只用异或和乘法),分布均匀,递归形式天然适合 constexpr。它不是密码学安全的哈希,但对于字符串匹配来说足够了。其他选择还有 CRC32、DJB2 等。

用户定义字面量有什么限制?

字面量运算符必须以下划线开头(不带下划线的保留给标准库)。参数类型是 const char* 和 size_t(字符串字面量)。它只能用于字面量,不能用于运行时字符串变量。

适用场景 ​

  • switch-case 匹配字符串(命令解析、协议处理)
  • 编译期字符串表查找
  • 消息/事件分发系统
  • 配置项解析

注意事项 ​

  • 编译时哈希和运行时哈希必须使用相同的算法和参数
  • 哈希碰撞虽然概率低但存在,关键场景需要加相等性检查
  • constexpr 递归有深度限制,超长字符串可能编译失败
  • 用户定义字面量运算符名必须以下划线开头
  • 64 位哈希比 32 位碰撞概率低很多,推荐优先使用

总结 ​

编译时字符串哈希用 constexpr 函数在编译期把字符串转为整数,配合用户定义字面量实现 switch-case 字符串匹配。FNV-1a 算法只用异或和乘法,递归形式天然适合 constexpr。面试中要能手写 FNV-1a 的 constexpr 实现,解释用户定义字面量的语法,演示 switch-case 的用法,以及讨论哈希碰撞的风险和应对策略。