TweakCode
FREE
Arrays and Stacks lessons

Hashing

How Hashing works

Before you start

  • Arrays & Strings

    Hashing is the tool for remembering facts while you walk an array. That lesson shows why one remembered fact can replace an inner loop.

    Open lesson

Why it matters

Duplicate records can trigger a second charge, send the same notification twice, or corrupt an import. Pairwise comparison may work for a short list, but its cost explodes as a stream grows. The solution must recognize a repeated value during one pass rather than compare every pair.

Real-world constraint

Charging a card exactly once

Networks drop responses, so clients retry, and the same payment request can arrive twice. Payment APIs such as Stripe accept an idempotency key with each request and remember the keys they have already handled. When a repeated key arrives, the API returns the saved result instead of charging again. At its core that is the line you just traced: if key in seen.

Example

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.

Input
nums = [2, 7, 3, 1, 3]
Output
True

Approach 2 · Resolve the bottleneck

The idea

Keep one example in view

Contains Duplicate

nums = [2, 7, 3, 1, 3]→True

The baseline, Compare every pair, is O(n²) · O(1). The better model below keeps this exact input and removes that bottleneck.

In [2, 7, 3, 1, 3], the final 3 matches the value at index 2. Instead of comparing up to 10 pairs, record each earlier value in a set and test the current value once.

Walk nums = [2, 7, 3, 1, 3] with a set called seen. After the first four values, seen is {1, 2, 3, 7}. The final 3 is already there, so the answer is True; no earlier value needs another comparison.

A set hashes each value to choose where to store or look for it. The final 3 follows the same probe path as the stored 3, then equality confirms the match. Different values can choose the same first slot, a collision, so the table probes another slot and grows before it gets crowded. Those details keep lookup and insertion O(1) on average.

  1. "cat"→hash("cat") % 8→3
  2. "owl"→hash("owl") % 8→6
  3. "dog"→hash("dog") % 8→3
  1. 0
  2. 1
  3. 2
  4. 3
    "cat"→ "dog"
  5. 4
  6. 5
  7. 6
    "owl"
  8. 7
Illustrative bucket numbers for a table of 8 buckets. "cat" and "dog" collide in bucket 3, so that bucket holds both. Finding "dog" hashes once and checks one bucket. Python's dict resolves collisions by probing other slots rather than chaining, but a lookup still checks a handful of slots, not the whole table.

Pro

The rest of this is on Pro

The idea above is free. The walkthrough, the cost, and the practice are on Pro.

See Pro plansSign in