Week 3 Graphs & hash tables

Question 1

What does the hash function do?

Answer 1

1.Converts input (key) into a fixed-size integer, the hash code.
2.Ensures uniform distribution to minimise collisions.

Question 2

How does the hash function resolve collisions?

Answer 2

1. Separate Chaining: Stores collided keys in a linked list or other structure.
2. Open Addressing: Finds the next available slot using methods like linear
   probing or quadratic probing.

Question 3

Hash table load factor?

Answer 3

The ratio of stored elements to the number of slots.

Question 4

Hash table resizing?

Answer 4

Rehashing to a larger table size when the load factor exceeds a
threshold.

Question 5

Hash table implementation performance optimisation consideration?

Answer 5

Aim for O(1) average-case time complexity for insertion, deletion, and
search.

Question 6

What are graph vertices?

Answer 6

Nodes representing entities.

Question 7

What are graph edges?

Answer 7

Connections between vertices, representing relationships.