Skip to content

hash table

A hash table is a data structure that maps keys to values and supports fast lookup, insertion, and deletion by computing an array index directly from each key. A hash function turns each key into a hash code, an integer that maps to a slot in an underlying array. From there, the value either settles into a free slot or runs into a collision with another key.

Here’s a diagram of a hash table in action:

A hash function turns a key into a hash code that maps to an array slot. A free slot stores the value, and a collision falls back to chaining or open addressing.
From Key to Slot, With Collision Handling

On average these operations take constant O(1) time, which makes hash tables the default choice for lookup-heavy work. The catch is collisions, where two distinct keys map to the same slot.

Implementations resolve collisions by chaining, which keeps colliding entries in a per-slot list, or by open addressing, which probes for the next free slot.

Try it on the chained hash table below: insert keys to watch them hash into slots and collide, then find one to see the lookup hash straight to its slot and scan only that short chain. To keep the arithmetic visible, the demo uses a simple stand-in hash that sums the key’s character codes:

Interactive diagram — enable JavaScript to view.

When too many collisions pile up, lookup performance can degrade toward O(n). A hash table avoids this by tracking its load factor, the ratio of stored entries to the number of slots. Once that ratio exceeds a set threshold, the table resizes and rehashes its contents into a larger array.

Hash tables require keys to be hashable and usually immutable, so a key’s hash never changes while it is stored.

The structure is the foundation of Python’s built-in dictionary and set, and some languages call the same data structure a hash map.

Build a Hash Table in Python With TDD

Tutorial

Build a Hash Table in Python With TDD

In this step-by-step tutorial, you'll implement the classic hash table data structure using Python. Along the way, you'll learn how to cope with various challenges such as hash code collisions while practicing test-driven development (TDD).

intermediate algorithms data-structures

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated June 24, 2026 • Reviewed by Leodanis Pozo Ramos
Computer Science Glossary Share Feedback