C++ Data structure homework A hashtable of size 7 uses separate chaining to reso
ID: 3838056 • Letter: C
Question
C++ Data structure homework
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
Given a string s = "xk-1xk-2 ... x0"
h(s) = xk-1 × ak-1 + xk-2 × ak-2 + ... + x0 × a0
Simplest compression function: modulo N:
Hash index = hashCode % N
Hash index of words:
find = ( (102 x 33^3 ) + (105 x 33^2 ) + (110 x 33^1 ) + (100 x 33^0 ) + )%7 = 2
edge = ( (101 x 33^3 ) + (100 x 33^2 ) + (103 x 33^1 ) + (101 x 33^0 ) + )%7 = 5
body = ( (98 x 33^3 ) + (111 x 33^2 ) + (100 x 33^1 ) + (121 x 33^0 ) + )%7 = 1
race = ( (114 x 33^3 ) + (97 x 33^2 ) + (99 x 33^1 ) + (101 x 33^0 ) + )%7 = 2
plan = ( (112 x 33^3 ) + (108 x 33^2 ) + (97 x 33^1 ) + (110 x 33^0 ) + )%7 = 5
beat = ( (98 x 33^3 ) + (101 x 33^2 ) + (97 x 33^1 ) + (116 x 33^0 ) + )%7 = 4
they = ( (116 x 33^3 ) + (104 x 33^2 ) + (101 x 33^1 ) + (121 x 33^0 ) + )%7 = 2
separate chaining:
0
1
body
2
find-->race-->they
3
4
beat
5
edge-->plan
6
Linear probing:
0
1
body
2
Find
3
4
5
edge
6
race index is 2 but find already there in 2 so next location 3 is free so race occupies 3
0
1
body
2
Find
3
Race
4
5
Edge
6
Plan hash index is 5 but edge alredy occupied it so it will placed at next free location that is 6
0
1
body
2
Find
3
Race
4
Beat
5
Edge
6
Plan
They hash index is 2 but find alredy occupied it so next available location is 0 so hash table will be
0
they
1
body
2
Find
3
Race
4
Beat
5
Edge
6
Plan
0
1
body
2
find-->race-->they
3
4
beat
5
edge-->plan
6
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.