Practice Flashcards
Flip to reveal answersHow does a hash table locate a value?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 5 Flashcards — Core principles of ADTs
Sign up free to track progress and get spaced-repetition review schedules.
Question
How does a hash table locate a value?
Answer
It runs the key through a **hash function**, takes the result **modulo the table size**, and goes straight to that bucket. The address is computed, not searched for.
Question
What three properties must a hash function have?
Answer
**Deterministic** (same key, same bucket, always), **fast** (it runs on every operation) and **uniform** (keys spread evenly).
Question
Why are collisions inevitable?
Answer
There are more possible keys than buckets, so two keys must eventually map to the same one. It is a counting argument, not a defect.
Question
Chaining or open addressing — what is the difference?
Answer
**Chaining** stores colliding keys in a list inside the bucket. **Open addressing** puts them in the next free bucket, so the table can never hold more items than buckets.
Question
What is a hash table's complexity?
Answer
**O(1) on average, O(n) in the worst case** — the worst case being a hash function that clusters every key into one bucket.
Read the notes
Full study notes for Core principles of ADTs
Topic 8.1 hub
Fundamentals of ADTs
More from Topic 8.1
All flashcards in this topic
Computer Science exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free