7

我正在为 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 哈希函数应该具有哪些特征？

4

2 回答 2

9

一个性能非常好的散列是伯恩斯坦散列。它甚至超过了许多流行的散列算法。

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 比较

于 2012-07-18T17:55:00.357 回答
0

对于小字母的问题，例如核酸序列搜索（例如alphabet = {A, T, C, G, U}），nt-Hash可能是一个很好的散列函数。它使用更快的二元运算和滚动散列更新，并且它还给出了均匀分布的散列值。

于 2020-10-09T14:46:04.177 回答