A Hash Table, also known as a Hash Map, is a data structure that provides a mechanism to store and retrieve data based on key-value pairs.

It is an associative array abstract data type where the key is hashed, and the resulting hash value is used as an index to locate the corresponding value in a bucket or slot.

Key Features

• Unique Keys: Each key in the hash table maps to a single value.
• Dynamic Sizing: Can adjust its size based on the number of elements.
• Fast Operations: Average time complexity for most operations is $O(1)$.

Visual Representation

Core Components

Hash Function

The hash function converts each key to a numerical hash value, which is then used to determine the storage location, or “bucket.”

Buckets

Buckets are containers within the hash table that hold the key-value pairs. The hash function aims to distribute keys uniformly across buckets to minimize collisions.

Collision Handling

• Open-Addressing: Finds the next available bucket if a collision occurs.
• Chaining: Stores colliding keys in a linked list within the same bucket.

Complexity Analysis

• Time Complexity: $O(1)$ - average and best-case, $O(n)$ - worst-case.
• Space Complexity: $O(n)$

Code Example: Hash Table

Here is the Python code:

# Initialize a hash table
hash_table = {}

# Add key-value pairs
hash_table['apple'] = 5
hash_table['banana'] = 2
hash_table['cherry'] = 3

# Retrieve a value
print(hash_table['apple'])  # Output: 5

# Update a value
hash_table['banana'] = 4

# Remove a key-value pair
del hash_table['cherry']