如何快速计算大型double类型向量的哈希值？

首先明确：哈希计算本质上需要读取所有数据，不存在完全无需遍历内存块的方法，但可以通过更高效的实现大幅降低耗时，达到1ms以内的目标。以下是针对你的限制（无优化编译、C++11及更早）的具体方案：

1. 换用针对连续内存优化的哈希算法 #

boost::hash_combine逐个元素处理的方式开销极大——每个元素都要执行移位、异或操作，且循环的函数调用/分支在无优化编译下会放大耗时。推荐使用MurmurHash3这类专为连续内存设计的哈希算法，它可以直接处理整块内存，利用CPU的批量读写能力，即使无优化也能显著提速。

代码实现示例 #

先实现MurmurHash3的64位版本（兼容C++11）：

#include <cstdint>

// MurmurHash3 x64 64位输出实现（兼容C++11）
void MurmurHash3_x64_64(const void* key, size_t len, uint32_t seed, uint64_t* out) {
    const uint64_t c1 = 0x87c37b91114253d5ULL;
    const uint64_t c2 = 0x4cf5ad432745937fULL;

    const uint64_t* blocks = reinterpret_cast<const uint64_t*>(key);
    size_t num_blocks = len / 8;

    uint64_t h1 = seed;

    for (size_t i = 0; i < num_blocks; ++i) {
        uint64_t k1 = blocks[i];

        k1 *= c1;
        k1 = (k1 << 31) | (k1 >> (64 - 31));
        k1 *= c2;

        h1 ^= k1;
        h1 = (h1 << 27) | (h1 >> (64 - 27));
        h1 = h1 * 5 + 0x52dce729;
    }

    const uint8_t* tail = reinterpret_cast<const uint8_t*>(key + num_blocks * 8);
    uint64_t k1 = 0;

    switch (len & 7) {
        case 7: k1 ^= static_cast<uint64_t>(tail[6]) << 48;
        case 6: k1 ^= static_cast<uint64_t>(tail[5]) << 40;
        case 5: k1 ^= static_cast<uint64_t>(tail[4]) << 32;
        case 4: k1 ^= static_cast<uint64_t>(tail[3]) << 24;
        case 3: k1 ^= static_cast<uint64_t>(tail[2]) << 16;
        case 2: k1 ^= static_cast<uint64_t>(tail[1]) << 8;
        case 1: k1 ^= static_cast<uint64_t>(tail[0]);
                k1 *= c1;
                k1 = (k1 << 31) | (k1 >> (64 - 31));
                k1 *= c2;
                h1 ^= k1;
    }

    h1 ^= len;
    h1 ^= h1 >> 33;
    h1 *= 0xff51afd7ed558ccdULL;
    h1 ^= h1 >> 33;
    h1 *= 0xc4ceb9fe1a85ec53ULL;
    h1 ^= h1 >> 33;

    *out = h1;
}

然后替换原代码中的哈希计算部分：

uint64_t hashValMurmur(0);
uint64_t startTime_us = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
// 直接处理整个向量的连续内存块
MurmurHash3_x64_64(myContainer.data(), myContainer.size() * sizeof(double), 0, &hashValMurmur);
uint64_t endTime_us = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();

cout << "ContainerSize = " << myContainer.size() <<"; MurmurHash = " << hashValMurmur << ", TimeToComputeHash(ms) = " << (endTime_us - startTime_us)/1000.0 << "ms" << std::endl;

2. 关键优化点说明 #

• 批量内存处理：直接把vector的底层连续内存作为字节流传入哈希函数，避免了逐个元素循环的开销。
• 低分支算法：MurmurHash3的分支极少，在无优化编译下不会因分支预测失败产生额外耗时。
• 无函数调用开销：哈希函数内部的循环比外部逐个调用hash_combine的开销小得多，尤其是无优化编译时。

3. 注意事项 #

• 若需跨平台哈希一致性，需注意double的字节序问题；仅在同一机器使用时可忽略此问题。
• 可以调整哈希种子（示例中为0）来满足不同的哈希冲突规避需求。

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