IB Computer Science HL · Year 2 · Lesson 28
Hash tables + B4 cumulative Paper 2 checkpoint
Abstract data types separate what operations mean from how they are implemented, helping you choose structures by behaviour and trade-offs.
Paper 250 minutesB4.1.6 · B4.1.1 · B4.1.2 · B4.1.3 · B4.1.4 · B4.1.5
Use Next or the arrow keys.
Today’s targets
What you need to be able to do
2 / 9
- ExplainThe core principles of ADTs
- RetrieveReconnect today’s new material to previously taught content from this topic.
B4.1.6B4.1.1B4.1.2B4.1.3B4.1.4B4.1.5
Paper 2 lensMatch the depth of every response to the command term. Previously learned content can move quickly, but retrieval must still be accurate.
Page 2 of 9
Retrieve
Rapid Recall Deck
3 / 9
Say the answer aloud before flipping. Mark secure knowledge quickly and spend time on the gaps.
- What is the purpose of a hash function in a hash table?: It transforms a key into an index/location used to place or find the associated data.
- What is a collision in hashing?: Two different keys produce the same table location/index.
- What are two common ways to resolve hash collisions?: Separate chaining stores multiple entries at a location; open addressing searches for another available location in the table.
- What is a hash table's load factor?: A measure of how full the table is, commonly the number of stored entries divided by the number of table slots.
- Why can a high load factor hurt hash-table performance?: More entries competing for limited locations generally increases collisions and the work needed to resolve them.
- Which Java and Python structures provide hash-based maps and sets?: Java: HashMap and HashSet. Python: dict and set.
- What three linked-list forms must you distinguish?: Singly linked, doubly linked, and circular linked lists.
- What four core operations apply to linked lists?: Insertion, deletion, traversal, and search.
- What ordering idea makes a binary search tree searchable?: Each node separates values into ordered left and right subtrees according to the chosen comparison rule.
- What two properties distinguish a set ADT?: Its elements are unique and the set is unordered.
Page 3 of 9
B4.1.6 · Learn
Core knowledge and application
4 / 9
B4.1.6Explain
The core principles of ADTs
Abstract data types separate what operations mean from how they are implemented, helping you choose structures by behaviour and trade-offs.
Exam moveGive the mechanism or relationship and make the reasons/causes explicit.
Required detail 1High-level description of data structures and their associated operations and purpose
Required detail 2The underlying mechanics of hash tables, including hashing functions, collision resolution strategies and load factors
Required detail 3The underlying mechanics of sets to store and manage data
Required detail 4HashMap and HashSet in Java; dict and set in Python
Assessment boundaryPaper 2
Explain it without notes
Explain: The core principles of ADTs in the context of a system that needs efficient insertion, search and set membership.
- High-level description of data structures and their associated operations and purpose
- The underlying mechanics of hash tables, including hashing functions, collision resolution strategies and load factors
- The underlying mechanics of sets to store and manage data
- HashMap and HashSet in Java; dict and set in Python
Page 4 of 9
Trace / construct
Programming checkpoint
5 / 9
prices = {"pen": 2.5, "notebook": 5.0}
prices["marker"] = 3.0
print(prices.get("pen"))HashMap<String, Double> prices = new HashMap<>();
prices.put("pen", 2.5);
prices.put("notebook", 5.0);
prices.put("marker", 3.0);
System.out.println(prices.get("pen"));Before you run itTrace the code by hand. Identify state changes, branch/loop behaviour, and the final result.
Modify it
Change one condition, input or operation so the program solves a slightly different problem. Predict the effect before editing.
Page 5 of 9
Worked example · B4.1.6
Hashing, collisions and load factor
6 / 9
Suppose index = key mod 5.
12 → 2 7 → 2 22 → 2
All three keys target bucket 2: this is a collision.
Separate chaining
Bucket 2 stores a small collection/list of entries: [12, 7, 22].
Open addressing
If bucket 2 is occupied, probe another bucket according to the chosen strategy until an available position is found.
Load factor
stored entries / number of buckets. As the table becomes crowded, collisions and probe/chain costs typically increase, so resizing/rehashing may be useful.Page 6 of 9
Apply
Transfer to a new scenario
7 / 9
ScenarioA system that needs efficient insertion, search and set membership needs a design or technical decision related to today’s topic. Explain what matters and why.
- High-level description of data structures and their associated operations and purpose
- The underlying mechanics of hash tables, including hashing functions, collision resolution strategies and load factors
Page 7 of 9
Exam lens
Paper 2 practice
8 / 9
Build the response before checking notesUse precise terminology and match the required depth.
- Explain: The core principles of ADTs in the context of a system that needs efficient insertion, search and set membership.
Self-checkAnswer the exact command term. For explain, include mechanism/reason; for compare, pair criteria; for discuss/evaluate/justify, build supported reasoning and a conclusion.
Page 8 of 9
Homework
Finish the learning cycle
9 / 9
IA — main task
Continue Criterion D development. Keep code readable, record meaningful implementation decisions, and maintain testing/evidence notes as you work.
Syllabus — short
Complete one targeted Paper 2/Paper 1 retrieval task from today’s lesson.
Designed by David Xu
© 2026 David Xu. All rights reserved.
Educators and students are welcome to use these materials for non-commercial teaching and learning with attribution. Please share the original link when possible. Reposting, redistributing modified copies, removing attribution, or commercial use requires prior permission.
End of Lesson 28.