Separate Chaining (Module 7)

Question 1

Which collision resolution technique stores the hash table as an array of bucket where each bucket containers a pointer to a linked list that holds all of the elements hashing to that index?

Answer 1

separate chaining

Question 2

Seperate Chaining Mechanism:
1) What first happens to the new key?
2) If the bucket at an index is empty, where does the new key go?
3) If a collision occur, what happens to the new key?

Answer 2

1) it’s hashed using a hash function to compute the index
2) it’s added as the first element of the list
3) it’s added to the list in that bucket

Question 3

What are 2 advantages for separate chaining?

Answer 3

1) multiple keys can be in the same index without probing or rehashing
2) linked lists can dynamically grow (avoiding overflow)

Question 4

What are 2 disadvantages for separate chaining?

Answer 4

1) needs extra memory for pointers
2) performance degradation (more collisions = more degradation)

Question 5

What should you do to prevent performance degradation and have efficient lookup times?

Answer 5

keep the average length of the chains small

Question 6

When is resizing typically done?

Answer 6

When a load factor exceeds a certain threshold

Question 7

What is the formula for a load factor?

Answer 7

of elements in table / total # of buckets in the table

Question 8

How does resizing work?

Answer 8

create a larger table and rehash all elements into new table

Question 9

Why do we rehash?

Answer 9

to make sure elements are distributed to maintain uniformity and reduce collisions