Hash Table

A hash table (also called a hash map or dictionary) is a data structure that stores key-value pairs. A hash function converts each key into a number, which selects a slot in an underlying array where the value is kept, so lookups do not need to scan the whole collection.

Why it matters

Hash tables give average O(1) time for insert, lookup and delete, which makes them one of the most useful structures in programming. Python dicts, JavaScript objects and Maps, Java HashMap and Go maps are all hash tables. Two different keys can hash to the same slot, a collision, handled by chaining (a small list per slot) or open addressing (probing for another slot). In the worst case, with many collisions, operations degrade toward O(n), and iteration order is often not meaningful.

Example

counts = {}
for word in ["up", "down", "up"]:
    counts[word] = counts.get(word, 0) + 1
# {'up': 2, 'down': 1}

Each word is hashed to find its counter immediately, rather than searching a list.

Common mistakes

• Using a mutable object as a key whose hash changes after insertion.
• Relying on iteration order where the language does not guarantee it.
• Confusing a hash table with a cryptographic hash.

Related

• Hashing
• Key-value store
• Array
• Big O notation

This page is general information written by our editorial team and updated when documentation changes. Servers and providers differ, so test changes safely first. See our editorial policy and disclaimer.