Computer Science · 12th Grade · Object-Oriented Design and Data Structures · Weeks 10-18

Hash Maps and Collision Resolution

Students are introduced to hash maps, exploring how these structures enable rapid data retrieval and various collision resolution strategies.

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

About This Topic

Hash maps are one of the most widely used data structures in professional software development, offering average O(1) time complexity for insertions, lookups, and deletions. Students in 12th-grade CS learn that a hash function transforms a key, such as a string or integer, into an array index, allowing near-instant access without scanning every element. The elegance of the approach depends heavily on the quality of the hash function; a poor function clusters keys at the same indices, causing collisions.

Collision resolution is where the design choices become interesting. Chaining stores multiple values at the same index using a linked list or similar structure, keeping the array compact but adding pointer overhead. Open addressing probes for the next available slot using strategies like linear probing, quadratic probing, or double hashing, each with different clustering behaviors and cache-friendliness profiles. Load factor, the ratio of stored items to array size, determines when resizing becomes necessary.

Active learning approaches work especially well here because students can physically simulate the hash-and-store process, reveal the hidden costs of collisions, and compare strategies by measuring lookup times on real data sets rather than just reading about them.

Key Questions

1. How do hash collisions impact the performance of a data retrieval system?
2. Differentiate between common collision resolution techniques like chaining and open addressing.
3. Design a hash function for a specific data type and evaluate its effectiveness.

Learning Objectives

• Analyze the time complexity of hash map operations (insertion, deletion, lookup) under various collision scenarios.
• Compare and contrast the performance characteristics of chaining and open addressing collision resolution techniques.
• Design and implement a hash function for a given data type, justifying the choice of algorithm and evaluating its collision rate.
• Evaluate the impact of load factor on hash map efficiency and determine appropriate resizing strategies.
• Critique the trade-offs between different open addressing probing methods (linear, quadratic, double hashing).

Before You Start

Arrays

Why: Students need a foundational understanding of array indexing and memory allocation to grasp how hash maps use arrays.

Linked Lists

Why: Knowledge of linked lists is essential for understanding the chaining collision resolution technique.

Basic Algorithms and Time Complexity (Big O Notation)

Why: Students must understand Big O notation to analyze the performance benefits and drawbacks of hash maps and collision resolution strategies.

Key Vocabulary

Hash Function	A function that takes an input (key) and returns a fixed-size integer (hash code), typically used as an index in an array.
Hash Collision	A situation where two different keys produce the same hash code, mapping to the same index in the hash map's underlying array.
Chaining	A collision resolution strategy where each array index stores a pointer to a secondary data structure (like a linked list) holding all elements that hash to that index.
Open Addressing	A collision resolution strategy where, upon collision, the algorithm probes for an alternative empty slot within the hash map's array itself.
Load Factor	The ratio of the number of stored elements to the size of the underlying array, indicating how full the hash map is.

Watch Out for These Misconceptions

Common Misconception

Hash maps always retrieve data in O(1) time regardless of implementation.

What to Teach Instead

O(1) is the average case assuming a good hash function and a reasonable load factor. With many collisions, lookup degrades toward O(n). Having students measure actual lookup times at high load factors makes this trade-off concrete rather than abstract.

Common Misconception

Any collision resolution strategy produces equivalent performance.

What to Teach Instead

Chaining and open addressing have different memory footprints, cache behavior, and sensitivity to load factor. Linear probing suffers from primary clustering while quadratic probing reduces it at the cost of secondary clustering. Benchmarking activities surface these differences more effectively than lecture alone.

Common Misconception

A hash function just needs to be random to work well.

What to Teach Instead

Good hash functions must be deterministic (same input always produces same output), fast to compute, and distribute keys uniformly. Randomness without determinism breaks lookup entirely. Analyzing flawed hash functions, such as those that ignore parts of the key, helps students understand all three requirements.

Active Learning Ideas

Simulation Activity: Human Hash Table

Assign students numbered seats representing array slots. Give each student a card with a key; they apply a simple modulo hash function and walk to their seat. When collisions occur, the class must decide in real time whether to chain (share the seat with a list) or probe (find the next open seat). Debrief by measuring how many steps each lookup required.

25 min·Whole Class

Think-Pair-Share: Choosing the Right Collision Strategy

Present three scenarios: a phone book lookup, a cache for web requests, and a frequency counter for streaming data. Pairs analyze which collision resolution strategy fits each scenario and why, then share reasoning with the class. Focus discussion on load factor and memory trade-offs.

15 min·Pairs

Collaborative Problem-Solving: Benchmarking Hash Map Performance

Students implement both chaining and linear probing in Python or Java, insert the same 1,000-item dataset, and measure average lookup times at different load factors. They graph results and write a one-paragraph recommendation. Comparing empirical data against theoretical expectations builds intuition for when theory and practice diverge.

40 min·Pairs

Gallery Walk: Hash Function Design Critique

Post four hash function implementations around the room, each with a different weakness (always returns 0, ignores most of the key, causes primary clustering). Groups rotate every four minutes, annotating sticky notes with the flaw they identified and a proposed fix. Whole-class debrief consolidates the criteria for a good hash function.

20 min·Small Groups

Real-World Connections

• Software engineers at Google use hash maps extensively to implement features like URL shortening services, where unique short codes map to long web addresses, requiring fast lookups.
• Database systems, such as those powering e-commerce sites like Amazon, utilize hash maps for indexing records, enabling quick retrieval of product information or customer data based on unique identifiers.

Assessment Ideas

Exit Ticket

Provide students with a small array (size 10) and a list of 5 key-value pairs. Ask them to: 1. Choose a simple hash function (e.g., key % array size). 2. Show the resulting array after inserting all pairs using chaining. 3. Identify any collisions.

Quick Check

Present students with two different hash functions for the same set of keys. Ask them to calculate the load factor and the number of collisions for each function. Which function appears more effective and why?

Discussion Prompt

Facilitate a class discussion comparing chaining and open addressing. Ask: 'When might chaining be preferable to open addressing, and what are its main drawbacks? Conversely, when would open addressing offer advantages, and what are its potential pitfalls?'

Frequently Asked Questions

What is a hash collision and why does it happen?

A hash collision occurs when two different keys produce the same array index after applying the hash function. Collisions are mathematically inevitable once the number of possible keys exceeds the array size. The goal is not to eliminate collisions but to resolve them efficiently so that average lookup time stays close to O(1).

What is the difference between chaining and open addressing in hash maps?

Chaining stores multiple values at the same index using a secondary structure like a linked list. Open addressing keeps all data in the main array and finds the next available slot when a collision occurs. Chaining handles high load factors more gracefully; open addressing is more cache-friendly at low load factors since data stays contiguous in memory.

When should you use a hash map instead of a sorted array or binary search tree?

Use a hash map when you need fast average-case lookups and do not require keys to be ordered. Sorted arrays and BSTs maintain order and support range queries, but their O(log n) lookup is slower than a well-designed hash map's O(1) average. If ordering matters, a tree-based structure is usually preferable.

How does active learning help students understand hash map collision resolution?

Physical simulation, where students act as array slots and walk through insertions and collisions, makes the abstract concept tangible. Students experience firsthand how linear probing clusters and why chaining adds overhead, building intuitions that reading code examples alone rarely produces. Benchmarking activities then connect the simulation to measurable performance outcomes.