Computer Science · Grade 11

Active learning ideas

Hashing and Hash Tables

Active learning works for hashing and hash tables because students need to physically interact with the concept of collisions and resolutions to truly grasp why hash tables are efficient. Moving from abstract calculations to hands-on simulations and real-time benchmarks makes the performance trade-offs visible and memorable.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

• 25–45 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Problem-Based Learning
• 45 min · Pairs

Pair Programming: Simple Hash Table

Pairs code a hash table in Python using a list of lists for chaining. They define a hash function with modulo, insert 15-20 keys like student IDs, handle collisions by appending to lists, and test retrieval. Pairs then swap codes to debug and compare load factors.

Explain how a hash function maps data to an index in a hash table.

Facilitation Tip

During Pair Programming: Simple Hash Table, ask pairs to swap roles between coding and recording observations so both partners engage with the algorithm and its behavior.

What to look for

Present students with a small dataset and a simple hash function (e.g., modulo division). Ask them to manually calculate the hash index for each item and identify any collisions. Then, ask them to explain how chaining would handle one specific collision.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Activity 02

• Problem-Based Learning
• 35 min · Small Groups

Small Groups: Physical Collision Simulation

Provide bins numbered 0-9 and balls labeled with hash values. Groups insert balls using modulo hashing, resolve collisions by stacking in bins or probing next empty. They record chain lengths after 20 insertions and discuss patterns before coding digitally.

Analyze the impact of hash collisions on the performance of a hash table.

Facilitation Tip

When running Small Groups: Physical Collision Simulation, set a timer so groups focus on counting collisions and testing resolutions quickly.

What to look for

Pose the question: 'Imagine you are designing a system to store student IDs and their grades. Would a hash table be a good choice? Why or why not? What potential issues might arise, and how could you address them?' Facilitate a class discussion on the trade-offs.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Activity 03

• Problem-Based Learning
• 25 min · Whole Class

Whole Class: Performance Benchmark

Display a shared Python script projecting insertions with and without collisions. Class votes on resolution strategies, runs timed lookups on growing data sets, and graphs results. Follow with individual predictions for larger inputs.

Design a simple collision resolution strategy for a given hash function.

Facilitation Tip

For Whole Class: Performance Benchmark, provide pre-loaded tables with varying collision densities to ensure all groups observe the same performance patterns.

What to look for

Provide students with a scenario: 'A hash table with 10 slots uses the hash function h(key) = key % 10. If keys 5, 15, and 25 are inserted, what happens? Describe one method to resolve the collision for key 15.'

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Activity 04

• Problem-Based Learning
• 30 min · Individual

Individual: Design Challenge

Each student designs a hash function and resolution for 30 unique strings, like emails. They simulate insertions on paper, calculate collisions, and propose improvements. Share one insight in a class gallery walk.

Explain how a hash function maps data to an index in a hash table.

What to look for

Present students with a small dataset and a simple hash function (e.g., modulo division). Ask them to manually calculate the hash index for each item and identify any collisions. Then, ask them to explain how chaining would handle one specific collision.

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

A few notes on teaching this unit

Experienced teachers approach this topic by letting students experience the problem before naming it, so they see the need for collision resolution. Avoid rushing to code; instead, build intuition with physical models first. Research shows that students remember the performance implications better when they measure slowdowns themselves rather than accepting textbook claims.

Successful learning shows when students can explain why collisions occur, choose an appropriate resolution strategy for a given scenario, and justify its impact on performance. They should also connect their manual calculations to the timing results from benchmarks.

---

Watch Out for These Misconceptions

• During Pair Programming: Simple Hash Table, watch for students who assume their hash function must avoid collisions entirely.

  Have pairs deliberately insert keys that collide to observe the behavior, then modify their resolution strategy instead of changing the hash function.

• During Whole Class: Performance Benchmark, watch for students who believe hash table operations will always run in constant time.

  Ask students to compare timing for tables with low and high collision counts, then ask them to explain the difference in their own words.

• During Small Groups: Physical Collision Simulation, watch for students who think hashing only applies to numeric keys.

  Provide mixed data types like names and IDs, and have students convert strings to numbers using ASCII sums before hashing.

---

Methods used in this brief

• Problem-Based Learning