Please review the problem and explain each step of the solution listed below, and give me an example of an application which this property would be undesirable in a hash function.
Consider a version of the division method in which h(k) = k mod m, where m = (2^p) -1 and k is a character string interpreted in radix 2^p. Show that if a string x can be derived from string y by permuting its characters, then x and y hash to the same value. <B>Give an example of an application in which this property would be undesirable in a hash function.</B>
All permutations can be generated by a sequence of two character interchanges. If two arbitrary characters, i and j, are switched, then the values hash to the same place.
We consider two numbers x and y which have characters i and j interchanged, and i > j.
Note: in this solution xi = x sub i and xj = x sub j (same goes for y).
x - y = (xi - yi)(m + 1)^(i-1) + (xj - yj)(m+1)^(j-1)
= (xi - xj)(m + 1)^(i-1) - (xi - xj)(m+1)^(j-1)
= (xi - xj)[(m + 1)^(i-1) - (m + 1)^(j-1) ]
= (xi - xj)(m + 1)^(j-1) * [(m + 1)^(i-j) -1]
= (xi - xj)(m + 1)^(j-1) * [(m + 1) - 1] * Summation of (m + 1)^k [from k = 0 to i - j - 1]
= 0 mod m© BrainMass Inc. brainmass.com October 24, 2018, 7:34 pm ad1c9bdddf
Division method for a hash function is examined.
Hash Division Function Numbers
A hash file uses the division function to calculate the bucket number from the given key value. The file was set with 11 buckets numbered 0 to 10, where each bucket can contain at most 3 records. Analyse what happens when records with the following keys are inserted into the hash file. Explain what went wrong and suggest a solution.
15 27 44 79 30 26 38
5 35 9 16 45 57 18
Check the attachment for the table correctly displayed.View Full Posting Details