h（k）= k mod m，其中k是以2 * p和m = 2^p-1爲基數解釋的字符串。證明h（x）= h（y）

-1

考慮散列函數：

h(k) = k mod m，其中k是在基數2 ^p且m = 2 ^p解釋的字符串 - 1顯示，通過在字符串y置換字符我們可以推導出字符串x ⇒ x和y散列爲相同的值。

我已經決定有兩種方法可以解決這個問題。我可以表明

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

H（X）=（X *（2 ^p - 1））％（2 ^p - 1），這將總是等於0不管我們使用的是什麼x

我在網上查了幾個解決方案，但我對這個問題很困惑。我認爲我最大的問題是我不知道我應該如何使用基數信息來解決這個問題。

我能得到一個提示，我該如何開始這個問題？

你知道的老把戲來快速確定一個數字是否是整除9？這是一樣的原則。 –

所以這就是「以基數2^p解釋」這一行的想法？我需要將每個字符的值加起來，並顯示無論順序如何，總數都是相同的。我會努力的！ – user1754045

你基本上被要求通過9個技巧來證明可分割的廣義版本。 –

如果m = 2^p - 1和k是字符串中radix 2^p解釋，即是除轉置字符散列到相同的值。例如相同讓m = 2^3 - 1 = 7以及使用ASCII值字符然後兩個字符串：

字符串`` abcd''表示爲

k = 97。 8^3 + 98。 8^2 + 99。 8 + 100 = 56828
其散列56828 模7 = 2

字符串``BADC '' 被表示爲

K = 98。 8^3 + 97。 8^2 + 100。 8 + 99 = 57283
其哈希57283 國防部7 = 2

2013-01-07 09:16:01 Atiq

回答