Back to the full dot-point answer
SingaporeComputer ScienceQuick questions
Data Structures
Quick questions on Hash tables explained: H2 Computing
7short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.
What are collisions?Show answer
Two different keys can hash to the same bucket - a collision. Since a finite table cannot give every possible key its own slot, collisions are inevitable and must be resolved. Two standard strategies:
What is load factor?Show answer
The load factor measures how full the table is:
What is a good hash function?Show answer
A good hash function distributes keys uniformly across buckets (few collisions), is fast to compute, and is deterministic (same key, same bucket every time). Poor distribution clusters keys and pushes the worst case toward .
What is open addressing?Show answer
Each bucket holds at most one key. On collision, probe for the next free bucket by a rule (linear probing tries the next index, wrapping around). Lookup follows the same probe sequence until it finds the key or an empty slot.
What is q1?Show answer
With , which bucket does key 23 hash to? [1 mark]
What is q2?Show answer
Define the load factor of a hash table and state its effect as it increases. [2 marks]
What is q3?Show answer
Distinguish between chaining and open addressing for collision resolution. [2 marks]
Have a question we have not covered?
This dot-point answer is short enough that we have not extracted many short questions yet. Read the full dot-point answer or ask Mo, our study assistant, in the chat for follow ups.