Please answer these questions properly, Thanks. A hashtable of size 7 uses separ
ID: 3836651 • Letter: P
Question
Please answer these questions properly, Thanks.
A hashtable of size 7 uses separate chaining to resolve collisions. A polynomial hash function where a = 33 is used. Sketch the table's contents after the following words have been added in the exact order shown: find, edge, body, race, plan, beat they You may find it useful to create a list of lowercase letters and their ASCII numeric value. The letter a's value is 97 and z's value is 122. A hashtable of size 7 uses linear probing to resolve collisions. Using Part A's polynomial hash function and sequence of words, sketch the table's contents after the words have been added.Explanation / Answer
Hashtable size = 7
Given order --> find,edge,body,race,plan,beat,they
ASCII numeric values for letter a is 97 and z's value is 122.
find the ASCII values for all words as
find --> 102+105+110+100 = 417
edge --> 101+100+103+101 = 405
body --> 98+111+100+121 = 430
race --> 114+97+99+101 = 411
plan --> 112+108+97+110 = 427
beat --> 98+101+97+116 = 412
they --> 116+104+101+121 = 442
PartA: Separate Chaning
Now, hashing based on hashtable function
H(K) = K mod M --> Here, K is the key and M is the size
find --> H(417) = 417 % 7 = 4
edge --> H(405) = 405 % 7 = 6
body --> H(430) = 430 % 7 = 3
race --> H(411) = 411 % 7 = 5
plan --> H(427) = 427 % 7 = 0
beat --> H(412) = 412 % 7 = 6
they --> H(442) = 442 % 7 = 1
Table
0 --> plan
1 --> they
2 -->
3 --> body
4 --> find
5 --> race
6 --> edge --> beat
Part B -- Linear probing
Hash function
H(K) = K mod M --> Here, K is the key and M is the size
find --> H(417) = 417 % 7 = 4
edge --> H(405) = 405 % 7 = 6
body --> H(430) = 430 % 7 = 3
race --> H(411) = 411 % 7 = 5
plan --> H(427) = 427 % 7 = 0
beat --> H(412) = 412 % 7 = 6
they --> H(442) = 442 % 7 = 1
Table
0 --> plan
1 --> beat ( since, bucket 6 is filled with "edge" so next empty position after 6 is "1")
2 --> they ( since, bucket 1 is filled with "beat" so next empty position after 1 is "2")
3 --> body
4 --> find
5 --> race
6 --> edge