在 C 中使用 Murmurhash

Question

我正在用 C 实现哈希表和哈希函数，并听说 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，那么这是否是我在上述函数中作为“长度”传递的值？参数“种子”，我认为这可以是任何任意值，只要它在哈希调用之间保持不变即可？考虑到我在 32 位计算机上工作，是否还需要更改任何其他参数？

我认为我还需要根据哈希表的大小对返回哈希取模？

此外，如果有人可以推荐一个用于字符串的更好/更快的替代哈希函数，那么我们将不胜感激

提前致谢

Answer 1

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

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

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

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

然后请记住，性能并不是哈希函数的唯一相关特征。获得整个密钥空间的均匀分布非常重要。我无法告诉你murmurhash在这方面有多“好”，但可能比我最近使用的一个非常简单的哈希要好得多：

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 字节）。