如何在C++中构建完美哈希（Perfect Hash）？

需求特性 #

• 完全无碰撞：所有固定输入值的哈希结果互不相同
• 仅适配固定值集：针对预先确定的N个值构建，不支持动态添加新值
• 映射范围：将N个值映射到0 .. N * 1.23 - 1的整数区间（即总空间为N的1.23倍，而非严格的N个位置）

核心实现思路 #

采用两级哈希策略构建无碰撞的完美哈希：

1. 第一级哈希：将输入值映射到总空间（大小为N*1.23）的分组中，通过随机生成哈希参数，确保每个分组内的元素数量足够少，便于第二级哈希处理。
2. 第二级哈希：为每个非空分组单独生成哈希函数，将分组内的元素映射到该分组对应的连续子区间内，保证分组内无碰撞，最终所有元素的哈希值均落在目标范围内且唯一。

C++ 完整实现代码 #

#include <vector>
#include <cstdint>
#include <random>
#include <unordered_map>
#include <unordered_set>

// 通用哈希函数结构体，支持自定义参数
struct HashFunc {
    uint64_t multiplier;
    uint64_t offset;
    uint64_t modulus;

    uint64_t operator()(uint64_t key) const {
        return ((multiplier * key + offset) % modulus);
    }
};

class PerfectHash {
private:
    HashFunc first_hash_;
    std::vector<std::unordered_map<uint64_t, uint64_t>> group_hash_map_;
    size_t total_space_;

public:
    // 构造函数：输入固定值集合，完成完美哈希构建
    explicit PerfectHash(const std::vector<uint64_t>& keys) {
        const size_t N = keys.size();
        total_space_ = static_cast<size_t>(N * 1.23);
        if (total_space_ < N) total_space_ = N; // 确保总空间不小于元素数量

        std::mt19937_64 rng(std::random_device{}());
        std::uniform_int_distribution<uint64_t> dist_multi(1, UINT64_MAX);
        std::uniform_int_distribution<uint64_t> dist_offset(0, UINT64_MAX);

        // 寻找有效的第一级哈希函数，确保分组大小满足第二级哈希的无碰撞要求
        bool valid_first_hash = false;
        while (!valid_first_hash) {
            first_hash_ = {dist_multi(rng), dist_offset(rng), total_space_};
            std::vector<std::vector<uint64_t>> groups(total_space_);

            // 将所有键分配到对应分组
            for (uint64_t key : keys) {
                const uint64_t group_idx = first_hash_(key);
                groups[group_idx].push_back(key);
            }

            // 检查每个分组的大小：分组大小k的平方不超过总空间，确保第二级哈希能找到无碰撞参数
            valid_first_hash = true;
            for (const auto& group : groups) {
                const size_t k = group.size();
                if (k * k > total_space_) {
                    valid_first_hash = false;
                    break;
                }
            }

            if (valid_first_hash) {
                // 为每个分组构建第二级哈希映射
                group_hash_map_.resize(total_space_);
                for (size_t g_idx = 0; g_idx < groups.size(); ++g_idx) {
                    const auto& group = groups[g_idx];
                    if (group.empty()) continue;

                    const size_t k = group.size();
                    bool valid_second_hash = false;
                    while (!valid_second_hash) {
                        const HashFunc second_hash = {dist_multi(rng), dist_offset(rng), k};
                        std::unordered_set<uint64_t> used_positions;
                        std::unordered_map<uint64_t, uint64_t> key_to_pos;

                        valid_second_hash = true;
                        for (uint64_t key : group) {
                            const uint64_t sub_pos = second_hash(key);
                            const uint64_t final_pos = g_idx + sub_pos;

                            // 确保最终位置不超出总空间且未被占用
                            if (final_pos >= total_space_ || used_positions.count(final_pos)) {
                                valid_second_hash = false;
                                break;
                            }
                            used_positions.insert(final_pos);
                            key_to_pos[key] = final_pos;
                        }

                        if (valid_second_hash) {
                            group_hash_map_[g_idx] = std::move(key_to_pos);
                        }
                    }
                }
            }
        }
    }

    // 获取输入值的完美哈希值，不在固定集合中则返回UINT64_MAX
    uint64_t get_hash(uint64_t key) const {
        const uint64_t group_idx = first_hash_(key);
        const auto& pos_map = group_hash_map_[group_idx];
        auto it = pos_map.find(key);
        return (it != pos_map.end()) ? it->second : UINT64_MAX;
    }
};

// 示例用法
#include <iostream>
int main() {
    std::vector<uint64_t> test_keys = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000};
    PerfectHash ph(test_keys);

    for (uint64_t key : test_keys) {
        std::cout << "Key: " << key << ", Hash: " << ph.get_hash(key) << std::endl;
    }

    // 测试不在集合中的键
    std::cout << "Key: 1234, Hash: " << ph.get_hash(1234) << std::endl;
    return 0;
}

代码说明 #

1. 哈希函数设计：使用线性同余哈希公式 (multiplier * key + offset) % modulus，通过随机生成参数确保哈希的均匀性。
2. 第一级哈希校验：反复生成第一级哈希参数，直到所有分组的大小满足k² ≤ 总空间，保证第二级哈希能找到无碰撞的参数。
3. 第二级哈希映射：为每个分组生成独立的哈希函数，将分组内元素映射到分组起始位置后的连续子区间，确保最终哈希值唯一且落在目标范围内。
4. 查询效率：查询时通过第一级哈希定位分组，再通过分组内的映射表直接获取哈希值，时间复杂度为O(1)。

内容的提问来源于stack exchange，提问作者Arty