Hash Tables and Dictionaries

Hash tables

A hash table stores key–value pairs and allows very fast lookup — ideally O(1) (constant time). A hash function converts a key into an index (a position in an underlying array) where the value is stored.

index = hash(key) MOD table_size

The hash function

A good hash function:

• is quick to compute;
• produces indexes evenly spread across the table (to minimise clashes);
• is deterministic (the same key always gives the same index).

Example: to store the key 137 in a table of size 10: 137 MOD 10 = 7 → store at index 7.

Collisions

A collision happens when two different keys hash to the same index. Collisions must be resolved:

• Chaining (open hashing): each table slot holds a list of items; collided items are appended to the list at that index.
• Open addressing (closed hashing): find the next free slot.
• Linear probing: try the next index, then the next, until an empty slot is found.
• Rehashing / double hashing: apply a second hash to jump to another slot.

Load factor

load factor = number of items ÷ table size

As the table fills up, collisions become more frequent and performance drops. When the load factor gets too high, the table is usually resized (rehashed) into a larger array.

Performance

• Best/average case: O(1) for search, insert and delete — the strength of hash tables.
• Worst case: O(n) if many collisions force long probe sequences or chains.

Dictionaries

A dictionary (or map/associative array) is an ADT that stores key → value pairs and is very commonly implemented using a hash table. Lookups are by key rather than index.

Worked example

Using hash(key) = key MOD 7, where is the key 45 stored, and what if 52 is added next?

• 45 MOD 7 = 3 → index 3.
• 52 MOD 7 = 3 → collision! With linear probing, try index 4 (next free) → store 52 there. ✓

Common mistakes

• Assuming hash tables are always O(1) — heavy collisions degrade to O(n).
• Forgetting a collision-resolution method is needed.
• Thinking the hash stores the key directly — it produces an index to store at.

Exam tips

• Explain the hash function's job (key → index via MOD) and the properties of a good one.
• Know at least two collision-resolution methods (chaining and linear probing).
• Link the load factor to performance and the need to resize/rehash.

Key facts to remember

• Hash table: hash function maps a key to an index for O(1) average lookup.
• Collisions (two keys, same index) are resolved by chaining or open addressing (linear probing / rehashing).
• High load factor → more collisions → resize; worst case is O(n). Dictionaries are typically built on hash tables.