hash table

A hash table, also called a hash map or hashmap, 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 value, 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 stores every entry inside the table itself and follows a probe sequence until it finds an empty 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. Other languages ship it under the hash map name, such as Java’s HashMap, while C++ calls it unordered_map. Some languages reserve map for the key-value abstraction and hash table for the structure beneath it, but in most settings the names are interchangeable.

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:

Have a question about this? Mentor AI can show you examples, compare related terms, and point you to tutorials.

  • Ask Mentor AI
  • Pick a question and Mentor AI takes it from here.
By Martin Breuss • Updated Sept. 26, 2026 • Reviewed by Leodanis Pozo Ramos
Computer Science Glossary Share Feedback