Explore BrainMass
Share

Division method for a hash function

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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.

problem
----------
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>

solution
---------
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
https://brainmass.com/computer-science/random-number-generation/division-method-for-a-hash-function-71748

Solution Summary

Division method for a hash function is examined.

$2.19
See Also This Related BrainMass Solution

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