Open Addressing / Linear Probing (Module 7)

Question 1

Which collision resolution technique finds another open slot in the hash table to store the key when collision occurs?

Answer 1

open addressing

Question 2

What are the 3 ways to find an avaliable slot through probing?

Answer 2

1) linear probing
2) quadratic probing
3) double hashing

Question 3

Which type of probing sequentially searches the table from the index of the collision until an open slot is found?

Answer 3

linear probing

Question 4

What is linear probing’s primary hash function?

Answer 4

hash(k)

Question 5

What is the linear probing formula?

Answer 5

(hash(k) + i) mod m

Question 6

What happens when multiple keys are hashed to the same buckets leading to a group of occupied buckets growing with each collision?

Answer 6

clustering

Question 7

Why is clustering problematic?

Answer 7

collisions lead to longer probe sequences and access times (degraded performance)

Question 8

Resizing and rehashing is ___________!

Answer 8

expensive

Question 9

What is the advantage of linear probing?

Answer 9

simple implementation

Question 10

What is the disadvantage of linear probing?

Answer 10

creates clusters that slow down insertion/search operations