In each of the following cases, we insert in an initially empty Hash Table the v

Question

In each of the following cases, we insert in an initially empty Hash Table the values 2, 29, 35, 14, 55, 47, 91, and 68, in this order. The hash function should calculate h=v%s, where v is the value and s=11 is the size of the array.

(a) Write the content (array) of the Hash Table, if resolving collisions by rehashing keys as h’=(h+2)%s. Show the hash keys calculated.

(b) Write the content (array) of the Hash Table, if using quadratic probing instead, deriving new keys as h’=((h+i2)%s, 1?i?s. Show the keys.  

(c) Sketch what the Hash Table will look like if we use chained buckets instead of rehashing values to resolve collision. Show the exact lists.

Explanation / Answer

a) v=2

h=2%11=2

therefore 2 will be mapped to bucket number 2.

v=29

h=29%11=7

29 will be mapped to 7.

v=35

h=35%11=2

therefore collision therefore we will rehash as:

h'=(2+2)%11=4%11=4

therefore 35 will be mapped to 4

v=14

h=14%11=3

14 will be mapped to 3.

v=55

h=55%11=0

55 will be mapped to 0.

v=47

h=47%11=3

therefore collision and will rehash as:

h'=(3+2)%11=5%11=5

therefore 47 will map to 5.

v=91

h=91%11=3

therefore collision and we will rehash as:

h'=(3+2)%11=5

again collision so we will again rehash as:

h"=(5+2)%11=7

again collision so we again rehash as:

h'''=(7+2)%11=9

so 91 will map to 9.

v=68

h=68%11=2

therefore collision and we will rehash to

h'=(2+2)%11=4

again collision so it will rehash to:

h"=(4+2)%11=6

therefore finally 68 will map to 6.

b) v=2

h=2%11=2

therefore 2 will map to 2.

v=29

h=29%11=7

29 will map to 7.

v=35

h=35%11=2

therefore collision and now we will rehash with i=1

h'=(2+1)%11=3

therefore 35 will map to 3.

v=14

h=14%11=3

therefore collision so we will rehash with i=1.

h'=(3+1)%11=4

so 14 will map to 4.

v=55

h=55%11=0

55 gets mapped to 0.

v=47

h=47%11=3

therefore collision and we will rehash with i=1

h'=(3+1)%11=4

again collision so we will again rehash with i=2

h"=(4+4)%11=8

therefore 47 will map to 8.

v=91

h=91%11=3

collision so we will rehash with i=1.

h'=(3+1)%11=4

again collision so we will rehash with i=2

h"=(4+4)%11=8

again collision so we will rehash with i=3

h"'=(8+9)%11=17%11=6

therefore 91 will map to 6.

v=68

h=68%11=2

collision so we will rehash with i=1

h'=(2+1)%11=3

again collision so we will rehash with i=2

h"=(3+4)%11=7

again collision so we will rehash with i=3

h"'=(7+9)%11=5

so 68 will map to 5.

c) v=2

h=2%11=2

2 will map to 2.

v=29

h=29%11=7

29 will map to 7.

v=35

h=35%11=2

collision so 35 will be added to the list of 2.

v=14

h=14%11=3

14 will map to 3

v=55

h=55%11=0

55 will map to 0.

v=47

h=47%11=3

so 47 will get added to the list of 3.

v=91

h=91%11=3

so 91 will get added to the list of 3.

v=68

h=68%11=2

so 68 will get added to the list of 2.

INDEX|ELEMENT|LIST

0|55|NULL

1IEMPTY|NULL

2|2|35->68

3|14|47->91

4|EMPTY|NULL

5|EMPTY|NULL

6|EMPTY|NULL

7|29|NULL

8|EMPTY|NULL

9|EMPTY|NULL

10|EMPTY|NULL

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.