如何验证这个散列函数不会给出两个不同字符串的相同结果？

Question

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

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

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)可以给出这个有限组中的任何数字，而且很难判断它们是哪一个。

遗憾的是，这个哈希函数的有趣部分，即散列的大小限制/模块操作，被忽略在代码之外--这让人怀疑您的代码来自何处。据我所见，和拉宾-卡布没有什么关系。