Rabin-Karp算法的最佳哈希函数是什么？

Question

我正在为Rabin-Karp算法寻找有效的哈希函数.这是我的实际代码(C编程语言).

static bool f2(char const *const s1, size_t const n1, 
               char const *const s2, size_t const n2)
{
    uintmax_t hsub = hash(s2, n2);
    uintmax_t hs   = hash(s1, n1);
    size_t   nmax = n2 - n1;

    for (size_t i = 0; i < nmax; ++i) {
        if (hs == hsub) {
            if (strncmp(&s1[i], s2, i + n2 - 1) == 0)
                return true;
        }
        hs = hash(&s1[i + 1], i + n2);
    }
    return false;
}

我考虑了一些Rabin-Karp C实现,但所有代码之间存在差异.所以我的问题是:Rabin-Karp哈希函数应该具有哪些特征？

Answer 1

伯恩斯坦哈希是一个表现极佳的哈希.它甚至超过了许多流行的哈希算法.

unsigned bernstein_hash ( void *key, int len )
{
    unsigned char *p = key;
    unsigned h = 0;
    int i;

    for ( i = 0; i < len; i++ )
        h = 33 * h + p[i];

    return h;
}

当然,您可以尝试其他哈希算法,如下所述: NIST上的哈希函数

注意:从来没有解释为什么33表现比任何其他"更多逻辑"常数更好.

为了您的兴趣:以下是不同哈希算法的良好比较:哈希算法的 strchr比较