Interview OS
Back to Algorithms & Data Structures

Library

Hash tables

Average O(1) lookup via hashing.

Associative

Overview

A hash table maps keys to buckets via a hash function for average O(1) insert and lookup. The important nuances are collision handling, load factor, and why worst-case degrades to O(n).

How it works

Associative
KeyBucketLookupOutputHash fnh(k)StoreO(1) avgProbeload factorUse
ClientDataServiceEdge

Step by step, with examples

  1. 1

    Hash fn

    • Map a key to a bucket index.
  2. 2

    Store

    • Resolve collisions via chaining/probing.
  3. 3

    Probe

    • Find or insert within the bucket.
  4. 4

    Use

    • Dedup, counting, and caching.
    • Example: dict, set

Overview

Maps keys to buckets via a hash function; average O(1) get/set, O(n) worst case under collisions.

Key idea

Trade memory for speed — most 'have I seen this?' problems become O(n) with a hash set.

When to use it

  • Counting / frequency
  • Deduplication
  • Memoization

Common pitfalls

  • Mutable keys
  • Assuming ordering
  • Worst-case collisions in adversarial input

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides