Layers of Logic

Foundation 03

Hash Map

A table that associates each unique key with one value.

Core4 operations comparedJava · Python · C++
01

Mental model

What the structure guarantees

A hash function turns a key into a table position. Different keys can land in the same region, so the implementation also stores enough information to resolve collisions and still compare the original keys.

02

Implementation

How that model appears in code

Average constant-time lookup depends on a suitable hash function and enough table capacity. A hash map does not sort keys unless a different ordered-map implementation is chosen.

Hash Map basics

Map<String, Integer> count = new HashMap<>();
count.put("a", count.getOrDefault("a", 0) + 1);
boolean seen = count.containsKey("a");
03

Operation costs

What gets more expensive as the input grows

OperationCostWhy
Insert or update a keyO(1) averageHashing selects a small table region.
Look up or remove a keyO(1) averageThe same hash leads back to its region.
Visit every entryO(n)Every stored key-value pair is visited.
Worst-case lookupO(n)Many collisions can force a long search.
04

Tradeoffs

Choose it for the operations it makes cheap

Good fit

  • Frequency counts
  • Remembering an item’s earlier position
  • Membership plus associated data

Poor fit

  • Sorted traversal
  • Range queries
  • Small fixed key sets where an array is simpler

Used by

Two Pointers alternativesSliding Window
05

Common mistakes

Errors that survive a first glance

  1. Missing is different from present with a zero value

    Check key membership when that distinction changes the answer.

  2. Mutable keys are unsafe

    Changing a key after insertion can change its hash and make the entry unreachable.

  3. Iteration order is not a sorting guarantee

    Use an ordered map or sort the keys when order is part of the result.