13. Hash Tables (Mapping Keys to Values)

Hash Tables (also known as Dictionaries or Hash Maps) are one of the most powerful and widely used data structures due to their speed.

Concept

A Hash Table stores data in an array, but uses a special function called a hash function to map the input key (like a name) to a numeric index where the corresponding value (like a phone number) is stored.

Performance

Ideally, hash tables offer nearly O(1) (constant time) performance for:

1. Insertion
2. Deletion
3. Lookup

This efficiency relies on having a good hash function that minimizes collisions (multiple keys mapping to the same index), which we will address later.