C++如何将std::vector<uint64_t>映射为单个uint64_t值

基础可行性结论 #

• 若允许极小概率的冲突，该映射可以通过哈希函数实现。
• 若要求100%无冲突的映射，仅当std::vector<uint64_t>的所有可能取值总数不超过2^{64时才能实现：根据鸽巢原理，单`uint64_t`仅能表示2}64种不同值，而长度不固定的std::vector<uint64_t>的可能取值为无穷多，必然会出现冲突。

哈希方案实现 #

固定长度或可变长度的vector都可以用增量哈希组合的方式计算哈希值，C++环境下的极简实现如下：

#include <vector>
#include <functional>
#include <cstdint>

uint64_t vector_to_uint64(const std::vector<uint64_t>& v) {
    uint64_t hash_val = 0;
    for (uint64_t elem : v) {
        // 通用哈希组合逻辑，常规场景下冲突概率可忽略
        hash_val ^= std::hash<uint64_t>{}(elem) + 0x9e3779b9 + (hash_val << 6) + (hash_val >> 2);
    }
    return hash_val;
}

如果对冲突容忍度更低，可选用XXH3、CityHash等工业级64位哈希算法，十亿级样本量下冲突概率可低至可忽略的水平。

无冲突需求的替代方案 #

如果业务场景完全不允许出现冲突，可选择以下两种方案：

• 位拼接方案：如果vector的长度固定，且每个元素的取值范围都有严格上限，所有元素的总位宽之和不超过64位，可直接通过位运算拼接为单个uint64_t值。比如长度固定为3、第一个元素取值不超过2^{16、后两个元素取值各不超过2}24的场景，可直接把三个元素的二进制位按顺序拼接为64位值。
• 映射表方案：维护一个std::map或std::unordered_map存储唯一vector和自增uint64_t ID的对应关系，每遇到新的vector就分配一个新的ID，查询时先查表再返回ID。该方案可实现100%无冲突，缺点是需要额外存储映射表，且仅能在提前收集到所有vector、或可以动态新增映射的场景下使用。

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