Hash Tables & Hash Maps

A Hash Table (also called a Hash Map) is a data structure that stores key-value pairs. It uses a hash function to compute an index (called a bucket) where the value is stored.

This allows average-case O(1) lookups, insertions, and deletions — making hash tables one of the fastest data structures for key-value storage.

Key Terms:

• Hash Function — Converts a key into a numeric index
• Bucket — A slot in the underlying array that stores values
• Key — The identifier used to store and retrieve a value
• Value — The data associated with a key
• Collision — When two different keys hash to the same index

A hash function takes a key (like a string) and converts it into a numeric index. A simple approach: sum all the character codes and take the remainder when dividing by the table size.

Formula: index = (sum of char codes) % tableSize

Insert key-value pairs into the hash table below. The key is hashed to find its bucket, and the value is stored there. Lookups work the same way — hash the key, go directly to the bucket.

Average time complexity: O(1) for both insert and lookup.

When two keys hash to the same bucket, we have a collision. There are two common strategies to resolve it:

• Chaining — Each bucket holds a linked list of entries
• Linear Probing — Find the next empty slot in the array

The load factor is the ratio of stored entries to the number of buckets: load factor = entries / buckets.

When the load factor exceeds a threshold (commonly 0.75), the table rehashes: it doubles in size and all entries are re-inserted at new positions.

1. What is the average time complexity for looking up a key in a hash table?

2. Which collision resolution strategy stores a linked list in each bucket?

3. What typically happens when a hash table's load factor exceeds 0.75?