Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 225 ยท Hashing

Hash Tables

Learn how hash tables work: hash function, buckets, collisions, load factor and resizing. Build a tiny hash map in Python and see why lookups are O(1) on average.

Suppose you keep a phone book in a list of (name, number) pairs. To find "Maya" you scan from the start until you hit her: O(n). Sort the list and use binary search and you get O(log n), but now every insert has to keep the order. Wouldn't it be nice to jump straight to the right spot, as if the name itself told you where to look?

That is what a hash table does. It turns a key into an array index with a function, stores the value at that index, and later repeats the same calculation to find it again. On average, insertion, lookup and deletion are all O(1). Python's dict and set are hash tables, and so are the maps and sets in almost every other language. It is arguably the most useful data structure in everyday programming.

The core idea

An array lets you reach any slot by index in O(1) (see arrays). The trouble is that keys are not small integers: they are strings, tuples, large numbers. A hash function converts a key into an integer, and the remainder after dividing by the table size picks a slot.

TEXT
key "maya" --hash--> 48213907 --% 8--> slot 3

slots:   0     1     2     3        4     5     6     7
       [   ] [   ] [   ] [maya:55] [   ] [   ] [   ] [   ]

To look up "maya", compute the same hash, take % 8, and open slot 3. No scanning. The vocabulary:

  • Key: what you search by. Value: the data attached to it.
  • Hash function: key -> integer. The same key must always give the same integer within one run.
  • Table: an array of m slots, usually called buckets.
  • Index: hash(key) % m.

Collisions are unavoidable

There are infinitely many possible keys and only m buckets. By the pigeonhole principle, two different keys will sometimes land in the same bucket. That is a collision. Even with a good hash function it happens early: with just 23 people in a room, there is about a 50% chance that two share a birthday (the same effect, with 365 buckets).

A hash table is therefore two things: a hash function that spreads keys evenly, and a collision strategy for when keys meet anyway. This lesson uses the simplest strategy, separate chaining: each bucket holds a small list of the (key, value) pairs that landed there. Other strategies, such as probing, come in Collision Handling.

TEXT
bucket 0: []
bucket 1: [("ana", 1)] -> [("zed", 9)]      <- two keys collided, both kept
bucket 2: []
bucket 3: [("maya", 55)]

A lookup computes the bucket, then scans that short chain comparing keys with ==. This is why a hash table needs both a hash and an equality test.

A tiny hash map from scratch

We need a hash function that gives the same numbers every time you run the lesson. Python's built-in hash() for strings is deliberately randomized between runs (more in Hash Functions), so here we write our own simple polynomial hash for strings.

Python A tiny hash map with chaining

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the printed buckets. With 4 keys in 8 buckets, some buckets are empty and a few may hold two entries. How crowded the buckets get determines the speed, which brings us to the load factor.

Load factor and resizing

The load factor is

TEXT
load factor = number of stored items / number of buckets

With chaining, the average chain length is the load factor. If it stays below a constant (say 0.75), a lookup scans a handful of entries at most, so operations are O(1) on average. If you keep inserting into a fixed number of buckets the chains grow and everything degrades toward O(n).

So a hash table resizes: when the load factor passes a threshold, allocate a bigger bucket array (often double) and re-insert every item, because hash % m changes when m changes. Rehashing is O(n), but it is rare: doubling means the cost is spread over many inserts, so inserts are amortized O(1), the same argument as for dynamic arrays and in amortized analysis.

Python Load factor and automatic resizing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 100 items the table doubled several times (4 buckets grows to 256), and the load factor ended up below the threshold. Each resize touched every item so far, yet the total across all resizes is less than 2 ร— 100 re-insertions.

Why O(1) is only "on average"

Case Cost When
Average O(1) keys spread evenly, load factor bounded
Worst O(n) all keys collide into one bucket (bad hash or an attack)

To see the worst case, use a terrible hash function that maps every key to the same number. A "hash table" with that function is just a linked list with extra steps.

Python A bad hash function makes everything collide

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real systems defend against this: Python randomizes string hashes per process so an attacker cannot craft thousands of keys that collide on purpose.

Hash tables in Python

You will rarely write your own. Use:

  • dict for key-value pairs and set for membership of unique items.
  • Average O(1) for d[k], d[k] = v, k in d, del d[k].
  • Keys must be hashable: immutable types such as int, str, tuple of hashables. Lists and dicts are not. Why that rule exists is the subject of Hash Functions.
Python Membership: list scan vs set lookup

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simplest table: direct addressing

Before hashing, there is a simpler idea. If every key is already a small integer in the range 0 .. U-1, you do not need a hash function at all: allocate an array of U slots and store the item for key k in slot k. That is a direct address table. Search, insert and delete are all O(1) in the worst case, with no collisions, because two different keys can never share a slot.

Python A direct address table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The weakness is memory. The table needs U slots no matter how many keys you store. Keys that are phone numbers or 64-bit ids would need an array with billions of slots, almost all empty. A direct address table is a good fit when the key range is small and dense (days of the month, ASCII codes, counters indexed by 0-255), and it is the reason a plain list works as a "dictionary" in many frequency-counting tasks.

A hash table keeps the same one-step jump but squeezes a huge key universe into m slots with hash(key) % m. The price is that two keys can now land in the same slot, which is exactly the collision problem on this page and in collision handling.

Hash table vs other structures

Structure Lookup Insert Delete Ordered traversal
Unsorted list O(n) O(1) at end O(n) no
Sorted array O(log n) O(n) O(n) yes
Balanced tree (BST) O(log n) O(log n) O(log n) yes
Hash table O(1) avg O(1) avg O(1) avg no (Python dict keeps insertion order)

Choose a hash table when you need fast lookup by exact key. Choose a tree or sorted array when you need ranges ("all keys between a and b"), the smallest or next-larger key, or sorted output.

Common mistakes

  • Using mutable keys. If a key changes after insertion, its hash changes and it is lost in the wrong bucket. Python forbids list keys for this reason.
  • Defining __eq__ without a matching __hash__. Equal objects must produce equal hashes.
  • Relying on hash values or their order. hash() of strings changes between runs, so never print or persist it.
  • Believing hash tables are always O(1). Poor hash functions, adversarial keys, or an over-full table break the guarantee.
  • Forgetting that resizing rehashes everything, so an individual insert can occasionally take O(n).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a hash function do in a hash table?

    The hash, reduced modulo the number of buckets, tells you which bucket to inspect for a key.
  2. 2. What is a collision?

    Different keys can share a bucket, so every hash table needs a strategy such as chaining or probing.
  3. 3. With separate chaining, 60 items in 20 buckets gives which load factor and meaning?

    Load factor is items divided by buckets, 60 / 20 = 3, which is the average chain length.
  4. 4. Why is insertion into a resizing hash table amortized O(1) even though a resize costs O(n)?

    Because the capacity doubles each time, the total rehashing work over n inserts is proportional to n.
  5. 5. When is a hash table the wrong choice?

    A hash table scatters keys, so it cannot answer range or ordered queries efficiently. A tree or sorted array can.

Summary

  • A hash table maps keys to buckets with hash(key) % bucket_count, giving average O(1) insert, lookup and delete.
  • Collisions are inevitable; chaining stores colliding entries in a short list per bucket.
  • The load factor (items / buckets) controls chain length; the table doubles and rehashes when it gets too full, keeping inserts amortized O(1).
  • Worst case is O(n) when many keys collide, so hash quality matters.
  • Python's dict and set are hash tables; keys must be hashable.
  • Continue with Collision Handling for open addressing and probing.

Next: Collision Handling