What does a hash function do in a hash table?

It converts a key into an index number used to place or find the value

It sorts the keys into alphabetical order

It encrypts the data so it cannot be read

It compresses the data to save memory

What is a "collision" in a hash table?

When two different keys hash to the same index

When the table runs out of memory completely

When a key is looked up but does not exist

When the hash function produces a negative number

Why is looking up a value in a well-designed hash table typically much faster than searching an unsorted array?

The hash function computes the likely location directly, instead of checking items one by one

Hash tables are always stored in faster computer memory

Hash tables automatically delete duplicate keys

Hash tables are smaller than arrays, so there is less to search

Select ALL statements that are true about hash tables.

A hash table stores data as key-value pairs rather than as a plain sequence of values

Chaining handles collisions by storing a small linked list of entries at each index

A poorly chosen hash function can cause many keys to cluster at the same few indices, hurting performance

Hash tables guarantee that data comes back out in the same order it was inserted

Hash Tables

⏱ 8 min✏️ Quiz at the end

Introduction

A hash table (also called a hash map) is a data structure that stores information as key-value pairs and is built to answer one question extremely quickly: "given this key, what value is attached to it?" A phone contacts app is a hash table in disguise — the key is a person's name, the value is their number, and typing a name should feel instant even with thousands of contacts saved.

This is a different job from the structures covered in arrays, linked lists, and trees, which mostly organise a sequence or a hierarchy of values. A hash table instead organises lookups, and it does this using a hash function.

The Hash Function

A hash function takes a key — a name, a word, an ID number, anything — and converts it into a number, which is then used as an index into an underlying array. Feed the same key in twice and the hash function returns the same index both times, which is exactly what allows the table to find a value again later: hash the key, jump straight to that index, and the value is sitting there waiting.

key: "Amara"  →  hash function  →  index 4
key: "Deshi"  →  hash function  →  index 1
key: "Farid"  →  hash function  →  index 4   ← same index as "Amara"!

This is what makes hash tables fast. Searching an unsorted array for a value means checking entries one by one until a match turns up, and that check gets slower as the array grows. A hash table instead computes the location directly from the key, so — on average — looking a value up, inserting a new one, or deleting one all take roughly the same, small amount of time, no matter how many entries the table holds.

Collisions

Look again at the diagram above: "Amara" and "Farid" both hashed to index 4. This is called a collision, and it is not a bug — it is a certainty. Any hash function maps a huge range of possible keys onto a much smaller range of array indices, so sooner or later two different keys will land on the same slot. A hash table's real design challenge is not computing hashes; it is handling collisions gracefully.

Two common strategies:

Chaining — each index in the array holds a small linked list of every entry that hashed there. When "Amara" and "Farid" both land on index 4, the table just adds both entries to that index's list. Looking up "Farid" means hashing to index 4, then checking the short list there — still much faster than scanning the whole table.
Open addressing — if a key's slot is already taken, the table probes forward (index 5, then 6, then 7...) until it finds an empty slot, and remembers that path when looking the key up again.

Load Factor and Resizing

The load factor of a hash table is the number of stored entries divided by the number of available slots. As the load factor climbs, collisions become more frequent and performance degrades — with chaining, the linked lists at each index grow longer, and each lookup has to check more entries. Well-implemented hash tables monitor their load factor and automatically resize (create a bigger underlying array and re-hash every existing entry into it) once it crosses a threshold, trading a one-time cost for keeping future lookups fast.

Why the Hash Function Matters

A good hash function spreads keys evenly across all available indices, so no single slot ends up overloaded while others sit empty. A poorly chosen hash function might send most keys to the same handful of indices, defeating the entire purpose — every lookup would then have to wade through a long chain, degrading toward the same speed as searching an unsorted list one item at a time. Designing hash functions that spread data evenly, even for keys that look similar to each other, is an entire area of computer science in its own right.

Where Hash Tables Show Up

Hash tables are everywhere in real software, not just in textbooks. Dictionaries in Python, objects in JavaScript, and maps in Java are all built on hash tables under the hood — that is precisely why looking up a value by key in those languages feels instant regardless of how much data is stored. Databases use hash indexes to jump straight to a row instead of scanning a whole table. Spell checkers hash every word in the dictionary so checking whether a typed word exists is a single lookup rather than a full search. Caches (including your web browser's) use hash tables keyed by URL so a previously visited page can be recalled instantly.

Hash Tables vs Other Structures

Feature	Array	Linked List	Hash Table
Organised by	Position (index 0, 1, 2...)	Sequence of pointers	Key, via a hash function
Typical lookup speed	Instant by index, slow by value	Slow — must walk from the head	Fast on average, by key
Preserves insertion order	Yes	Yes	No
Best suited to	Ordered sequences	Frequent insertion/deletion in sequence	Fast lookup by a unique key

Key Words

Hash function — converts a key into an index in the underlying array
Key-value pair — the two-part entry a hash table stores: a key used to look something up, and the value attached to it
Collision — when two different keys hash to the same index
Chaining — resolving collisions by storing a linked list of entries at each index
Load factor — the ratio of stored entries to available slots, used to decide when to resize