The objective of this assignment is to provide on handexperience of: o Hashing o

Question

The objective of this assignment is to provide on handexperience of:

o       Hashing

o       Collision Resolution

Question

Given input {5, 86, 35, 67, 99, 48, 6, 15, 59} and a hashfunction h(x) =x mod 7,

show the resulting:

·        Chaining hashtable.

·        Openaddressing hash table using linear probing.

·        Openaddressing hash table using quadratic probing.

Explanation / Answer

Bucket size is not given, so we consider it is 11 Chaining Find mod for all elements one by oneFirst we will find 5 mod 7 =5This location is empty so it will be occupied in this locationFirst we will find 86 mod 7 =2This location is empty so it will be occupied in this locationFirst we will find 35 mod 7 =0This location is empty so it will be occupied in this locationFirst we will find 67 mod 7 =4This location is empty so it will be occupied in this locationFirst we will find 99 mod 7 =1This location is empty so it will be occupied in this locationFirst we will find 48 mod 7 =6This location is empty so it will be occupied in this locationFirst we will find 6 mod 7 =6This location is already occupied so it will be chained to this location First we will find 15 mod 7 =1This location is already occupied so it will be chained to this location First we will find 59 mod 7 =3This location is empty so it will be occupied in this locationAfter above calculation, final bucket will be [0] -> 35[1] -> 99 -> 15[2] -> 86[3] -> 59[4] -> 67[5] -> 5[6] -> 48 -> 6[7][8][9][10]#########################################################################Open addressing (Linear probing ( h(k) % 7 + i*c )%BUCKET_SIZE),assume c =1 Find mod for all elements one by onefor finding index we will use, (5 mod 7 + 0)%11 =5HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (86 mod 7 + 0)%11 =2HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (35 mod 7 + 0)%11 =0HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (67 mod 7 + 0)%11 =4HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (99 mod 7 + 0)%11 =1HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (48 mod 7 + 0)%11 =6HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (6 mod 7 + 0)%11 =6MISS: This location is already occupied so it try next location location for finding index we will use, (6 mod 7 + 1)%11 =7HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (15 mod 7 + 0)%11 =1MISS: This location is already occupied so it try next location location for finding index we will use, (15 mod 7 + 1)%11 =2MISS: This location is already occupied so it try next location location for finding index we will use, (15 mod 7 + 2)%11 =3HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (59 mod 7 + 0)%11 =3MISS: This location is already occupied so it try next location location for finding index we will use, (59 mod 7 + 1)%11 =4MISS: This location is already occupied so it try next location location for finding index we will use, (59 mod 7 + 2)%11 =5MISS: This location is already occupied so it try next location location for finding index we will use, (59 mod 7 + 3)%11 =6MISS: This location is already occupied so it try next location location for finding index we will use, (59 mod 7 + 4)%11 =7MISS: This location is already occupied so it try next location location for finding index we will use, (59 mod 7 + 5)%11 =8HIT: This location is empty so it will be occupied in this locationAfter above calculation, final bucket will be [0] -> 35[1] -> 99[2] -> 86[3] -> 15[4] -> 67[5] -> 5[6] -> 48[7] -> 6[8] -> 59[9][10]#########################################################################Open addressing using quarditic ( h(k) % 7 + i*c + i*c*c )%BUCKET_SIZE, assume c=1 Find mod for all elements one by onefor finding index we will use, (5 mod 7 + 0 + 0)%11 =5HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (86 mod 7 + 0 + 0)%11 =2HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (35 mod 7 + 0 + 0)%11 =0HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (67 mod 7 + 0 + 0)%11 =4HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (99 mod 7 + 0 + 0)%11 =1HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (48 mod 7 + 0 + 0)%11 =6HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (6 mod 7 + 0 + 0)%11 =6MISS: This location is already occupied so it try next location location for finding index we will use, (6 mod 7 + 1 + 1)%11 =1MISS: This location is already occupied so it try next location location for finding index we will use, (6 mod 7 + 2 + 4)%11 =2MISS: This location is already occupied so it try next location location for finding index we will use, (6 mod 7 + 3 + 9)%11 =9HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (15 mod 7 + 0 + 0)%11 =1MISS: This location is already occupied so it try next location location for finding index we will use, (15 mod 7 + 1 + 1)%11 =7HIT: This location is empty so it will be occupied in this locationfor finding index we will use, (59 mod 7 + 0 + 0)%11 =3HIT: This location is empty so it will be occupied in this locationAfter above calculation, final bucket will be [0] -> 35[1] -> 99[2] -> 86[3] -> 59[4] -> 67[5] -> 5[6] -> 48[7] -> 15[8][9] -> 6[10]

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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