Track 16 · Lesson 6 of 12

Hashing for speed

Use dictionaries and sets to replace repeated searching with constant-time lookups: find repeats, pairs, groups and duplicates in one pass.

You will be able to

• Explain why lookups in a dict or set take about the same time regardless of size
• Replace a nested search loop with a single pass and a set or dict
• Solve pair-finding problems such as two-sum in O(n)
• Count, group and deduplicate records in one pass, including normalising messy keys