logo标签列表

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

c++calgorithmpseudocoderabin-karp
8
我正在寻找一种高效的哈希函数用于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哈希函数应该具备哪些特性？

3
你已经看过这个链接了吗？我可以给你翻译一下。 - Gigi
1
Rabin-Karp 不能使用任何哈希函数，它需要一种专门的哈希函数，可以快速地从已知位置 (i-1) 的值计算出位置 i 的哈希值。 - rossum
是的，@Gigi，我有。但是如果有一个更好的哈希函数，那就完美了（因为我将多次运行这个函数）。@rossum：根据维基百科的文章，我进行了一次“重新哈希”函数。 - md5
1
你读过这个答案吗？ - zenpoy
@md5，可能是md5，不管怎样只是个玩笑 :) - nurgasemetey
4个回答
10

一个非常高效的哈希算法是Bernstein哈希。它甚至比许多流行的哈希算法运行得更快。

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哈希算法比较

1
在算术运算中，“unsigned”溢出了，这样可以吗？ - Pupsik
@Pupsik 溢出通常不是问题，所以我会说是的。 - devoured elysium
6
为什么这个回答被接受并得到高票数？它的时间复杂度是O（p）。如果对主文本的每个窗口都调用它，模式搜索函数的时间复杂度将为O（p*t），与暴力方法相同。问题涉及适用于Rabin Karp算法的哈希函数，而该函数并不适用。 - Saptarshi Basu
7
拉宾-卡普算法涉及使用滚动哈希函数。滚动哈希函数具有特殊属性：如果我们已经知道H(c[0..n])的值，例如，我们可以快速地计算出H(c[1..n+1])。这是滚动哈希函数的特性，伯恩斯坦哈希没有这个特性！我认为我们应该对这个答案进行反对投票！ - Kirill Frolov
我不确定为什么有评论声称这个哈希函数不能有效地滚动。它等价于（模sizeof(unsigned)）基于33进制的字符串的伪表示。如果您的窗口长度为k，则可以通过将哈希减去pow(33, k-1)*str[i-k]来“删除”哈希中的str[i-k]。即要滚动哈希一次，您可以执行hash = 33 * (hash - pow(33, k-1) * str[i-k]) + str[i]。 - Navneeth
2
Rabin-Karp哈希函数应具备哪些特点？
Rabin-Karp需要一个滚动哈希。最简单的滚动哈希是移动总和。Adler-32和Buzhash也很简单，比移动总和表现更好。
这些任何一种滚动哈希技术都适用于Rabin-Karp：
  • 移动和
    • 通过减法来删除最旧的字节
    • 通过加法来添加新的字节
  • 多项式滚动哈希
    • 通过减法来删除最旧的字节
    • 通过乘法和加法来添加新的字节
  • Rabin指纹
    • 一个在 GF(2) 上是不可约的多项式滚动哈希
  • 表哈希
    • 通过表查找和 xor 来删除最旧的字节
    • 通过表查找和 xor 来添加新的字节
  • 循环多项式, 又称为Buzhash
    • 基于循环移位的表哈希
  • Adler-32校验和
    • 默认情况下不是滚动和，但可以轻松调整为 "滚动"
    • 通过两次减法来删除最旧的字节
    • 通过两次加法来添加新的字节
0

对于小字母问题，例如核酸序列搜索（例如alphabet = {A，T，C，G，U}），nt-Hash 可能是一个很好的哈希函数。它使用二进制操作，速度更快，并且具有滚动哈希更新，同时还提供均匀分布的哈希值。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接