Murmurhash在C中的使用

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

然后请记住，性能并不是散列函数的唯一相关特性。实现整个密钥空间的均匀分布是非常重要的。我不能告诉你在这方面“好”的杂音有多大，但可能比我在周围玩时使用的非常简单的散列要好得多：

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个字节)。