Hash Table Size (Module 7)

Question 1

What happens if the table size is a composite number? (m = 10)

Answer 1

keys may have hash values that repeatedly collide due to common factors with m

Question 2

Why do prime numbers give better distribution of hash values?

Answer 2

they have no divisors other than 1 and themselves (minimizes patterns)

Question 3

A prime ‘m’ guarantees m-1 is _________ by many keys

Answer 3

not divisible

Question 4

What type of bias produces a biased distribution if m is composite?

Answer 4

modular arithmetic bias

Question 5

What is the best-case time complexity for hash tables?

Answer 5

O(1)

Question 6

What is the worst-case time complexity for hash tables?

Answer 6

O(n)

Question 7

What is the space complexity for separate chaining and open addressing?

Answer 7

O(m)

Question 8

What is the time complexity for rehashing?

Answer 8

O(n)

Question 9

What is the space complexity for rehashing?

Answer 9

O(2m)

Question 10

Choosing a table size m as a prime number is crucial in all probing techniques because?

Answer 10

1) reduces clustering
2) ensures full coverage
3) improves hash function effectiveness
4) prevents cycles

Question 11

What are 3 ideas for extra optimization?

Answer 11

1) take in better keys
2) optimize the bucket
30 modify the array’s internal capacity