Computer Science · 11th Grade

Active learning ideas

Hash Tables and Hashing Functions

Active learning works especially well for hash tables because the abstract mechanics of hashing and collisions become visible only when students physically simulate or analyze concrete cases. Students need to see how a single poorly chosen hash function can collapse a near-instant lookup into a linear search to truly grasp why these structures matter.

• Common Core State Standards
• CSTA: 3B-AP-14

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

Activity 01

• Simulation Game
• 25 min · Small Groups

Simulation Game: Paper Hash Table

Each student group receives a set of key cards and a small table drawn on paper with 10 buckets. They design a simple hash function, insert all keys, and document every collision. Groups then compare which hash functions produced fewer collisions and discuss why, building intuition about what makes a good hash function.

Explain the mechanism of a hash table for efficient data retrieval.

Facilitation Tip

During the Paper Hash Table activity, circulate and ask each group to explain their hash function choice before they insert values to surface assumptions early.

What to look for

Present students with a small array representing a hash table and a simple hash function. Provide a list of key-value pairs. Ask students to trace the insertion of each pair, showing how collisions are handled using a specified strategy (e.g., chaining). Check their work for correct index calculation and collision management.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 02

• Think-Pair-Share
• 20 min · Pairs

Think-Pair-Share: Collision Resolution Comparison

Present two approaches to resolving a collision (chaining vs. linear probing) with a small worked example of each. Students individually predict what happens when the table gets 80% full for each strategy, compare predictions with a partner, then the class discusses the real trade-offs in terms of memory and performance degradation.

Analyze different collision resolution strategies (e.g., chaining, open addressing).

Facilitation Tip

In the Collision Resolution Comparison, assign each pair one chaining example and one open addressing example so they compare the exact same input set side by side.

What to look for

Pose the question: 'Imagine you are designing a hash table for storing student IDs and their corresponding grades. What are the potential problems with a hash function that only uses the first digit of the student ID? How would this impact performance, and what strategies could you use to resolve these issues?' Facilitate a class discussion on their responses.

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

Activity 03

• Case Study Analysis
• 30 min · Small Groups

Case Study Analysis: Real Hash Function Failures

Groups analyze examples of poor hash function design (naively hashing by first letter, causing dramatic clustering for common starting letters). Each group identifies the design flaw, predicts the performance impact, and proposes an improvement. The class then synthesizes properties of a well-designed hash function.

Evaluate the impact of a poorly designed hash function on performance.

Facilitation Tip

For the Gallery Walk, assign poster titles that force comparison: ‘Chaining when load factor > 0.8’ versus ‘Open addressing when load factor < 0.5’.

What to look for

Ask students to write down one advantage of using a hash table over a simple array for lookups. Then, have them describe in one sentence the core difference between chaining and open addressing as collision resolution methods.

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

Activity 04

• Gallery Walk
• 35 min · Small Groups

Gallery Walk: Hash Table Trade-Off Posters

Groups each research and create a poster on one aspect: chaining, open addressing, load factor effects, or hash function design. A gallery walk allows all students to build a complete picture of hash table design through peer-created materials, with sticky-note questions and comments left at each station.

Explain the mechanism of a hash table for efficient data retrieval.

What to look for

Present students with a small array representing a hash table and a simple hash function. Provide a list of key-value pairs. Ask students to trace the insertion of each pair, showing how collisions are handled using a specified strategy (e.g., chaining). Check their work for correct index calculation and collision management.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

A few notes on teaching this unit

Start with the Paper Hash Table to make the invisible visible, then use the Case Study to anchor the discussion in failure rather than abstraction. Research shows that students grasp O(n) degradation more when they witness it themselves in a controlled simulation, so avoid lecturing about worst-case performance up front. Always connect the activity back to real systems students use daily, like dictionary lookups or login databases, to build relevance and memory.

By the end of these activities, students should be able to trace a key through a hash function, compute its bucket, and defend why a collision strategy matters. They should also compare chaining and open addressing using real data and explain trade-offs without defaulting to ‘chaining is always better’ or ‘hash tables are always O(1).’

---

Watch Out for These Misconceptions

• During the Paper Hash Table activity, watch for students assuming every hash function will distribute keys evenly without testing a deliberately bad hash function.

  Ask each group to rerun their simulation using a hash function that uses only the last digit, then observe how many collisions occur. Direct their attention to the clustering pattern to confront the uniformity assumption.

• During the Real Hash Function Failures case study, watch for students believing any hash function that produces integers is acceptable.

  Have students compare two hash functions on the same dataset: one that mixes digits and one that just sums them. Ask them to calculate the load factor per bucket and justify which function they would deploy.

• During the Collision Resolution Comparison think-pair-share, watch for students generalizing that chaining always outperforms open addressing.

  Provide identical datasets to each pair and ask them to calculate cache behavior and probe sequences under high load. Prompt them to identify scenarios where open addressing may be preferable despite more collisions.

---

Methods used in this brief

• Simulation Game
• Think-Pair-Share
• Case Study Analysis
• Gallery Walk