Hash Tables / Hash Maps

A hash table (also known as a hash map) is a data structure that stores key–value pairs and allows fast insertion, deletion, and lookup. By using a hash function to map keys to indices, hash tables achieve average-case constant time performance for most operations.

Hash tables are one of the most widely used data structures and appear in databases, caches, symbol tables, compilers, and almost every real-world software system.

What Is a Hash Table?

A hash table consists of:

• Keys - unique identifiers
• Values - data associated with keys
• Hash function - maps keys to indices
• Buckets - storage locations for values

Key ──hash──▶ Index ──▶ Bucket

The hash function determines where a key-value pair is stored.

Basic Idea

1. A key is passed to a hash function
2. The hash function produces an index
3. The value is stored at that index
4. The same process is used to retrieve the value

hash("apple") → 3
table[3] = 42

Why Hash Tables Are Fast

Hash tables avoid scanning data linearly.

This makes hash tables ideal for frequent lookups.

Collisions

A collision occurs when two different keys produce the same index.

Example:

hash("cat")  → 2
hash("dog")  → 2

Both keys map to the same bucket.

Collision Resolution Techniques

Hash tables handle collisions using:

1. Separate Chaining

Each bucket stores a list of entries.

Index 2 → ("cat", 1) → ("dog", 4)

2. Open Addressing

If a bucket is occupied, probe for the next available slot.

Index 2 → occupied → try 3 → try 4

Rust’s standard HashMap uses hashing + probing strategies internally.

Load Factor

The load factor measures how full the table is:

load factor = number of entries / number of buckets

A high load factor increases collisions. Hash tables resize automatically to maintain performance.

Common Operations

Hash tables typically support:

• Insert (put)
• Lookup (get)
• Delete (remove)
• Update

All run in O(1) average time.

Hash Maps in Rust

Rust provides HashMap<K, V> in std::collections.

It offers:

• Safe memory management
• Automatic resizing
• Protection against hash collision attacks
• High performance

Why Hash Tables Are Useful

Hash tables are ideal when:

• Fast lookups are required
• Data is accessed by key
• Order does not matter
• Insertions and deletions are frequent

They are foundational for caches, indexes, symbol tables, and memoization.