Using the hash function H(NUMBER) = NUMBER % 15, place the following numbers int
ID: 3694094 • Letter: U
Question
Using the hash function H(NUMBER) = NUMBER % 15, place the following numbers into the hash using coalesced hashing with a cellar. How many collisions did you have? Suppose we are using the 7 digit student numbers (SNs) of students at NSU to hash into a table of size 100 with linear probing of size 1. Discuss the merits of each of the following hash functions: H(SN) = product of all the digits In the SN mod 100. H(SN) = sum of all the digits In the SN mod 100. H(SN) = value of the first two digits (as a two d git integer) of the SN. H(SN) = value of the last two digits (as a two-digit integer) of the SN.Explanation / Answer
Hello user, I will answer your question gladly :D
4.a) Lets apply the hash function to each number:
951 % 15 = 6
055 % 15 = 10
099 % 15 = 9
811 % 15 = 1
543 % 15 = 3
075 % 15 = 0
990 % 15 = 0 ->1 ->2
710 % 15 = 5
047 % 15 = 2-> 3
722 % 15 = 2->3->4
So, we got 3 initial collisions, but if we count the relocations, it would be 5 total collisions.
5.a) It would be a useful hash function IF THE DIGITS of the SN would not include the zero, because when one digit is zero, the result would be zero, and will carry heavy collision problems... Besides that problem, you need to consider the size of the product of the digits, because it could go besides the size of the data it contains.
5.b) the sum of the digit is not a good option, because the 7 digit SN can reach 63 with its sum as maximum (9*7=63). So it would lead to collision problems because all the sums having similar results.
5.c) In general, the identification numbers are auto-increments, which means that A LOT of students would have the same first 2 digits( 0000001-0099999 for instance), which will result in heavy collisions.
5.d) The last 2 digits of a SN sounds good, because it would be a repeated case for each hundred students :D
If you have any doubts, you can contact me by this way. Have a nice day! :D
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.