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

Question

我正在为Rabin-Carp算法寻找一个高效的哈希函数。这是我的实际代码（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-CarpC实现，但所有代码之间都存在差异。所以我的问题是：Rabin-Carp散列函数应该具有什么特性？

Answer 1

一个性能非常好的哈希是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比较

Rabin-Carp散列函数应该具有哪些特性？

拉宾·卡普需要一个滚动散列。最简单的滚动散列是移动和。Adler-32和Buzhash也很简单，表现比移动总和更好。

这些滚动散列技术中的任何一种都应该适用于Rabin Karp:

• 移动总和
  • 用减法删除最旧的字节
  • 通过加法添加新字节
• 多项式滚动散列
  • 用减法删除最旧的字节
  • 用乘法和加法加一个新字节
• 拉宾指纹
  • 一个多项式在GF（2）上不可约的多项式滚动散列
• 制表哈希
  • 使用表查找和xor删除最旧的字节
  • 使用表查找和xor添加新字节
• 循环多项式，又名Buzhash
  • 基于循环移位的制表散列
• Adler-32校验和
  • 默认情况下不是滚动校验和，但很容易调整为"0"；滚动"
  • 用两个减法删除最旧的字节
  • 添加两个新字节

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

考虑到Java JDK的实现者会有一些想法，我查找了那里使用的函数。

从Java 19开始，https://github.com/openjdk/jdk/blob/jdk-19+23/src/java.base/share/classes/java/lang/String.java#L2326

更新功能为：

h' = 31 * h + c

初始值为0。