Wiki.Quizz.vn

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Hash Table Concept ======

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.

===== Basic Idea =====

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

===== Important Correction: Real Structure =====

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.

===== Case 1: No Collision =====

If no other key maps to the same index:

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

This is the simplest case.

===== Case 2: Collision (Different Keys, Same Index) =====

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".

===== Case 3: Same Key (Update Value) =====

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

===== Case 4: Lookup (get operation) =====

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"

===== Correct Mental Model =====

Two-level thinking:

High-level:
  key → hash(key) → index → value

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

===== Summary =====

- 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)

===== Key Insight =====

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