Computing · JC 2 · Abstract Data Structures and Algorithms · Semester 1

Hash Tables and Collision Resolution Strategies

Students will understand how variables are used to store and retrieve different types of data (numbers, text) in a program.

• MOE Syllabus Outcomes
• MOE: Programming - Middle School

About This Topic

Hash tables enable fast data storage and retrieval by using a hash function to map keys to array indices, achieving average O(1) operations. JC 2 students examine collision resolution when multiple keys hash to the same index: separate chaining appends elements to linked lists at that index, while open addressing probes alternative slots using linear probing, quadratic probing, or double hashing. They compare these strategies, analyzing how load factor influences worst-case O(n) and average-case lookup times, and derive expected probes under uniform hashing.

This topic anchors the Abstract Data Structures and Algorithms unit, linking to time complexity analysis and hash function design. Students justify uniform distribution properties and recognize how poor hashes cause clustering and degrade to linear search. These skills support real applications in databases, caches, and search engines, fostering rigorous evaluation of algorithmic efficiency.

Active learning suits this topic well. Students implement tables in code, simulate collisions with physical props like bins and balls, and benchmark strategies with datasets of rising loads. Such hands-on tasks reveal performance trade-offs concretely, build debugging intuition, and connect theory to measurable outcomes.

Key Questions

1. Compare separate chaining and open addressing (linear probing, quadratic probing, double hashing) as collision resolution strategies, analysing how each affects worst-case and average-case lookup time as load factor increases.
2. Derive the expected number of probes for a successful search under uniform hashing with open addressing and explain the significance of the load factor threshold for rehashing.
3. Design and evaluate a hash function for a given key domain, justifying its distribution properties and explaining how a poor hash function can cause worst-case O(n) performance.

Learning Objectives

• Compare the performance of separate chaining and open addressing (linear probing, quadratic probing, double hashing) under varying load factors, analyzing their impact on worst-case and average-case lookup times.
• Derive the expected number of probes for a successful search in an open addressing hash table assuming uniform hashing, and explain the significance of the load factor threshold for rehashing.
• Design and evaluate a hash function for a given key domain, justifying its distribution properties and explaining how a poor hash function can lead to O(n) worst-case performance.
• Analyze the trade-offs between different collision resolution strategies in terms of space complexity and time complexity for insertion, deletion, and search operations.

Before You Start

Arrays and Lists

Why: Students need a solid understanding of array indexing and manipulation to grasp how hash tables store data and how collisions are handled by probing.

Basic Time Complexity Analysis (Big O Notation)

Why: Students must understand Big O notation to analyze and compare the efficiency of different collision resolution strategies and hash functions.

Linked Lists

Why: Understanding linked lists is essential for comprehending the separate chaining collision resolution strategy.

Key Vocabulary

Hash Function	A function that takes a key as input and returns an integer index, intended to distribute keys uniformly across an array.
Collision	A situation where two different keys are mapped to the same index in a hash table by the hash function.
Separate Chaining	A collision resolution strategy where each array slot points to a linked list (or other data structure) containing all keys that hash to that slot.
Open Addressing	A collision resolution strategy where all elements are stored directly in the hash table array, and collisions are resolved by probing for an alternative empty slot.
Load Factor	The ratio of the number of elements stored in a hash table to the total number of slots available in the table.

Watch Out for These Misconceptions

Common Misconception

Hash tables always run in O(1) time.

What to Teach Instead

Worst-case performance hits O(n) from clustering or poor hashes. Simulations with physical buckets or code benchmarks at high loads let students observe and quantify degradation, correcting fixed-time assumptions through data.

Common Misconception

Linear probing outperforms all other strategies.

What to Teach Instead

It suffers primary clustering, worsening probes faster than quadratic or double hashing at moderate loads. Group coding races comparing probe counts on identical data reveal these differences, guiding strategy selection.

Common Misconception

Load factor above 1.0 is acceptable.

What to Teach Instead

Performance plummets before load factor 1; rehash at 0.7 threshold. Graphing class benchmark data visualizes probe spikes, emphasizing proactive resizing via active measurement.

Active Learning Ideas

Physical Simulation: Collision Buckets

Provide cups as hash buckets and colored balls as keys numbered for hashing. Groups compute hashes, place balls, and resolve collisions by chaining (stack in cup) or linear probing (next cup). Record probe counts for 20 insertions, then discuss patterns.

30 min·Small Groups

Pair Coding: Separate Chaining Table

Pairs write a Python hash table using lists for chaining. Insert 50 keys with deliberate collisions, implement search, and count probes. Test with load factors 0.5 and 0.9, logging average times.

45 min·Pairs

Group Benchmark: Probing Strategies

Small groups code linear, quadratic, and double hashing tables. Generate random datasets, measure insert/search times up to load factor 0.8, and plot results in shared Google Sheets for class comparison.

50 min·Small Groups

Individual Challenge: Hash Function Design

Students design a hash for student IDs or strings, aiming for even distribution. Submit code, class tests all on same dataset, and votes on best via probe averages and visuals.

40 min·Individual

Real-World Connections

• Database systems, such as PostgreSQL or MySQL, use hash tables extensively for indexing to speed up data retrieval operations, allowing applications to query records quickly based on specific fields.
• Web browsers and network routers employ hash tables to implement caches, mapping URLs or IP addresses to cached content or routing information for faster access and efficient network traffic management.
• Software developers use hash tables (often called dictionaries or maps in programming languages) to store configuration settings or user preferences, enabling rapid lookup of specific parameters.

Assessment Ideas

Quick Check

Present students with a small hash table example (e.g., size 5) and a list of keys. Ask them to trace the insertion of each key using linear probing, identifying any collisions and showing the final state of the table. Then, ask them to calculate the load factor.

Discussion Prompt

Facilitate a class discussion by posing the question: 'When would you choose separate chaining over open addressing, and why?' Prompt students to consider scenarios with frequent insertions/deletions versus scenarios prioritizing memory efficiency, referencing load factor and probe sequences.

Exit Ticket

Provide students with a simple key-value pair (e.g., 'apple', 5). Ask them to design a basic hash function for a small table (e.g., size 7), calculate the hash index, and explain how they would handle a collision if another key also hashed to the same index using quadratic probing.

Frequently Asked Questions

What are collision resolution strategies in hash tables?

Key strategies include separate chaining, which links colliding keys in lists per slot, and open addressing: linear probing steps sequentially, quadratic skips squares, double hashing uses a second function. Each balances space and speed; chaining handles high loads better, probing saves memory. Students analyze via load factor impacts on probes.

How does load factor affect hash table performance?

Load factor (items/slots) rises degrade average probes: under 0.5, linear probing nears 1.5 probes; past 0.7, it surges. Chaining probes grow logarithmically. Deriving formulas and plotting simulations show rehash thresholds, preventing O(n) fallbacks in practice.

How can active learning help students understand hash tables?

Hands-on coding of strategies, physical bucket simulations, and benchmark races make abstract probes and load effects visible. Pairs debug real slowdowns, groups compare graphs, turning theory into tangible trade-offs. This builds intuition for analysis over rote memorization, aligning with MOE inquiry skills.

When should you rehash a hash table?

Rehash when load factor nears 0.7 for open addressing to avoid probe explosions, doubling table size. Chaining tolerates higher but slows insertions. Students derive this from expected probe math and confirm via timed tests on growing datasets, justifying dynamic resizing in code.