c - 在 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 */

请记住，性能并不是哈希函数的唯一相关特征。获得整个 key 空间的平均分配非常重要。我无法告诉您 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;
}

尽管这个简单的函数可能更快。这是一个权衡，一个“聪明”的散列算法试图尽可能快，同时仍然提供良好的分布。上面的简单函数并没有真正提供良好的分布，例如它永远不会将整个 key 空间用于小输入(小于 5 个字节)。