4. (10 Points) When using division method to map keys to tableindexes, it is normally better using a prime number for table size.Provide mapped indexes for the keys in the table using thisdivision method: index = key %m. Also, provide the total number ofcollisions for each m.
Keys
10
100
1000
10000
#Collisions
m=100
m=101
Answer
Division method is a simplest hashing technique. The function isas follows,
h(x)= x mod m
x is an integer ie key and m stands for table size here
Collision occurs when more than one key is mapped to the sameindex.
The table is filled by the remainders of key%m.
Keys10100100010000Collisionsm=100100003m=101101009110
m=100
- key =10, index= key %m=10 % 100=10
- key =100,
OROR