python - 我如何验证这个哈希函数不会给我两个不同的字符串相同的结果？

Question

考虑两个不同的字符串具有相同的长度。

我正在实现 robin-karp 算法并使用下面的哈希函数：

def hs(pat):
    l = len(pat)
    pathash = 0
    for x in range(l):
        pathash += ord(pat[x])*prime**x # prime is global variable equal to 101
    return pathash

Answer 1

这是一个哈希。根据定义，不能保证不会发生冲突 - 否则，散列必须至少与散列值一样长。

你所做的事情背后的想法是基于数论：与你的有限群的大小互质的数字的幂（可能原作者的意思是 2^N）可以给你任何数字有限群，很难分辨它们是哪一个。

遗憾的是，这个散列函数的有趣部分，即散列的大小限制/模运算，已被排除在此代码之外——这让人想知道您的代码来自哪里。据我立即看到，与 Rabin-Karb 没什么关系。