Computer Science · Grade 12

Active learning ideas

Hash Tables and Hashing

Active learning works for hash tables because students need to see performance degrade when collisions occur, not just read about it. These activities let them manipulate hash functions, count chains, and compare timings, turning abstract time complexity into something they can measure and discuss. Concrete experiments correct misconceptions faster than lectures ever could.

• Ontario Curriculum Expectations
• CS.DSAA.11
• CS.P.11

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

Activity 01

• Document Mystery
• 35 min · Pairs

Pair Programming: Implement Hash Table

Students in pairs write a hash table class with insert, search, and delete methods using modular hashing and chaining. They test with 50 keys, logging collisions. Pairs swap code to debug and compare load factors.

How does a hash function contribute to the efficiency of data lookup?

Facilitation Tip

During Pair Programming: Implement Hash Table, remind students to print intermediate states of their table so they can trace collisions visually as they code.

What to look for

Present students with a small hash table (e.g., size 10) and a list of keys to insert. Ask them to trace the insertion process, showing the hash function calculation, the resulting index, and how collisions are handled using separate chaining. Then, ask them to calculate the load factor.

• Analyze
• Evaluate
• Self-Management
• Decision-Making

Activity 02

• Document Mystery
• 25 min · Small Groups

Small Groups: Collision Simulation

Groups use index cards as buckets and sticky notes as keys to hash student names, resolving collisions via chaining or probing. They measure probe sequences for worst-case lookups. Groups present findings on clustering effects.

Explain different strategies for resolving collisions in a hash table.

Facilitation Tip

During Small Groups: Collision Simulation, provide colored beads or sticky notes so students can physically move items and count chain lengths in real time.

What to look for

Pose the following scenario: 'Imagine you are designing a system to store user profiles for a social media platform with millions of users. Which collision resolution strategy (separate chaining or open addressing) would you choose, and why? Discuss the potential trade-offs in terms of memory usage and search speed.'

• Analyze
• Evaluate
• Self-Management
• Decision-Making

Activity 03

• Document Mystery
• 45 min · Whole Class

Whole Class: Benchmark Challenge

Class loads datasets into array lists, binary search trees, and hash tables, timing 1000 operations with Python's time module. Discuss graphs of results to compare average and worst-case runtimes.

Evaluate the trade-offs between space and time complexity in hash table design.

Facilitation Tip

During Whole Class: Benchmark Challenge, standardize the hardware and software to ensure comparisons are fair and repeatable.

What to look for

Provide students with a simple hash function and a set of keys. Ask them to identify two keys that would cause a collision. Then, ask them to explain in one sentence how separate chaining would resolve this specific collision.

• Analyze
• Evaluate
• Self-Management
• Decision-Making

Activity 04

• Document Mystery
• 20 min · Individual

Individual: Load Factor Analysis

Each student modifies a provided hash table to resize at different load factors (0.5, 0.7, 0.9), runs trials, and plots space-time graphs. Submit analysis of optimal thresholds.

How does a hash function contribute to the efficiency of data lookup?

Facilitation Tip

During Individual: Load Factor Analysis, circulate with graph paper and ask students to sketch load factor versus average chain length as they vary table sizes.

What to look for

Present students with a small hash table (e.g., size 10) and a list of keys to insert. Ask them to trace the insertion process, showing the hash function calculation, the resulting index, and how collisions are handled using separate chaining. Then, ask them to calculate the load factor.

• Analyze
• Evaluate
• Self-Management
• Decision-Making

A few notes on teaching this unit

Start with a concrete example: ask students how long it would take to find a name in a phone book without an index. Use that to introduce hashing as an index-maker. Avoid formal proofs early; let students discover load factor impacts through measurement. Keep the focus on trade-offs—time versus space, simplicity versus predictability—so they see why no single solution fits every problem.

Students should finish these activities able to trace a key through any hash table, explain why collisions matter, and choose a resolution strategy based on data rather than instinct. They should also recognize that fast access depends on good design choices, not magic guarantees.

---

Watch Out for These Misconceptions

• During Pair Programming: Implement Hash Table, watch for students assuming their hash function is perfect because it spreads keys evenly in one trial.

  Have them insert keys in reverse order or with skew distributions to show how clustering emerges and how chain lengths grow, then adjust the hash or table size based on what they observe.

• During Small Groups: Collision Simulation, watch for students believing collisions can be avoided with a clever hash.

  Use the pigeonhole principle with a small table and more keys than slots, forcing collisions despite any hash function, then let them experience chaining and probing as unavoidable responses.

• During Whole Class: Benchmark Challenge, watch for students thinking chaining always wastes more memory than probing.

  Ask them to graph memory usage versus load factor for both strategies on the same axes, highlighting where probing’s larger table offsets its simpler pointers.

---

Methods used in this brief

• Document Mystery