Skip to content
BENIBIX Learn

Hash Table

Development🧮 Algorithms & Data StructuresData Structures

Also known as Hash Map, Hashmap, Dictionary (Data Structure)

A store of keys and values. It finds a value by its key in one step.

Think of it like

Think of it like a coat check. Your ticket number says exactly which hook your coat is on.

Example

Emma's app keeps 2 million users in a hash table keyed by email. Finding one user takes the same time as finding one of 10.

Why it matters

It is the fastest common way to look things up by name. Caches, databases and counters all use one.

Definition

A hash table stores pairs of keys and values. It finds a value by its key in one quick step. A hash function turns each key into a number that says where to keep it. To look it up again, the table runs the same function and goes straight there. On average, finding, adding and removing all take O(1) time. Python's dict and JavaScript's Map are hash tables.

Common mistake

Expecting the keys to come out in order. Many hash tables keep no order; sort the keys if you need one.

Key takeaways

  1. 1
    Keys and values. Find a value by its key.
  2. 2
    A hash picks the spot. Same key, same spot.
  3. 3
    O(1) on average. However many items.