gen-define-a-hash-table-and-give-one-short-worked-example-754c

Define a hash table and give one short worked example.

# Hash Table ## Definition A **hash table** (or hash map) is a data structure that stores key-value pairs and provides fast lookups, insertions, and deletions. It uses a **hash function** to compute an index (hash code) from a key, which determines where to store the corresponding value in an underlying array. **Key characteristics:** - Average time complexity: O(1) for search, insert, and delete - Uses a hash function to map keys to array indices - Handles collisions (when different keys hash to the same index) --- ## Worked Example **Scenario:** Store student IDs and names in a hash table with array size 5. **Hash function:** `hash(key) = key % 5` ### Operations: 1. **Insert (12345, "Alice")** - `12345 % 5 = 0` → store at index 0 2. **Insert (67890, "Bob")** - `67890 % 5 = 0` → collision! (handle with chaining or probing) - Using chaining: store both at index 0 in a linked list 3. **Insert (54321, "Carol")** - `54321 % 5 = 1` → store at index 1 ### Resulting Hash Table: ``` Index 0: → [12345: "Alice"] → [67890: "Bob"] Index 1: → [54321: "Carol"] Index 2: → null Index 3: → null Index 4: → null ``` **Lookup (67890):** Hash to index 0, search the chain → find "Bob" ✓