Layers of Logic

Foundation 04

Hash Set

A hash table that records only whether a value is present.

Core3 operations comparedJava · Python · C++
01

Mental model

What the structure guarantees

A set is the membership-only form of a hash map. It answers “have I seen this?” without attaching a separate value to the key.

02

Implementation

How that model appears in code

Choose a set when presence is the entire state. Choose a map when you also need a count, index, timestamp, or other value.

Hash Set basics

Set<Integer> seen = new HashSet<>();
seen.add(7);
boolean repeated = !seen.add(7);
03

Operation costs

What gets more expensive as the input grows

OperationCostWhy
Add, find, or remove a valueO(1) averageHashing narrows the search to one region.
Visit all valuesO(n)Each stored value is visited.
Worst-case membership testO(n)Collisions can place many values together.
04

Tradeoffs

Choose it for the operations it makes cheap

Good fit

  • Duplicate detection
  • Visited-state tracking
  • Distinct-value windows

Poor fit

  • Counting occurrences
  • Remembering where a value appeared
  • Sorted output

Used by

Sliding WindowFast & Slow Pointers alternative
05

Common mistakes

Errors that survive a first glance

  1. A set removes duplicates by definition

    If duplicate counts matter, the set has already discarded information you need.

  2. The set version may use O(n) memory

    For cycle detection, two pointers can reach the same time bound with constant extra space.

  3. Order is not guaranteed

    Membership is the contract; display order is not.