Hashing Linear Probing

(1) Using division method for a hash function H and a hash table of size m, store your data of student IDs (n= 30) in an array of records using random generator. Record includes Student ID, and Name.

H (k) = k mod m

m : A prime number between 2**6 < m < 2**7 and not too close to the power of 2 (e.g. 79)

• Read 30 6-digit student IDs from array of records And mapped them to hash table using linear probing
• Print out hash table
• Do minimum two searches one with ID found and the other one with ID not found.

(2) Using multiplication method for a hash function H and a hash table of size m, store your data of student IDs to an array of records same as in (A).

H (k) = [ m * ( k * A mod 1 ) ]
A = ( 5**(1/2) - 1 ) / 2 = 0.6180339887 (by Knuth 1973)

m : A natural number for table size ( e.g. 79)

Do (a), (b), and (c) same as in Problem (A).