algorithm - h(k) = k mod m，其中 k 是以基数 2^p 和 m = 2^p – 1 解释的字符串。证明 h(x) = h(y)

Question

完整的问题是：

考虑哈希函数：

h(k) = k mod m，其中 k 是以基数 2 ^p和 m = 2 ^p – 1 解释的字符串。表明通过置换字符串中的字符，我们可以将字符串和哈希y导出为相同的值。x ⇒ xy

我决定有两种方法可以解决这个问题。我可以证明

h(x) - h(y) = 0或者

h(x) = (x * (2 ^p - 1)) % (2 ^p - 1) 无论我们使用什么 x，它总是等于 0

我在网上查找了几种解决方案，但我对这个问题感到非常困惑。我认为我最大的问题是我不确定我应该如何使用基数信息来解决这个问题。

我可以得到关于我应该如何开始这个问题的提示吗？

Answer 1

如果m = 2^p - 1和 k 是在 中解释的字符串radix 2^p，则两个字符串相同，除了转置的字符散列到相同的值例如 letm = 2^3 - 1 = 7和使用字符的 ASCII 值：

字符串“abcd”表示为

k = 97。8^3 + 98 。8^2 + 99 。8 + 100 = 56828
哈希 56828 mod 7 = 2。

字符串“badc”表示为

k = 98。8^3 + 97 。8^2 + 100 。8 + 99 = 57283
哈希 57283 mod 7 = 2。