ToB企服应用市场:ToB评测及商务社交产业平台

标题: murmur 算法 [打印本页]
作者: 拉不拉稀肚拉稀    时间: 2024-9-22 07:05
标题: murmur 算法
简介

MurmurHash是一种高效的非加密哈希函数，实用于哈希表中的一般哈希任务。
MurmurHash的名称来源于Murmur，意为一种低频的声音，体现了其设计的低碰撞率和高性能。
名称来自两个根本操作，乘法（MU）和旋转（R），在其内部循环中使用。与其它盛行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特性表现更精良。
MurmurHash与加密散列函数不同，它不是专门设计为难以被对手逆转，因此不实用于加密目的。它常被应用于分布式系统，许多开源项目如Kafka、Redis，Memcached，Cassandra，HBase，Elasticsearch等等都使用它。
MurmurHash的当前的版本是MurmurHash3，可以或许产生出32-bit或128-bit哈希值。
优点和缺点

速度快，比安全散列算法快几十倍；
厘革足够猛烈，相似的字符串如“abc”和“abd”可以或许均匀散落在哈希环上；
高熵：确保输入的微小厘革会显著改变输出，减少碰撞。
高性能：利用简朴的位操作和混淆步骤，实用于现代处理器。
确定性：相同的输入总是生成相同的输出。
不包管安全性（缺点）
算法原理

以MurmurHash3_x86_32为例，它实用于32位系统，并输出32位的哈希值。下面是MurmurHash3的主要步骤：
初始化

设置一个种子（seed）值，用于初始化哈希值。这样可以通过不同的种子来生成不同的哈希值。
处理块（chunks）

输入数据被分成固定大小的块（通常为4 bytes）。每个块使用一次哈希函数。
对于每个块，起首将它们视为32位整数。
混淆过程：

对每个32位块进行一系列位操作，包罗乘法、左移和右移。这些操作用来混淆位，使得输入的不同位对终极哈希值有较大的影响。
具体的混淆步骤如下：
  1. k *= c1;
  2. k = rotl32(k, r1);
  3. k *= c2;
  4. h ^= k;
  5. h = rotl32(h, r2);
  6. h = h * m + n;
复制代码
c1, c2, r1, r2, m, n是固定的常数，通过实验选择，使得哈希函数具有精良的分布性和随机性。
处理尾部（tail）

假如输入数据的长度不是块大小的倍数，剩余的未处理字节（称为尾部）也会影响终极哈希值。
对尾部的字节进行雷同的混淆处理，但处理量要少得多
终极化（finalization）

  1. h ^= h >> 16;
  2. h *= 0x85ebca6b;
  3. h ^= h >> 13;
  4. h *= 0xc2b2ae35;
  5. h ^= h >> 16;
复制代码
Demo

  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <string.h>
  5. #define ROTL32(x, r) ((x << r) | (x >> (32 - r)))
  7. uint32_t MurmurHash3_x86_32(const void *key, int len, uint32_t seed) {
  8.     const uint8_t *data = (const uint8_t *)key;
  9.     const int nblocks = len / 4;
  10.     uint32_t h1 = seed;
  11.    
  12.     const uint32_t c1 = 0xcc9e2d51;
  13.     const uint32_t c2 = 0x1b873593;
  15.     // Body
  16.     const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
  17.     for (int i = -nblocks; i; i++) {
  18.         uint32_t k1 = blocks[i];
  20.         k1 *= c1;
  21.         k1 = ROTL32(k1, 15);
  22.         k1 *= c2;
  24.         h1 ^= k1;
  25.         h1 = ROTL32(h1, 13);
  26.         h1 = h1 * 5 + 0xe6546b64;
  27.     }
  29.     // Tail
  30.     const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
  31.     uint32_t k1 = 0;
  33.     switch (len & 3) {
  34.     case 3:
  35.         k1 ^= tail[2] << 16;
  36.     case 2:
  37.         k1 ^= tail[1] << 8;
  38.     case 1:
  39.         k1 ^= tail[0];
  40.         k1 *= c1;
  41.         k1 = ROTL32(k1, 15);
  42.         k1 *= c2;
  43.         h1 ^= k1;
  44.     }
  46.     // Finalization
  47.     h1 ^= len;
  48.     h1 ^= h1 >> 16;
  49.     h1 *= 0x85ebca6b;
  50.     h1 ^= h1 >> 13;
  51.     h1 *= 0xc2b2ae35;
  52.     h1 ^= h1 >> 16;
  54.     return h1;
  55. }
  57. int main() {
  58.     const char *key = "Hello, World!";
  59.     uint32_t seed = 42;  // A random seed value
  60.     uint32_t hash = MurmurHash3_x86_32(key, strlen(key), seed);
  62.     printf("Hash of '%s' with seed %u is: %u\n", key, seed, hash);
  63.         /* Hash of 'Hello, World!' with seed 42 is: 1794106050 */
  64.     return 0;
  65. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4