Hash Tables

This lesson covers hash tables — a data structure that provides fast average-case access to data using a hash function to compute an index from a key. Hash tables are used extensively in computing for dictionaries, caches, database indexing, and more.

---

What is a Hash Table?

A hash table (also called a hash map) is a data structure that stores key-value pairs. It uses a hash function to convert each key into an index (hash) that determines where the value is stored in an underlying array.

Key       → Hash Function → Index → Store/Retrieve Value
"Alice"   → h("Alice")    → 3     → array[3] = "Alice's data"
"Bob"     → h("Bob")      → 7     → array[7] = "Bob's data"

Key Properties

Property	Description
Key	A unique identifier for each data item.
Value	The data associated with the key.
Hash function	A function that converts a key into an array index.
Bucket/Slot	A position in the underlying array.
Average access time	O(1) for insertion, deletion, and lookup.

---

Hash Functions