C++怎么实现一个MurmurHash算法_C++非加密哈希函数与性能分析-C++-PHP中文网

C++怎么实现一个MurmurHash算法_C++非加密哈希函数与性能分析

尼克

发布： 2025-12-04 10:27:07

原创

364人浏览过

MurmurHash3 是高性能非加密哈希函数，适用于 C++ 中哈希表等场景，具有优良分布性与运算速度。

c++怎么实现一个murmurhash算法_c++非加密哈希函数与性能分析

要实现一个高效的非加密哈希函数，MurmurHash 是广泛使用的选择之一，尤其在 C++ 高性能场景中（如哈希表、布隆过滤器等）表现优异。它由 Austin Appleby 在 2008 年提出，具有良好的分布性与极快的运算速度。下面介绍如何在 C++ 中实现 MurmurHash3 的核心算法，并简要分析其性能特点。

MurmurHash3 算法原理

MurmurHash3 是 MurmurHash 系列中最成熟的一个版本，支持 32 位和 128 位输出。它采用混合乘法、异或和移位操作来打乱输入数据的比特分布，核心思想是：

将输入数据按固定字节大小（通常是 4 字节或 16 字节）分块处理
每一块通过一系列“mix”操作更新哈希状态
剩余不足块大小的数据单独处理
最后进行一次终态混合（fmix）以增强雪崩效应

该算法不用于加密安全场景，但对普通哈希用途（如 unordered_map）非常高效。

C++ 实现 MurmurHash3_32

以下是一个简洁的 MurmurHash3 32 位版本实现，适用于任意长度的字节数组：

立即学习“C++免费学习笔记（深入）”；

#include <cstdint>
#include <cstddef>
<p>// 常量定义
static constexpr uint32_t MURMUR_SEED = 0xc70f6907; // 可自定义种子
static constexpr uint32_t c1 = 0xcc9e2d51;
static constexpr uint32_t c2 = 0x1b873593;</p><p>uint32_t murmur3_32(const uint8_t* key, size_t len) {
uint32_t h = MURMUR_SEED;
uint32_t k;</p><pre class='brush:php;toolbar:false;'>const uint8_t* tail;
const uint32_t* blocks = reinterpret_cast<const uint32_t*>(key);

// 处理完整的 4 字节块
for (size_t i = len / 4; i != 0; i--) {
    k = *blocks++;
    k *= c1;
    k = (k << 15) | (k >> 17);
    k *= c2;

    h ^= k;
    h = (h << 13) | (h >> 19);
    h = h * 5 + 0xe6546b64;
}

// 处理剩余字节（0~3 字节）
tail = reinterpret_cast<const uint8_t*>(blocks);
k = 0;
switch (len & 3) {
    case 3: k ^= tail[2] << 16;
    case 2: k ^= tail[1] << 8;
    case 1: k ^= tail[0];
            k *= c1;
            k = (k << 15) | (k >> 17);
            k *= c2;
            h ^= k;
};

// 终态混合
h ^= len;
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;

return h;

登录后复制

}

这个实现可以直接用于字符串或内存块：

阿贝智能

阿贝智能是基于AI技术辅助创作儿童绘本、睡前故事和有声书的平台，助你创意实现、梦想成真。

查看详情

#include <iostream>
#include <string>
<p>int main() {
std::string str = "hello world";
uint32_t hash = murmur3_32(
reinterpret_cast<const uint8_t*>(str.data()),
str.size()
);
std::cout << "Hash: " << hash << "\n";
return 0;
}</p>

登录后复制