A hash table is a data structure that stores data as key-value pairs and uses a hash function to quickly compute the storage location.

When we write:

set("abc", "xyz")

Internally, it becomes:

index = hash("abc") % array_size
A[index] = ("abc", "xyz")

This means: - The key (“abc”) is passed into a hash function - The hash function converts it into a number - That number is reduced into a valid array index using modulo (%) - The value is stored together with the key at that index

In real implementations, each slot is usually a “bucket”, not a single value:

A[index] = list of (key, value)

Even if there is only one element, it is still stored inside a bucket.

If no other key maps to the same index:

A[index] = [("abc", "xyz")]

This is the simplest case.

Different keys can map to the same index:

"abc" → index 2
"def" → index 2

In this case:

A[2] = [
  ("abc", "xyz"),
  ("def", "123")
]

This is called “chaining”.

If the same key is inserted again:

set("abc", "v1")
set("abc", "v2")

The hash table does NOT create duplicates.

Instead, it updates the existing value:

Before:

A[index] = [("abc", "v1")]

After:

A[index] = [("abc", "v2")]

Rule:

Same key → overwrite value

When we do:

get("abc")

Steps: 1. Compute index = hash(“abc”) % array_size 2. Go to A[index] 3. Search inside the bucket 4. Match the key exactly 5. Return its value

Example:

A[index] = [("abc", "xyz"), ("def", "123")]

Only return value where key == “abc”

Two-level thinking:

High-level:

key → hash(key) → index → value

Real implementation:

key → hash(key) → index → A[index] = list of (key, value)

- Hash table maps keys to values using a hash function - Index is computed as: hash(key) % array_size - Each slot is a bucket storing (key, value) - Same key overwrites old value - Different keys with same index are stored together (collision handling) - Average time complexity for get/set is O(1)

Hash tables are fast because they convert a key directly into an index, avoiding full scanning of data structures like arrays or lists.