gpt4 book ai didi

c++ - Rabin-Karp 算法的最佳哈希函数是什么?

转载 作者:塔克拉玛干 更新时间:2023-11-03 01:20:12 27 4
gpt4 key购买 nike

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

最佳答案

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;
}

当然,您可以尝试其他哈希算法,如下所述: Hash function on NIST

注意:从未解释过为什么 33 的性能如此之好比任何其他“更多逻辑”常量。

为了您的兴趣:这是对不同哈希算法的一个很好的比较: strchr comparison of hash algorithms

关于c++ - Rabin-Karp 算法的最佳哈希函数是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11546791/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com