在C语言中使用Murmurhash

Question

在C语言中使用Murmurhash

5

我正在实现一个哈希表以及相应的哈希函数，并听说 Murmurhash 是一个适用于此目的的快速算法。查阅一些 C 语言代码后，找到了以下内容：

uint32_t murmur3_32(const char *key, uint32_t len, uint32_t seed) {
    static const uint32_t c1 = 0xcc9e2d51;
    static const uint32_t c2 = 0x1b873593;
    static const uint32_t r1 = 15;
    static const uint32_t r2 = 13;
    static const uint32_t m = 5;
    static const uint32_t n = 0xe6546b64;

    uint32_t hash = seed;

    const int nblocks = len / 4;
    const uint32_t *blocks = (const uint32_t *) key;
    int i;
    for (i = 0; i < nblocks; i++) {
        uint32_t k = blocks[i];
        k *= c1;
        k = (k << r1) | (k >> (32 - r1));
        k *= c2;

        hash ^= k;
        hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
    }

    const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);
    uint32_t k1 = 0;

    switch (len & 3) {
    case 3:
        k1 ^= tail[2] << 16;
    case 2:
        k1 ^= tail[1] << 8;
    case 1:
        k1 ^= tail[0];

        k1 *= c1;
        k1 = (k1 << r1) | (k1 >> (32 - r1));
        k1 *= c2;
        hash ^= k1;
    }

    hash ^= len;
    hash ^= (hash >> 16);
    hash *= 0x85ebca6b;
    hash ^= (hash >> 13);
    hash *= 0xc2b2ae35;
    hash ^= (hash >> 16);

    return hash;
}

我想澄清一些关于这里传递的参数的问题。"Key" 显然是您要哈希的字符串。如果在结构体中定义为具有 46 个数组长度，那么这是否是我将作为上述函数中的 "length" 传递的值？参数 "seed"，我认为它可以是任意的值，只要在哈希调用之间保持恒定即可？还有其他参数需要更改吗？考虑到我正在使用 32 位机器。

我认为我还需要通过我的哈希表的大小对返回的哈希进行模运算？

此外，如果有人可以推荐一种更优秀/更快速的用于字符串的替代哈希函数，那将不胜感激。

提前致谢。

- Mathias

是的（但使用 sizeof 以避免错误）。是的。可能不是。是的。 - user253751

1

const uint32_t *blocks = (const uint32_t *) key; 这假设key对齐足够以转换为32位指针。对于char指针，这不能保证。 - wildplasser

@wildplasser 架构相关，在 x86 上没有问题，据我所知...但是提出的很好。 - user2371524

至少会有性能损失（并且这是相关的，因为原帖过于关注性能）。未对齐的总线访问可能很昂贵，可能足以抵消在32位块上操作的收益。 - wildplasser

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user2371524 · Accepted Answer

关于参数的问题：是的，只需要阅读代码，你的假设是正确的。

只要哈希表的大小是2的幂次方，就不需要取模。然后你可以使用位掩码，例如（伪代码）：

void* hashtbl[1<<8]; /* 256 */

int key = hash(value, ...) & ((1<<8) - 1); /* 0xff */

请注意，性能不是哈希函数的唯一相关特征。非常重要的是获得整个键空间的均等分布。我无法告诉您在这方面有多好，但可能比我最近为了玩耍而使用的非常简单的哈希函数要好得多：

static unsigned int
hash(const void *key, size_t keyLen, unsigned int hashmask)
{
    size_t i;
    unsigned int h = 5381;

    for (i=0; i<keyLen; ++i)
    {
        h += (h << 5) + ((const unsigned char *)key)[i];
    }

    return h & hashmask;
}

虽然这个简单的函数可能更快，但这是一个权衡，而“聪明”的哈希算法试图在保持良好分布的同时尽可能快。上面的简单函数实际上并没有给出良好的分布，例如对于小输入（少于5个字节），它永远不会使用整个键空间。